We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Rearrange Array Elements by Sign

Number: 2271

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Bloomberg, Meta, Adobe, Uber, Apple, Microsoft

Problem Description

Given an even-length array that contains an equal number of positive and negative integers, rearrange the array such that:

  1. Every consecutive pair of integers have opposite signs.
  2. The order of appearance for the positive numbers and negative numbers is preserved.
  3. The rearranged array starts with a positive integer.

Key Insights

  • The order of positive and negative integers must remain as in the original array.
  • Since the array length is even and contains equal numbers of positive and negative numbers, split the array into two separate lists.
  • Use a two-pointer or merge-like approach to alternate between the two lists.
  • No in-place modifications are required.

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in the array (we traverse the array a few times). Space Complexity: O(n) extra space for storing separate lists for positive and negative integers.

Solution

We solve the problem by first iterating through the original array to segregate positives and negatives into two lists. Since their order must be preserved, we simply append them. Then, we iterate through both lists concurrently, alternating the positive and negative integers to form the final output array. This approach guarantees that every two consecutive numbers have opposite signs and respects the order constraints.

Code Solutions

# Function to rearrange array elements by sign
def rearrangeArray(nums):
    # Separate positive and negative integers
    positives = [num for num in nums if num > 0]
    negatives = [num for num in nums if num < 0]
    
    # Initialize the result array
    result = []
    # Merge the two lists, alternating elements
    for i in range(len(positives)):
        # Append one positive number
        result.append(positives[i])
        # Append one negative number
        result.append(negatives[i])
    return result

# Example usage:
if __name__ == "__main__":
    nums = [3,1,-2,-5,2,-4]
    print(rearrangeArray(nums))  # Expected output: [3, -2, 1, -5, 2, -4]
← Back to All Questions