Start practising

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, 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.

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 Java code.

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.
Java
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.
Java
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.

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.