easyArray ProblemsJava

Move All Negative Numbers to the Beginning of an Array

Rearrange an array so all negative numbers come before all non-negative numbers.

Quick Answer

Keep a boundary index `j` for the next negative slot. Scan the array; each time you find a negative value, swap it into position `arr[j]` and advance `j`. When the scan ends, every index below `j` holds a negative number. This partitions the array in O(n) time and O(1) space.

Problem Statement

Given an integer array, rearrange it so that all negative numbers appear before all non-negative numbers. The order within each group does not need to be preserved. Rearrange in place.

For example, [-1, 2, -3, 4, 5, -6] can become [-1, -3, -6, 4, 5, 2]: every negative value now sits ahead of every non-negative value.

Input: An integer array arr of length n (n >= 0).

Output: The same array partitioned so negatives precede non-negatives.

Examples

Example 1
Input:  [-1, 2, -3, 4, 5, -6]
Output: [-1, -3, -6, 4, 5, 2]

The three negatives are gathered at the front by successive swaps.

Example 2
Input:  [3, -2, -1, 4]
Output: [-2, -1, 3, 4]

-2 and -1 swap to the front; 3 and 4 fall to the back.

Constraints

  • 0 <= n <= 10^6
  • Must be done in place; relative order need not be preserved

Think Before You Code

Reveal the questions to ask yourself first
  • How can one index remember where the next negative value belongs?
  • When you meet a negative value ahead of that boundary, how do you bring it back?
  • Does this version need to keep the negatives in their original order?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
Think of the front of the array as a growing region of negatives, tracked by an index `j`.
Hint 2
Whenever `arr[i]` is negative, swap it with `arr[j]` and then advance `j` by one.
Hint 3
By the end, indices 0..j-1 are all negative and the rest are non-negative — a classic partition.

Approach

Reveal the step-by-step approach

Partition with a boundary pointer, like the partition step of quicksort.

  1. Set j = 0; it marks the first slot not yet known to hold a negative.
  2. For i from 0 to n - 1: if arr[i] < 0, swap arr[i] with arr[j] and increment j.
  3. When the loop finishes, all negatives occupy indices 0 .. j - 1 and every later index is non-negative.

Each element is examined once and swaps are O(1), so the whole partition is linear.

Dry Run

Walk through the example step by step

Partitioning [-1, 2, -3, 4, 5, -6] (j starts at 0):

i | arr[i] | action              | array               | j
--+--------+---------------------+---------------------+--
0 | -1     | swap arr[0],arr[0]  | [-1, 2,-3, 4, 5,-6] | 1
1 |  2     | no swap             | [-1, 2,-3, 4, 5,-6] | 1
2 | -3     | swap arr[1],arr[2]  | [-1,-3, 2, 4, 5,-6] | 2
3 |  4     | no swap             | [-1,-3, 2, 4, 5,-6] | 2
4 |  5     | no swap             | [-1,-3, 2, 4, 5,-6] | 2
5 | -6     | swap arr[2],arr[5]  | [-1,-3,-6, 4, 5, 2] | 3

Solution

Reveal the full Java solution
import java.util.Arrays;

public class MoveNegativesToFront {
    public static void moveNegatives(int[] arr) {
        int j = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < 0) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                j++;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {-1, 2, -3, 4, 5, -6};
        moveNegatives(a);
        System.out.println(Arrays.toString(a)); // [-1, -3, -6, 4, 5, 2]

        int[] b = {3, -2, -1, 4};
        moveNegatives(b);
        System.out.println(Arrays.toString(b)); // [-2, -1, 3, 4]
    }
}

The index j is an invariant boundary: everything before it is negative. When a negative is found at i, swapping it to j extends that region by one. Since j never passes i, no negative is ever pushed back out. The trade-off is that the order inside each group may change; a stable version would need extra space.

Time: O(n)Space: O(1)

Common Mistakes

  • Treating 0 as negative; use `< 0` so zero stays in the non-negative group.
  • Advancing `j` even when no swap happens, which corrupts the boundary.

Edge Cases to Test

  • An all-negative array is returned unchanged with j reaching n.
  • An all-non-negative array is returned unchanged with j staying at 0.
  • An empty array must not throw.

Interview Follow-Ups

  • How would you preserve the original relative order of both groups?
  • How would you separate negatives, zeros, and positives into three regions?
  • How does this relate to the Dutch National Flag partitioning scheme?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us