This article focuses on the algorithm to move the negative elements of an array to the front. This is a basic problem of rearranging elements in an array. This can be solved by many approaches, this article will explore the two-pointer approach.

Table of content:

1. Problem statement
2. Idea, Steps to solve it (with step by step example)
3. Time and Space Complexity
4. Implementation
5. Shortcomings
6. Applications

Problem statement

Problem statement: move the negative elements of an array to the front

Example:

Input will be:

2 -9 10 12 5 -2 10 -4

Output will be:

-9 -2 -4 2 10 12 5 10

Note:

• The order of negative elements are same.
• The order of positive elements are same.
• All negative elements have been moved to the front.
• All positive elements have been moved to the end or followed by all the negative elements.

Idea & Steps to solve it

The idea of the algorithm is to have two pointers left and right.

All the elements before left should be negative and all elements after right should be positive. This way if any elements are at their wrong positions swaps can occur to correct it.

Steps:

1. Initialize left pointer to 0 and right pointer to size(nums)-1
2. check if both left and right elements are negative, increment left pointer if true
3. check if left element is positive and right element is negative then swap the elements, increment left and decrement right
4. check if both left and right elements are positive, decrement right pointer if true
5. otherwise, increment left and decrement right pointers
6. repeat 2-5 until left pointer <= right pointer

algo rearrange(nums):
    left = 0
    right = size(nums)-1
    while left < right:
       compare the nums[left] and nums[right]:
           if both are negative:
               left = left + 1
           else if the left element is positive and the right element is negative:
               swap the elements
               left = left + 1
               right = right - 1
           else if both are positive:
               right = right - 1
           else:
               left = left + 1
               right = right - 1

Consider this example that illustrates all possible cases,

    nums: -2 -1 2 4 5 -3 5
           ^             ^
           |             |
          left        right  

    nums[left] < 0 nums[right] > 0 => left++ right--

    nums: -2 -1 2 4 5 -3 5
              ^        ^
              |        |
             left    right  

    nums[left] < 0 nums[right] < 0 => left++

    nums: -2 -1 2 4 5 -3 5
                ^      ^
                |      |
              left    right  

    nums[left] > 0 nums[right] < 0 => swap

    nums: -2 -1 -3 4 5 2 5
                   ^ ^
                   | |
                left right  
    
    nums[left] > 0 nums[right] > 0 => left++ right--

    nums: -2 -1 -3 4 5 2 5
                   ^ ^
                   | |
               right left
    
    
    left <= right is true => break loop

Time and Space Complexity

For this particular algorithm the number of comparison operations done will always be Θ(N/2). Thus we consider swaps as the basic operation and compare complexity based on this factor

• Worst case time complexity: Θ(k), where k is the number of negative elements
  • This occurs when all negative elements occur after the positive elements. All negative elements need to be swapped over to the front of the array.
• Average case time complexity: O(N/2)
  • On average, by probabilistic analysis, about N/2 negative numbers lie to the right of left pointer and need to be swapped over.
• Best case time complexity: Θ(1)
  • This occurs when the elements are already in the correct order and do not require any rearranging.
• Space complexity: Θ(1)

Implementation

void rearrange(vector<int> &nums) {
    int left = 0;
    int right = nums.size() - 1;
    while(left < right) {
        int left_ele = nums[left];
        int right_ele = nums[right];
        if(left_ele < 0 && right_ele < 0) {
            left += 1;
        } else if(left_ele > 0 && right_ele < 0) {
            // out of order
            nums[left] = right_ele;
            nums[right] = left_ele;
        } else if(left_ele > 0 && right_ele > 0) {
            right -= 1;
        } else {
            left += 1;
            right -= 1;
        }
    }
}

int main() {
    vector<int> nums = {4, 2, -5, 8, -2, 10, -7};
    rearrange(nums);
    for(auto ele: nums) {
        cout << ele << " ";
    }
    cout << "\n";
}

Output:

-7 -2 -5 8 2 10 4

Shortcomings

• Since 0 is neither a negative or positive number, the algorithm fails to place it at the right spot and it may land either in the negative or positive halves

Applications

• Preferred instead of sorts when only the relative ordering of positive and negative elements is required as opposed to ordering of each element

With this article at OpenGenus, you must have a strong idea of how to Move negative elements to front of array.