.png)
Rearrange Array by Sign (Positive and Negative)
Problem Statement
You are given an integer array arr containing both positive and negative numbers.
Rearrange the array such that:
- Positive and negative numbers appear alternately
- The relative order of positive numbers and negative numbers is maintained
- The array always starts with a positive number
It is guaranteed that the number of positive and negative elements is equal.
Example 1
Input
arr = [3, 1, -2, -5, 2, -4]
Output
[3, -2, 1, -5, 2, -4]
Example 2
Input
arr = [-1, 1]
Output
[1, -1]
Why This Problem Is Important
- Very common array manipulation problem
- Asked in FAANG & product-based interviews
- Tests stable rearrangement
- Helps understand two-pointer & indexing logic
- Appears in coding rounds
- Important for placement preparation
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Extra Array | O(n) | O(n) |
| Approach 2 | Index Placement (Optimal) | O(n) | O(n) |
⚠️ Note: In-place O(1) solution with order preserved is not feasible in linear time.
Approach 1: Extra Array
Idea
Store positives and negatives separately, then place them alternately in the result array.
Algorithm
- Traverse array and store positives in one list and negatives in another
- Initialize result array
- Place positives at even indices and negatives at odd indices
Time & Space Complexity
- Time: O(n)
- Space: O(n)
Implementations
C
#include
int main() {
int arr[] = {3,1,-2,-5,2,-4};
int n = 6;
int pos[3], neg[3];
int p = 0, q = 0;
for(int i = 0; i < n; i++) {
if(arr[i] > 0)
pos[p++] = arr[i];
else
neg[q++] = arr[i];
}
int idx = 0;
for(int i = 0; i < p; i++) {
arr[idx++] = pos[i];
arr[idx++] = neg[i];
}
for(int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
C++
#include
#include
using namespace std;
int main() {
vector arr = {3,1,-2,-5,2,-4};
vector pos, neg;
for(int x : arr) {
if(x > 0) pos.push_back(x);
else neg.push_back(x);
}
int idx = 0;
for(int i = 0; i < pos.size(); i++) {
arr[idx++] = pos[i];
arr[idx++] = neg[i];
}
for(int x : arr)
cout << x << " ";
return 0;
}
Java
import java.util.*;
public class RearrangeBySign {
public static void main(String[] args) {
int[] arr = {3,1,-2,-5,2,-4};
List pos = new ArrayList<>();
List neg = new ArrayList<>();
for(int x : arr) {
if(x > 0) pos.add(x);
else neg.add(x);
}
int idx = 0;
for(int i = 0; i < pos.size(); i++) {
arr[idx++] = pos.get(i);
arr[idx++] = neg.get(i);
}
System.out.println(Arrays.toString(arr));
}
}
Python
arr = [3,1,-2,-5,2,-4]
pos = []
neg = []
for x in arr:
if x > 0:
pos.append(x)
else:
neg.append(x)
idx = 0
for i in range(len(pos)):
arr[idx] = pos[i]
arr[idx + 1] = neg[i]
idx += 2
print(arr)
JavaScript
let arr = [3,1,-2,-5,2,-4];
let pos = [], neg = [];
for (let x of arr) {
if (x > 0) pos.push(x);
else neg.push(x);
}
let idx = 0;
for (let i = 0; i < pos.length; i++) {
arr[idx++] = pos[i];
arr[idx++] = neg[i];
}
console.log(arr);
Approach 2: Index Placement (Optimal)
Idea
Directly place positive numbers at even indices and negative numbers at odd indices using a new array.
Algorithm
- Create result array of size n
- Initialize posIndex = 0, negIndex = 1
- Traverse original array
- Place positives at posIndex, negatives at negIndex
- Increment indices by 2
Time & Space Complexity
- Time: O(n)
- Space: O(n)
Implementations
C++
#include
using namespace std;
int main() {
int arr[] = {3,1,-2,-5,2,-4};
int n = 6;
int result[6];
int pos = 0, neg = 1;
for(int i = 0; i < n; i++) {
if(arr[i] > 0) {
result[pos] = arr[i];
pos += 2;
} else {
result[neg] = arr[i];
neg += 2;
}
}
for(int i = 0; i < n; i++)
cout << result[i] << " ";
return 0;
}
Java
import java.util.*;
public class RearrangeBySign {
public static void main(String[] args) {
int[] arr = {3,1,-2,-5,2,-4};
int n = arr.length;
int[] result = new int[n];
int pos = 0, neg = 1;
for(int x : arr) {
if(x > 0) {
result[pos] = x;
pos += 2;
} else {
result[neg] = x;
neg += 2;
}
}
System.out.println(Arrays.toString(result));
}
}
Python
arr = [3,1,-2,-5,2,-4]
n = len(arr)
result = [0]*n
pos, neg = 0, 1
for x in arr:
if x > 0:
result[pos] = x
pos += 2
else:
result[neg] = x
neg += 2
print(result)
JavaScript
let arr = [3,1,-2,-5,2,-4];
let n = arr.length;
let result = new Array(n);
let pos = 0, neg = 1;
for (let x of arr) {
if (x > 0) {
result[pos] = x;
pos += 2;
} else {
result[neg] = x;
neg += 2;
}
}
console.log(result);
Dry Run
Input
[3,1,-2,-5,2,-4]
Positives → [3,1,2]
Negatives → [-2,-5,-4]
Final Output:
[3,-2,1,-5,2,-4]
Summary
- Order must be preserved
- Extra space is required for stability
- Index placement is clean and interview-friendly
- Very common medium-level interview problem
Next Problem in the Series
Check if Array Can Be Divided into Equal Sum Subarrays
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
