Rearrange Array Elements

December 21, 2023

medium

Problem #

Given an array of integers, rearrange the elements such that all negative numbers appear before all positive numbers. The original relative order of elements must be preserved.

Solution 1 #

def rearrange_negatives_first(arr):
    """
    Rearrange the array so that all negative numbers appear before all positive numbers.
    The original relative order of the elements is preserved.
    """
    # Separate negative and positive numbers while preserving their order
    negative_nums = [x for x in arr if x < 0]
    positive_nums = [x for x in arr if x >= 0]

    # Combine the separated lists
    return negative_nums + positive_nums

# Example usage
arr = [1, -3, 5, -2, 4, -6, 7, -9]
rearranged_array = rearrange_negatives_first(arr)
print(rearranged_array)

This code works as follows:

The rearrange_negatives_first function takes an array arr as input.
It uses list comprehensions to create two lists: negative_nums for the negative elements and positive_nums for the non-negative elements of the array.
These lists are then concatenated, with the list of negative numbers first, and returned as the result.
The example at the end demonstrates how the function works with a specific array. The output will be the rearranged array with all negative numbers placed before the positive numbers.

Solution 2 #

Here’s the improved and more efficient Python code for rearranging an array so that all negative numbers appear before all positive numbers, while preserving the original relative order:

def rearrange_negatives_first_optimized(arr):
    """
    Rearrange the array so that all negative numbers appear before all positive numbers.
    The original relative order of the elements is preserved.
    This function is optimized to use less space.
    """
    # Pointer for the position to insert the next negative number
    next_neg_index = 0

    for i in range(len(arr)):
        if arr[i] < 0:
            # If a negative number is found, it is swapped to the next negative index position
            arr[i], arr[next_neg_index] = arr[next_neg_index], arr[i]
            next_neg_index += 1

    return arr

# Example usage
arr = [1, -3, 5, -2, 4, -6, 7, -9]
rearranged_array = rearrange_negatives_first_optimized(arr)
print(rearranged_array)

In this optimized version, the algorithm uses a single pass through the array, making it more efficient, especially for larger arrays. It swaps negative numbers to the front of the array as it encounters them, thus avoiding the need for additional space for separate lists. The original relative order of both negative and positive numbers is preserved.

Solution 2 Analysis: Step by Step #

The algorithm used in the provided code is a variation of the two-pointer technique. This technique is commonly employed in array manipulation problems, especially when rearranging or partitioning elements based on certain conditions. Here’s how it’s applied in this context:

Two-Pointer Concept: In essence, the algorithm uses a single pointer (next_neg_index) that acts as a marker for the position where the next negative number should be placed.
Single Pass Through the Array: The function iterates through the array once. During this iteration, it checks each element to determine if it is negative.
Swapping Elements: When a negative number is encountered, it is swapped with the element at the position indicated by next_neg_index. This ensures that negative numbers are moved to the front of the array.
Incrementing the Pointer: After a swap, the pointer (next_neg_index) is incremented. This step is crucial as it marks the new insertion point for the next negative number, thereby preserving the order of the negative numbers as they originally appeared.
Maintaining Relative Order: The algorithm maintains the relative order of the negative numbers and the positive numbers. Negative numbers are moved to the front in the same order they appeared, and positive numbers remain in their original order after all negative numbers.
Efficiency and Simplicity: This approach is efficient because it only requires a single traversal of the array and does not need additional data structures. The space complexity is O(1), as it rearranges the array in place.

In summary, the algorithm efficiently partitions the array into negative and non-negative numbers while maintaining their original relative order, using a single-pointer technique and in-place swaps.