Python - Move All Negative Elements to One Side of an Array

Python – Move All Negative Elements to One Side of an Array

This tutorial explains how to rearrange an array so that all negative elements are moved to one side. This is a common question in data structures and algorithms (DSA) interviews. We’ll discuss the problem statement, sample inputs/outputs, solution steps, and provide Python programs using different methods to achieve the result.

Problem Statement

Given an array of integers, rearrange the elements so that all negative numbers appear on one side of the array (either left or right). The order of the elements does not need to be maintained.

Sample Input and Output

Example 1:

</>

Copy

# Sample Input
arr = [-3, 1, -2, 4, 5, -6]

# One possible Output (negatives on the left)
# Note: The order of negatives or non-negatives may vary.
Output: [-3, -2, -6, 4, 5, 1]

Example 2:

</>

Copy

# Sample Input
arr = [2, -1, 0, -3, 4, -5]

# One possible Output (negatives on the left)
Output: [-1, -3, -5, 2, 0, 4]

Solution Approach

There are several ways to solve this problem. Here are two common methods:

Two-Pointer Approach:

This in-place method uses two pointers—one starting from the beginning and the other from the end—to swap elements. When the left pointer finds a non-negative number and the right pointer finds a negative number, they are swapped. This process continues until the pointers meet.
List Comprehension Method:

This method creates two new lists: one for negative elements and one for non-negative elements, and then concatenates them. While simple, this method uses extra memory for the new lists.

Python Program

Method 1: Using the Two-Pointer Approach

</>

Copy

# Function to move all negative elements to the left side using two-pointer approach
def move_negatives_two_pointer(arr):
    left, right = 0, len(arr) - 1
    while left <= right:
        # If the left element is negative, move the pointer to the right
        if arr[left] < 0:
            left += 1
        # If the right element is non-negative, move the pointer to the left
        elif arr[right] >= 0:
            right -= 1
        else:
            # Swap the elements
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1
    return arr

# Testing Method 1
arr1 = [-3, 1, -2, 4, 5, -6]
print("Rearranged Array (Two-Pointer):", move_negatives_two_pointer(arr1.copy()))

Output:

Rearranged Array (Two-Pointer): [-3, -6, -2, 4, 5, 1]

This method rearranges the array in-place without using extra memory.

Method 2: Using List Comprehension

</>

Copy

# Function to move all negative elements to the left using list comprehension
def move_negatives_list_comprehension(arr):
    negatives = [x for x in arr if x < 0]
    non_negatives = [x for x in arr if x >= 0]
    return negatives + non_negatives

# Testing Method 2
arr2 = [2, -1, 0, -3, 4, -5]
print("Rearranged Array (List Comprehension):", move_negatives_list_comprehension(arr2))

Output:

Rearranged Array (List Comprehension): [-1, -3, -5, 2, 0, 4]

While the list comprehension method is straightforward and easy to understand, it creates new lists rather than modifying the original array.

Conclusion

In this tutorial, we explored two methods to move all negative elements to one side of an array:

Two-Pointer Approach: An in-place solution that uses two pointers to swap elements, ideal for optimizing space.
List Comprehension: A simple method that separates negatives and non-negatives into two lists and then concatenates them, but uses extra space.

Choose the method that best fits your needs based on space complexity and simplicity. The two-pointer approach is often preferred in interviews for its in-place operation and efficiency.

TutorialKart

Python – Move All Negative Elements to One Side of an Array