Practice › Arrays
Rearrange Array by Sign
Medium · Arrays · Asked at Amazon, Microsoft
The array has an equal number of positive and negative integers (no zeros). Rearrange it so signs alternate, starting with a positive, keeping the original relative order of positives and of negatives.
Input
First line: n. Second line: n space-separated integers.
Output
The rearranged array, space-separated.
Constraints
- 2 ≤ n ≤ 10^5, n is even
Example 1
Input
6 3 1 -2 -5 2 -4
Output
3 -2 1 -5 2 -4
Example 2
Input
2 -1 1
Output
1 -1
Hints
- The answer has positives at even indices (0, 2, 4…) and negatives at odd ones.
- Use two write pointers, pos = 0 and neg = 1, each jumping by 2.
Approach
Make a result array. Scan the input in order: put a positive number at result[pos] and move pos forward by 2; put a negative at result[neg] and move neg forward by 2. Each sign group keeps its original order, and the result starts with a positive.
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> res(n);
int pos = 0, neg = 1;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
if (x > 0) { res[pos] = x; pos += 2; }
else { res[neg] = x; neg += 2; }
}
for (int i = 0; i < n; i++) cout << res[i] << (i + 1 < n ? " " : "\n");
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, a = data[0], data[1 : data[0] + 1]
res = [0] * n
res[0::2] = [x for x in a if x > 0]
res[1::2] = [x for x in a if x < 0]
print(*res)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] res = new long[n];
int pos = 0, neg = 1;
for (int i = 0; i < n; i++) {
long x = sc.nextLong();
if (x > 0) { res[pos] = x; pos += 2; }
else { res[neg] = x; neg += 2; }
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append(i > 0 ? " " : "").append(res[i]);
System.out.println(sb);
}
}Solve Rearrange Array by Sign online · All practice problems