Rearrange Array Elements by Sign — Problem & Solution
Rearrange Array Elements by Sign solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Rearrange Array Elements by Sign is a medium coding problem on arrays, two pointers and simulation, asked in Amazon and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Two Pointers, Simulation
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a 0-indexed integer array nums of even length, holding an equal number of positive and negative integers.
Rearrange it so that consecutive elements have opposite signs, the array starts with a positive integer, and the relative order within the positives and within the negatives is preserved.
Example 1
Input: nums = [3,1,-2,-5,2,-4]
Output: [3,-2,1,-5,2,-4]
Example 2
Input: nums = [-1,1]
Output: [1,-1]
Example 3
Input: nums = [1,-1,2,-2]
Output: [1,-1,2,-2]
Constraints
2 <= nums.length <= 40nums.length is even.Equal counts of positive and negative values.-1000 <= nums[i] <= 1000, and nums[i] != 0
Hints for Rearrange Array Elements by Sign
Hint 1
Split into a list of positives and a list of negatives, each in original order.
Hint 2
Then interleave them, positives at the even indices.
Hint 3
Two cursors over the original array achieve the same in one pass, writing directly into the output.
How to solve Rearrange Array Elements by Sign
Split positives and negatives in original order and interleave, positives at even indices.
Approach
- Filter positives and negatives.
- Emit
pos[k], neg[k]for eachk.
Why it works
Equal counts guarantee the interleave is exact, and filtering preserves relative order.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Two cursors over the original array writing into a preallocated output achieve the same in one pass.
Reference solution
Python
def rearrangeArray(nums):
pos = [x for x in nums if x > 0]
neg = [x for x in nums if x < 0]
out = []
for p, n in zip(pos, neg):
out.append(p)
out.append(n)
return outJava
public static int[] rearrangeArray(int[] nums) {
int[] out = new int[nums.length];
int p = 0, n = 1;
for (int x : nums) {
if (x > 0) {
out[p] = x;
p += 2;
} else {
out[n] = x;
n += 2;
}
}
return out;
}C++
vector<int> rearrangeArray(vector<int>& nums) {
vector<int> out(nums.size(), 0);
int p = 0, n = 1;
for (int x : nums) {
if (x > 0) {
out[p] = x;
p += 2;
} else {
out[n] = x;
n += 2;
}
}
return out;
}JavaScript
var rearrangeArray = function(nums) {
const pos = [], neg = [];
for (let i = 0; i < nums.length; i++) {
if (nums[i] > 0) pos.push(nums[i]);
else neg.push(nums[i]);
}
const out = [];
for (let i = 0; i < pos.length; i++) {
out.push(pos[i]);
out.push(neg[i]);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Two Pointers Technique