Move all the negative elements to one side of the array

Problem Statement

Given an array of positive and negative integers, move all negative elements to one side of the array (either left or right) without maintaining the relative order. The order of elements doesn't matter.

Example:

• Input: [-1, 2, -3, 4, 5, 6, -7, 8, 9]
• Output: [-1, -3, -7, 4, 5, 6, 2, 8, 9] (all negatives on left)
• Note: Any arrangement with negatives on one side is valid

Approach 1: Using Extra Space (Brute Force)

Intuition

Create two separate arrays for positive and negative numbers, then merge them back.

Algorithm

1. Create two temporary arrays
2. Traverse original array, put negatives in one, positives in another
3. Copy negative array followed by positive array back to original

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public void moveNegatives(int[] arr) {
        List<Integer> negatives = new ArrayList<>();
        List<Integer> positives = new ArrayList<>();
        
        for (int num : arr) {
            if (num < 0) {
                negatives.add(num);
            } else {
                positives.add(num);
            }
        }
        
        int index = 0;
        for (int num : negatives) {
            arr[index++] = num;
        }
        for (int num : positives) {
            arr[index++] = num;
        }
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass to separate, another to merge
• Space Complexity: O(n) - Extra arrays to store elements

Approach 2: Two Pointer Technique (Optimal)

Intuition

Use two pointers from both ends. If left pointer finds positive and right finds negative, swap them. This is similar to the partition step in QuickSort.

Algorithm

1. Initialize left = 0, right = n-1
2. Move left forward while it points to negative
3. Move right backward while it points to positive
4. If left < right, swap and continue

public class Solution {
    public void moveNegatives(int[] arr) {
        int left = 0, right = arr.length - 1;
        
        while (left <= right) {
            // Move left pointer if it's already pointing to negative
            if (arr[left] < 0) {
                left++;
            }
            // Move right pointer if it's already pointing to positive
            else if (arr[right] >= 0) {
                right--;
            }
            // Left is positive, right is negative - swap them
            else {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
        }
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n) - Each element is visited at most once
• Space Complexity: O(1) - Only two pointer variables

Approach 3: Partition Method (Like QuickSort)

Intuition

Similar to partitioning in QuickSort, use a single pointer j to track the boundary where negatives end.

Algorithm

1. Initialize j = 0 (boundary for negatives)
2. Traverse array with index i
3. If arr[i] is negative, swap with arr[j] and increment j

public class Solution {
    public void moveNegatives(int[] arr) {
        int j = 0; // Boundary for negative elements
        
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < 0) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                j++;
            }
        }
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass through the array
• Space Complexity: O(1) - Only one extra variable

Variant: Maintaining Relative Order

If you need to maintain the relative order of elements, use a modified approach:

Note: This stable version has O(n²) time complexity due to shifting.

Key Takeaways

1. Two-pointer technique is ideal for partitioning problems
2. The problem is a variation of partitioning used in QuickSort
3. Without order requirement, O(n) time and O(1) space is achievable
4. If relative order must be maintained, it becomes harder (O(n²) with O(1) space or O(n) with O(n) space)
5. Zero is typically considered positive in these problems (can be clarified in interview)