DEV Community

Sri Mahalakshmi
Sri Mahalakshmi

Posted on

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

#algorithms #tutorial #beginners #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
Enter fullscreen mode Exit fullscreen mode

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

        for i in range(len(arr)):
Enter fullscreen mode Exit fullscreen mode

Loop through the array using index i.

            if arr[i] >= 0:
Enter fullscreen mode Exit fullscreen mode

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

                temp = arr[i]
Enter fullscreen mode Exit fullscreen mode

Store the positive element temporarily.

                j = i
Enter fullscreen mode Exit fullscreen mode

Start shifting from current position.

                while j > pos_index:
                    arr[j] = arr[j - 1]
                    j -= 1
Enter fullscreen mode Exit fullscreen mode

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

                arr[pos_index] = temp
Enter fullscreen mode Exit fullscreen mode

Place the positive element at the correct position.

                pos_index += 1
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Step-by-Step Example

Input:

[1, -1, 3, 2, -7, -5, 11, 6]
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)