Move all the negative elements to one side of the array

The problem of move all the negative elements to one side of the array is a common programming task known as partitioning or segregating elements. In this specific case, the goal is to rearrange the elements in such a way. That all the negative numbers appear before (or to the left of) any positive or non-negative numbers in the array.

The task can be seen as a sorting problem. Where the only requirement is to separate the elements based on their negativity rather than sorting them in ascending or descending order. By moving the negative elements to one side, we create a partition in the array that divides the negative and non-negative numbers.

Example for Move all the negative elements to one side of the array

Let’s break down the solution:

The moveNegativeElements method takes an integer array arr as input.
We initialize two pointers, left and right, with the start and end indices of the array, respectively.
We enter a while loop that continues until the left pointer is less than or equal to the right pointer.
Inside the loop, we search for the first positive element from the left side of the array. We increment the left pointer until we find a positive element or until left becomes greater than right.
Similarly, we search for the first negative element from the right side of the array. We decrement the right pointer until we find a negative element or until left becomes greater than right.
If the left pointer is still less than or equal to the right pointer, it means we have found a positive element on the left side and a negative element on the right side that need to be swapped.
We swap the positive and negative elements using a temporary variable, increment the left pointer, and decrement the right pointer.
The process continues until the left pointer becomes greater than the right pointer, indicating that all negative elements have been moved to one side of the array.
In the main method, we create an example array arr and print its original state.
We then call the moveNegativeElements method, passing the array as an argument, to rearrange the negative elements.
Finally, we print the modified array to verify the result.


import java.util.Arrays;

public class NegativeElements {

    public static void moveNegativeElements(int[] arr) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            // Find the first positive element from the left
            while (left <= right && arr[left] < 0) {
                left++;
            }
            // Find the first negative element from the right
            while (left <= right && arr[right] >= 0) {
                right--;
            }

            if (left <= right) {
                // Swap the positive and negative elements
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = { -2, 3, -5, -1, 7, 8, -6 };
        System.out.println("Original array: " + Arrays.toString(arr));

        moveNegativeElements(arr);

        System.out.println("Array after moving negative elements: " + Arrays.toString(arr));
    }
}

When you run the code, the output will be:


Original array: [-2, 3, -5, -1, 7, 8, -6]
Array after moving negative elements: [-2, -6, -5, -1, 7, 8, 3]

The time complexity of the provided example for moving negative elements to one side of the array is O(n), where n is the size of the array. This is because the solution involves a single pass through the array using two pointers.

The space complexity of the example is O(1) since it uses only a constant amount of additional space, regardless of the size of the input array. The solution modifies the array in-place without requiring any additional data structures or dynamically allocating memory. Therefore, the space complexity remains constant.

I hope this example helps you understand how to efficiently move negative elements in an array using Java.