Rearrange Array Elements by Sign

Medium

Google

1 view

Topics:

Arrays

You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers.

You should return the array of nums such that the the array follows the given conditions:

Every consecutive pair of integers have opposite signs.
For all integers with the same sign, the order in which they were present in nums is preserved.
The rearranged array begins with a positive integer.

Return the modified array after rearranging the elements to satisfy the aforementioned conditions.

Example 1:

Input: nums = [3,1,-2,-5,2,-4] Output: [3,-2,1,-5,2,-4] Explanation: The positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4]. The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4]. Other ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.

Example 2:

Input: nums = [-1,1] Output: [1,-1] Explanation: 1 is the only positive integer and -1 the only negative integer in nums. So nums is rearranged to [1,-1].

Rearrange Array Elements by Sign

Medium

Google

1 view

Topics:

Arrays

You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers.

You should return the array of nums such that the the array follows the given conditions:

Every consecutive pair of integers have opposite signs.
For all integers with the same sign, the order in which they were present in nums is preserved.
The rearranged array begins with a positive integer.

Return the modified array after rearranging the elements to satisfy the aforementioned conditions.

Example 1:

Input: nums = [3,1,-2,-5,2,-4] Output: [3,-2,1,-5,2,-4] Explanation: The positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4]. The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4]. Other ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.

Example 2:

Input: nums = [-1,1] Output: [1,-1] Explanation: 1 is the only positive integer and -1 the only negative integer in nums. So nums is rearranged to [1,-1].

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values within the input array?
What should I return if the input array does not contain an equal number of positive and negative integers?
Are there any constraints on the space complexity of my solution?
If there are multiple possible rearrangements that satisfy the conditions, is any one of them acceptable?
Can I assume that the input array will always be non-empty?

Brute Force Solution

Approach

The basic approach to rearranging positives and negatives is to separate all the numbers into two separate groups: positives and negatives. Then, we merge these groups together in an alternating fashion.

Here's how the algorithm would work step-by-step:

First, walk through the pile of numbers and put all the positive numbers into one new pile, and all the negative numbers into another new pile.
Next, start a completely fresh pile to hold the rearranged numbers.
Now, take the first number from the positive pile and put it into the fresh pile.
Then, take the first number from the negative pile and put it into the fresh pile, right after the positive number.
Keep alternating between taking a number from the positive pile and the negative pile, and putting them into the fresh pile, until you run out of numbers in either the positive or negative pile.
If one of the piles still has numbers left over after the other one is empty, just add all the remaining numbers from that pile to the end of the fresh pile.

Code Implementation

def rearrange_array_elements(numbers):
    positive_numbers = []
    negative_numbers = []

    for number in numbers:
        if number >= 0:
            positive_numbers.append(number)
        else:
            negative_numbers.append(number)

    rearranged_numbers = []

    positive_index = 0
    negative_index = 0

    # Interleave positive and negative numbers.
    while positive_index < len(positive_numbers) and negative_index < len(negative_numbers):
        rearranged_numbers.append(positive_numbers[positive_index])
        positive_index += 1
        rearranged_numbers.append(negative_numbers[negative_index])
        negative_index += 1

    # Add any remaining positive numbers.
    while positive_index < len(positive_numbers):
        # Append remaining positive numbers
        rearranged_numbers.append(positive_numbers[positive_index])
        positive_index += 1

    # Add any remaining negative numbers.
    while negative_index < len(negative_numbers):
        # Append remaining negative numbers
        rearranged_numbers.append(negative_numbers[negative_index])
        negative_index += 1

    return rearranged_numbers

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once to separate positive and negative numbers into two separate lists. Subsequently, it iterates to merge these lists back into the original array, alternating between positive and negative numbers. The merging process involves iterating through the positive and negative lists, which in the worst case, could still sum up to n. Therefore, the overall time complexity is dominated by these linear traversals, resulting in O(n).

Space Complexity

