Moving All Negative Elements to the End of an Array in Python

Problem Explanation

You are given an array arr[] containing both positive and negative integers.
Your task is to move all the negative elements to the end of the array while maintaining the order of positive elements.

Note: The operation should be done in-place, meaning no extra array should be used.

Example:

• Input: arr = [1, -1, 3, 2, -7, -5, 11, 6]
  Output: [1, 3, 2, 11, 6, -1, -7, -5]

• Input: arr = [-5, 7, -3, -4, 9, 10, -1, 11]
  Output: [7, 9, 10, 11, -5, -3, -4, -1]

Method Used: Two Pointer Technique (Stable Partition)

We use a pointer to track where the next positive number should go, and rearrange elements accordingly.

Why This Method?

• Time complexity: O(n) (single traversal)
• Space complexity: O(1) (in-place)
• Maintains order of positive elements
• Simple and efficient

Python Code with Explanation

class Solution:
    def segregateElements(self, arr):

        pos_index = 0

pos_index keeps track of where the next positive element should be placed.

        for i in range(len(arr)):

Loop through the array using index i.

            if arr[i] >= 0:

Check if the current element is positive (or zero).

                temp = arr[i]

Store the positive element temporarily.

                j = i

Start shifting from current position.

                while j > pos_index:
                    arr[j] = arr[j - 1]
                    j -= 1

Shift all elements one step to the right to make space for the positive number.

                arr[pos_index] = temp

Place the positive element at the correct position.

                pos_index += 1

Move the position forward for the next positive element.

Complete Code

class Solution:
    def segregateElements(self, arr):
        pos_index = 0

        for i in range(len(arr)):
            if arr[i] >= 0:
                temp = arr[i]
                j = i

                while j > pos_index:
                    arr[j] = arr[j - 1]
                    j -= 1

                arr[pos_index] = temp
                pos_index += 1

        return arr

Step-by-Step Example

Input:

[1, -1, 3, 2, -7, -5, 11, 6]

Step 1: Move positives forward while maintaining order
Step 2: Negatives automatically shift to the end

Output:

[1, 3, 2, 11, 6, -1, -7, -5]

Time and Space Complexity

• Time Complexity: O(n^2) (due to shifting elements)
• Space Complexity: O(1)

Key Takeaway

This approach maintains the original order of positive elements while moving negatives to the end, making it a stable in-place solution.