Arranging the array

Medium Arrays & Hashing Merge Sort Like Approach Original on GeeksforGeeks

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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(n)
SpaceO(n)

Copy all negatives in order, then all non-negatives in order, into a new array and copy back.

  1. First pass: collect negatives.
  2. Second pass: collect non-negatives.
  3. 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);
    }
}

2In place (merge sort style with rotation)

TimeO(n log n)Each level of recursion does O(n) reversal work over log n levels.
SpaceO(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.

  1. Recurse on arr[lo..mid] and arr[mid+1..hi].
  2. Find i = first non-negative in the left half and j = last negative in the right half.
  3. 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--; }
    }
}

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.