O(N) – The algorithm creates two new piles (lists) to store positive and negative numbers separately. In the worst-case scenario, one of these lists could contain all N elements of the original array. Furthermore, a fresh pile (list) of size N is created to hold the rearranged numbers. Therefore, the algorithm uses auxiliary space proportional to the input size N, resulting in O(N) space complexity.

Optimal Solution

Approach

The goal is to rearrange numbers so that positive and negative numbers alternate. The clever idea is to separate positives and negatives first, then merge them together in the correct order. This avoids excessive swapping and comparisons.

Here's how the algorithm would work step-by-step:

First, divide the numbers into two separate groups: one containing only positive numbers, and the other containing only negative numbers.
Next, create a new sequence where we'll put the numbers in their final order.
Now, alternate picking numbers from the positive and negative groups and placing them into the new sequence.
If one group runs out of numbers before the other, simply add the remaining numbers from the longer group to the end of the new sequence.
The new sequence now contains the numbers in the desired alternating order.

Code Implementation

def rearrange_array_elements_by_sign(numbers):
    positive_numbers = []
    negative_numbers = []

    for number in numbers:
        if number > 0:
            positive_numbers.append(number)
        else:
            negative_numbers.append(number)

    rearranged_numbers = []
    positive_index = 0
    negative_index = 0

    # Alternate adding positive and negative numbers
    while positive_index < len(positive_numbers) and negative_index < len(negative_numbers):
        rearranged_numbers.append(positive_numbers[positive_index])
        positive_index += 1
        rearranged_numbers.append(negative_numbers[negative_index])
        negative_index += 1

    # Add any remaining positive numbers
    while positive_index < len(positive_numbers):
        # Add remaining positive numbers
        rearranged_numbers.append(positive_numbers[positive_index])
        positive_index += 1

    # Add any remaining negative numbers
    while negative_index < len(negative_numbers):
        # Add remaining negative numbers
        rearranged_numbers.append(negative_numbers[negative_index])
        negative_index += 1

    return rearranged_numbers

Big(O) Analysis

Time Complexity

O(n) – The algorithm involves iterating through the input array of size n once to separate positive and negative numbers into two separate lists. Then, it iterates through these lists to merge them into a new array, which takes at most n steps. Since we have two independent loops each taking O(n) time, the overall time complexity is O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The algorithm creates two separate lists to store positive and negative numbers respectively. In the worst-case scenario, where all numbers are either positive or negative, one of these lists could contain N elements, where N is the size of the input array. Additionally, a new sequence (list) is created to store the rearranged numbers, which also has a size of N. Therefore, the auxiliary space used is proportional to the size of the input array, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or throw an IllegalArgumentException, depending on requirements.
Input array with only positive or only negative numbers	Since the problem states an equal number of positive and negative numbers, this input should not occur; consider throwing an exception or returning an empty array if it does.
Input array with very large or very small integers (potential overflow)	The algorithm itself should not be directly affected by large numbers as it only cares about the sign; integer overflow isn't a direct concern with this logic, but one might consider it for memory allocation based on the magnitude of numbers.
Equal number of positive and negative numbers but no possible valid rearrangement (e.g., positive numbers all clustered together at the beginning).	A valid arrangement is always possible given the constraint of equal number of positive and negative numbers, and the problem statement necessitates that order of appearence of same sign should be retained, so this case is not possible.
Input array with an extremely large number of elements (scalability concerns).	The proposed two-pointer approach offers O(n) time complexity and O(n) space complexity for creating the rearranged array, so large n may cause memory issues.
The absolute values of the numbers might be duplicate, but not the numbers themselves (e.g., [1, -1, 2, -2, 1, -1])	The algorithm only cares about the sign of the number, duplicate absolute values don't affect the logic if we maintain relative ordering.
Handling of zero values, if zero is considered positive or negative.	Since problem requires positive number to begin with and equal number of positive and negative numbers, we assume zero is explicitly not included.
Input array already arranged according to the rules.	The algorithm should still correctly rearrange the array, resulting in the same array being returned.