Arranging the array
Arranging the array is a medium arrays & hashing problem solved with the merge sort like approach pattern.
The best approach, in place (merge sort style with rotation), runs in O(n log n) time and O(log n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from simple (extra array, stable) up.
Problem
Rearrange the array so that all negative numbers come before all non-negative numbers, while keeping the original relative order inside each group.
The in-place version with no extra array is the interesting one: it reuses the merge-sort idea together with the double reversal trick.
Examples
Example 1
- Input
arr = [-3, 3, -2, 2]- Output
[-3, -2, 3, 2]- Why
- Negatives first in their original order, then positives in their original order.
Example 2
- Input
arr = [4, -1, 5, -6, -2]- Output
[-1, -6, -2, 4, 5]
Constraints
1 <= arr.length <= 10^5- Keep the relative order within negatives and within positives.
- Zero counts as non-negative.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Simple (extra array, stable) | O(n) | O(n) |
| In place (merge sort style with rotation) | O(n log n) | O(log n) |
1Simple (extra array, stable)
O(n)O(n)Copy all negatives in order, then all non-negatives in order, into a new array and copy back.
- First pass: collect negatives.
- Second pass: collect non-negatives.
- Write back.
class Solution {
public void rearrange(int[] arr) {
int[] tmp = new int[arr.length];
int k = 0;
for (int x : arr) if (x < 0) tmp[k++] = x;
for (int x : arr) if (x >= 0) tmp[k++] = x;
System.arraycopy(tmp, 0, arr, 0, arr.length);
}
}class Solution:
def rearrange(self, arr: List[int]) -> None:
tmp = [0] * len(arr)
k = 0
for x in arr:
if x < 0:
tmp[k] = x
k += 1
for x in arr:
if x >= 0:
tmp[k] = x
k += 1
arr[:] = tmpclass Solution {
public:
void rearrange(vector<int>& arr) {
vector<int> tmp(arr.size());
int k = 0;
for (int x : arr) if (x < 0) tmp[k++] = x;
for (int x : arr) if (x >= 0) tmp[k++] = x;
arr = tmp;
}
};function rearrange(arr) {
const tmp = new Array(arr.length).fill(0);
let k = 0;
for (const x of arr) if (x < 0) tmp[k++] = x;
for (const x of arr) if (x >= 0) tmp[k++] = x;
for (let i = 0; i < arr.length; i++) arr[i] = tmp[i];
}2In place (merge sort style with rotation)
O(n log n)Each level of recursion does O(n) reversal work over log n levels.O(log n)Recursion stack only; no extra array.Split the array, arrange each half recursively, then merge. After both halves are arranged the middle looks like [L-neg][L-pos][R-neg][R-pos]. Swap the two middle blocks by reversing [L-pos][R-neg] and then reversing each block back. This is the same double reversal used to rotate an array, and it keeps the order.
- Recurse on arr[lo..mid] and arr[mid+1..hi].
- Find i = first non-negative in the left half and j = last negative in the right half.
- Reverse arr[i..j], then reverse each of the two sub-blocks back into order.
class Solution {
public void rearrange(int[] arr) {
arrange(arr, 0, arr.length - 1);
}
private void arrange(int[] a, int lo, int hi) {
if (lo >= hi) return;
int mid = (lo + hi) >>> 1;
arrange(a, lo, mid);
arrange(a, mid + 1, hi);
int i = lo;
while (i <= mid && a[i] < 0) i++; // first positive on the left
int j = mid + 1;
while (j <= hi && a[j] < 0) j++; // one past the last negative on the right
j--;
if (i > mid || j < mid + 1) return; // nothing to swap
reverse(a, i, mid);
reverse(a, mid + 1, j);
reverse(a, i, j);
}
private void reverse(int[] a, int i, int j) {
while (i < j) { int t = a[i]; a[i] = a[j]; a[j] = t; i++; j--; }
}
}class Solution:
def rearrange(self, arr: List[int]) -> None:
self.arrange(arr, 0, len(arr) - 1)
def arrange(self, a: List[int], lo: int, hi: int) -> None:
if lo >= hi:
return
mid = (lo + hi) >> 1
self.arrange(a, lo, mid)
self.arrange(a, mid + 1, hi)
i = lo
while i <= mid and a[i] < 0: # first positive on the left
i += 1
j = mid + 1
while j <= hi and a[j] < 0: # one past the last negative on the right
j += 1
j -= 1
if i > mid or j < mid + 1: # nothing to swap
return
self.reverse(a, i, mid)
self.reverse(a, mid + 1, j)
self.reverse(a, i, j)
def reverse(self, a: List[int], i: int, j: int) -> None:
while i < j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1class Solution {
public:
void rearrange(vector<int>& arr) {
arrange(arr, 0, (int) arr.size() - 1);
}
private:
void arrange(vector<int>& a, int lo, int hi) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
arrange(a, lo, mid);
arrange(a, mid + 1, hi);
int i = lo;
while (i <= mid && a[i] < 0) i++; // first positive on the left
int j = mid + 1;
while (j <= hi && a[j] < 0) j++; // one past the last negative on the right
j--;
if (i > mid || j < mid + 1) return; // nothing to swap
reverse(a, i, mid);
reverse(a, mid + 1, j);
reverse(a, i, j);
}
void reverse(vector<int>& a, int i, int j) {
while (i < j) { int t = a[i]; a[i] = a[j]; a[j] = t; i++; j--; }
}
};function rearrange(arr) {
arrange(arr, 0, arr.length - 1);
}
function arrange(a, lo, hi) {
if (lo >= hi) return;
const mid = (lo + hi) >>> 1;
arrange(a, lo, mid);
arrange(a, mid + 1, hi);
let i = lo;
while (i <= mid && a[i] < 0) i++; // first positive on the left
let j = mid + 1;
while (j <= hi && a[j] < 0) j++; // one past the last negative on the right
j--;
if (i > mid || j < mid + 1) return; // nothing to swap
reverse(a, i, mid);
reverse(a, mid + 1, j);
reverse(a, i, j);
}
function reverse(a, i, j) {
while (i < j) { const t = a[i]; a[i] = a[j]; a[j] = t; i++; j--; }
}Edge cases to test
- All negative or all positive
- Zeros mixed in
Hints
Hint 1
A plain partition breaks the order. A merge step can keep it: if both halves are already arranged, how do you combine them?
FAQ
What is the best time complexity for Arranging the array?
In place (merge sort style with rotation) runs in O(n log n) time and O(log n) extra space. Each level of recursion does O(n) reversal work over log n levels.
Which pattern does Arranging the array use?
It is a arrays & hashing problem that uses the merge sort like approach pattern. Other problems with the same pattern: Count Inversions, Reverse Pairs, Sort an Array.
Is there a brute force solution for Arranging the array?
Yes. Simple (extra array, stable) takes O(n) time and O(n) space. Copy all negatives in order, then all non-negatives in order, into a new array and copy back.
Which edge cases should I test for Arranging the array?
All negative or all positive; Zeros mixed in.