How to Move All Negative Numbers to the Beginning of an Array in Java
Moving all negative numbers to the beginning of an array is a classic array partitioning problem that frequently appears in coding interviews. Unlike the "move zeros" problems, this question introduces an important design decision: Should the relative order of elements be preserved?
If order preservation is required, you'll need an additional array. If order doesn't matter, an efficient in-place two-pointer technique can solve the problem using constant extra space.
In this tutorial, you'll learn both approaches, understand their trade-offs, and discover when each solution should be used.
Problem Statement
Given the following array:
int[] numbers = {1, -2, 3, -4, -5, 6};Move all negative numbers to the beginning.
Order-Preserving Output
[-2, -4, -5, 1, 3, 6]Non-Order-Preserving Output
[-5, -2, -4, 1, 3, 6]Both outputs are correct depending on the problem requirements.
Order Preservation: A Key Design Decision
Before writing any code, determine whether the original order of the elements must remain unchanged.
For example:
Original
[1, -2, 3, -4, -5, 6]If order is preserved:
[-2, -4, -5, 1, 3, 6]Notice that:
- Negative numbers remain in the same order.
- Positive numbers also remain in the same order.
If order is not required:
[-5, -2, -4, 3, 1, 6]The partition is still correct, but the original ordering changes.
Always clarify this requirement before choosing an algorithm.
Method 1: Order-Preserving (Using an Extra Array)
This approach creates another array and copies all negative numbers first, followed by all non-negative numbers.
Example
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] numbers = {1, -2, 3, -4, -5, 6};
int[] result = new int[numbers.length];
int index = 0;
for (int num : numbers) {
if (num < 0) {
result[index++] = num;
}
}
for (int num : numbers) {
if (num >= 0) {
result[index++] = num;
}
}
System.out.println(Arrays.toString(result));
}
}Output
[-2, -4, -5, 1, 3, 6]Explanation
The algorithm performs two passes:
- Copy every negative number.
- Copy every non-negative number.
Since elements are copied in their original order, the relative order is preserved.
Time Complexity: O(n)
Space Complexity: O(n)
Method 2: Non-Order-Preserving In-Place Technique (Optimal)
When preserving order is not required, the two-pointer technique provides the optimal solution.
Example
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] numbers = {1, -2, 3, -4, -5, 6};
int left = 0;
int right = numbers.length - 1;
while (left <= right) {
if (numbers[left] < 0) {
left++;
} else if (numbers[right] >= 0) {
right--;
} else {
int temp = numbers[left];
numbers[left] = numbers[right];
numbers[right] = temp;
left++;
right--;
}
}
System.out.println(Arrays.toString(numbers));
}
}Output
[-5, -2, -4, 3, 1, 6](Your output may vary because the order of elements is not preserved.)
Explanation
Two pointers move toward each other.
- The left pointer searches for a misplaced positive number.
- The right pointer searches for a misplaced negative number.
- When both are found, they are swapped.
This partitions the array without creating another array.
Time Complexity: O(n)
Space Complexity: O(1)
Step-by-Step Explanation
Consider:
[1, -2, 3, -4, -5, 6]Initially:
left = 0
right = 5Step 1
left = 0 → 1
right = 5 → 6Since 6 is already non-negative:
right--Now:
right = 4Step 2
left = 0 → 1
right = 4 → -5Both values are misplaced.
Swap them.
[-5, -2, 3, -4, 1, 6]Update:
left = 1
right = 3Step 3
numbers[1] = -2Already negative.
Move left pointer.
left = 2Step 4
numbers[2] = 3
numbers[3] = -4Swap them.
[-5, -2, -4, 3, 1, 6]Pointers cross.
The algorithm stops.
Internal Working
Initial array:
[1, -2, 3, -4, -5, 6]After first swap:
[-5, -2, 3, -4, 1, 6]After second swap:
[-5, -2, -4, 3, 1, 6]Notice that:
- All negative numbers are grouped at the beginning.
- All non-negative numbers are grouped at the end.
- Their original ordering is no longer preserved.
Real-Life Analogy
Imagine two people organizing cards.
One person starts from the left.
The other starts from the right.
Whenever they find a positive card on the left and a negative card on the right, they simply exchange them.
This quickly groups all negative cards together without worrying about maintaining their original order.
Best Practices
- Clarify whether order preservation is required before choosing an algorithm.
- Use the two-pointer approach when order does not matter.
- Use an extra array when preserving order is required.
- Treat zero as non-negative unless the problem specifies otherwise.
- Test arrays containing only positive numbers or only negative numbers.
Common Mistakes
1. Assuming the Two-Pointer Technique Preserves Order
It does not.
Swapping elements changes their original order.
2. Forgetting to Clarify How Zero Should Be Treated
Most interview problems treat zero as non-negative.
Always verify the requirement.
3. Using an Extra Array When It Isn't Necessary
If order is unimportant, the in-place solution is both faster and more memory-efficient.
4. Incorrect Pointer Movement
Moving the pointers in the wrong situations may produce incorrect results or infinite loops.
Expert Tips
- The two-pointer convergence technique is very similar to the partition step used in Quick Sort.
- Many interview problems involve partitioning elements according to a condition rather than sorting them.
- If both stable ordering and O(1) extra space are required, the problem becomes significantly more difficult.
- Always explain your assumptions about ordering and the treatment of zero during interviews.
Comparison Table
| Method | Time Complexity | Space Complexity | Preserves Order? |
|---|---|---|---|
| Extra Array | O(n) | O(n) | ✅ Yes |
| Two-Pointer In-Place | O(n) | O(1) | ❌ No (Optimal for Space) |
Frequently Asked Questions
1. Does the in-place solution preserve the order of elements?
No. The two-pointer technique partitions the array efficiently but does not preserve the original order.
2. How can I preserve the order of negative numbers?
Use an extra array and copy all negative numbers first, followed by all non-negative numbers.
3. Is zero considered negative?
No. In most problems, zero is treated as a non-negative value unless stated otherwise.
4. Which algorithm is the two-pointer technique similar to?
It closely resembles the partition step used in the Quick Sort algorithm.
5. Can I preserve order and still use O(1) extra space?
Not with this straightforward approach. Stable in-place partitioning is a much more advanced problem.
6. What is the time complexity of the two-pointer solution?
The algorithm runs in O(n) time because each pointer traverses the array at most once.
7. Can I partition the array based on another condition?
Yes. Simply replace the sign checks with your own condition.
For example:
- Even vs. odd numbers
- Positive vs. non-positive numbers
- Multiples of a given value
- Prime vs. non-prime numbers
8. Is this problem commonly asked in coding interviews?
Yes. It is one of the standard array partitioning questions and is often asked alongside problems such as moving zeros, segregating even and odd numbers, and implementing Quick Sort partitioning.
