Move Negative Numbers to Beginning in Java
Problem
Moving negative numbers to the beginning means partitioning the array so every negative value sits before every non-negative value, without necessarily preserving the original order of the untouched elements.
Given an array of integers, rearrange it in place so every negative number appears before every non-negative number.
Java Program
import java.util.Arrays;
public class MoveNegativesToBeginning {
public static void main(String[] args) {
int[] arr = {8, -3, 12, -7, 5, -1, 9};
int left = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) { // swap this negative into the next open front slot
int temp = arr[left];
arr[left] = arr[i];
arr[i] = temp;
left++;
}
}
System.out.println(Arrays.toString(arr));
}
}Output
Core Logic
Swapping each negative value into the next open slot at the front, as it's found while scanning left to right, partitions the array in a single in-place pass.
- 1
lefttracks the next open slot for a negative value, starting at0. - 2The loop visits every index
i; wheneverarr[i]is negative, it's swapped witharr[left]. - 3After each swap,
leftadvances to the next slot. - 4By the end of the scan, every negative value has been swapped into one of the first
leftpositions.
[8, -3, 12, -7, 5, -1, 9], the negatives -3, -7, and -1 end up swapped into the first three slots, in the order they were found.Key Point: The negatives keep their original relative order, since each one is swapped forward as soon as it's found — but the positives don't: 12 ends up after 5 in the result, even though it appeared before 5 in the original array, because a swap displaced it.
Why: Each element is visited once, and negatives are swapped into place using the left boundary pointer — no extra array is allocated.
Key Concepts
Approach 2: Extra Array (Stable Order)
import java.util.Arrays;
public class MoveNegativesToBeginningStable {
public static void main(String[] args) {
int[] arr = {8, -3, 12, -7, 5, -1, 9};
int[] result = new int[arr.length];
int index = 0;
for (int num : arr) {
if (num < 0) result[index++] = num; // first pass: collect negatives in order
}
for (int num : arr) {
if (num >= 0) result[index++] = num; // second pass: append positives in order
}
System.out.println(Arrays.toString(result));
}
}
Output
Core Logic
Collecting the negatives and positives into a fresh array in two separate passes keeps both groups in their original relative order — something the in-place swap can't guarantee for the untouched elements.
- 1A new array
resultthe same size asarris created, along with anindexcounter starting at0. - 2The first pass walks
arrand copies every negative value intoresult, in the order encountered. - 3The second pass walks
arragain and copies every non-negative value intoresult, continuing from wherever the first pass left off. - 4Because each pass preserves the scan order of its own group, both the negatives and the positives keep their original relative order in the result.
[8, -3, 12, -7, 5, -1, 9], the first pass collects [-3, -7, -1], and the second pass appends [8, 12, 5, 9] — unlike the swap version, 12 still comes before 5 here.Key Point: This trades the in-place version's O(1) extra space for a guarantee the swap technique doesn't make: both groups keep their exact original order, not just the negatives.
Why: Two separate passes each visit every element once, and the result array holds a full copy of the original — but both groups keep their original relative order, something the in-place swap technique doesn't guarantee for the untouched elements.
Key Concepts
Approach 3: Java 8
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class MoveNegativesToBeginningStream {
public static void main(String[] args) {
int[] arr = {8, -3, 12, -7, 5, -1, 9};
// Splits into two groups, each keeping its original relative order
Map<Boolean, List<Integer>> partitions = Arrays.stream(arr)
.boxed()
.collect(Collectors.partitioningBy(n -> n < 0));
int[] result = Stream.concat(partitions.get(true).stream(), partitions.get(false).stream())
.mapToInt(Integer::intValue)
.toArray();
System.out.println(Arrays.toString(result));
}
}
Output
Core Logic
Partitioning the stream into two groups — negative and non-negative — with a single declarative collector reproduces the same stable-order split as the manual two-pass version, without writing the two passes by hand.
- 1
Arrays.stream(arr).boxed()turns the array into aStream<Integer>. - 2
.collect(Collectors.partitioningBy(n -> n < 0))splits it into aMap<Boolean, List<Integer>>— every negative undertrue, every non-negative underfalse— with each list keeping its original relative order. - 3
Stream.concat(partitions.get(true).stream(), partitions.get(false).stream())joins the negatives followed by the positives into one combined stream. - 4
.mapToInt(Integer::intValue).toArray()unboxes that combined stream back into a plainint[].
[8, -3, 12, -7, 5, -1, 9] gives true -> [-3, -7, -1] and false -> [8, 12, 5, 9]; concatenating them gives [-3, -7, -1, 8, 12, 5, 9], the same stable order the Extra Array approach produces.Key Point: partitioningBy() is the standard-library tool for exactly this 'split into two groups' shape — it expresses the same stable partition as the manual two-pass version in one declarative call, at the cost of building two intermediate lists instead of writing directly into a result array.
Why: partitioningBy() visits every element once, building two lists whose combined size is n, before mapToInt() converts the concatenated result back into an array.