Explorer
Data Structures & Algorithms

Alternating rearrangement of positive and negative numbers preserving order.

Problem Statement

You are given a 0-indexed integer array `nums` of even length consisting of an equal number of positive and negative integers. Rearrange the elements of `nums` such that: 1. Every consecutive pair of integers have opposite signs. 2. For all integers of the same sign, the order in which they were present in `nums` is preserved. 3. The rearranged array begins with a positive integer. Return the modified array.

Examples

Input: nums = [3, 1, -2, -5, 2, -4]

Output: [3, -2, 1, -5, 2, -4]

Explanation: Combining the input according to Rearrange array elements by sign logic yields [3, -2, 1, -5, 2, -4].

Input: nums = [-1, 1]

Output: [1, -1]

Explanation: Combining the input according to Rearrange array elements by sign logic yields [1, -1].

Complexity

Time Complexity: O(N)

Space Complexity: O(N)

Hints

šŸ’” Hint 1: The array has equal numbers of positive and negative integers. šŸ’” Hint 2: Positive numbers must occupy even indices (0, 2, 4...) and negative numbers odd indices (1, 3, 5...). šŸ’” Hint 3: Use two index pointers: posIndex = 0 and negIndex = 1, advancing each by +2 when a corresponding number is placed.

Editorial & Approach

Problem Overview & Intuition

Since positive elements belong at even positions (0, 2, 4, ...) and negative elements at odd positions (1, 3, 5, ...), we can place each element directly into an output array of size N in one pass using two index pointers.

Step-by-Step Approach

  1. Allocate result = new Array(nums.length).
  2. Initialize posIndex = 0 and negIndex = 1.
  3. Iterate through num in nums:
  4. If num > 0, set result[posIndex] = num, then posIndex += 2.
  5. If num < 0, set result[negIndex] = num, then negIndex += 2.
  6. Return result.

Optimal Implementation (JavaScript)

function rearrangeArray(nums) {
  const result = new Array(nums.length);
  let posIndex = 0, negIndex = 1;
  for (let num of nums) {
    if (num > 0) {
      result[posIndex] = num;
      posIndex += 2;
    } else {
      result[negIndex] = num;
      negIndex += 2;
    }
  }
  return result;
}

Complexity Analysis

Time Complexity O(N) ā€” single pass to position every element.
Space Complexity O(N) ā€” for the output array.

Edge Cases & Corner Traps Handled

  • Array of size 2: [pos, neg] or [neg, pos].
  • Large alternating numbers.

Rearrange array elements by sign

Medium
You are given a 0-indexed integer array `nums` of even length consisting of an equal number of positive and negative integers. Rearrange the elements of `nums` such that: 1. Every consecutive pair of integers have opposite signs. 2. For all integers of the same sign, the order in which they were present in `nums` is preserved. 3. The rearranged array begins with a positive integer. Return the modified array.
Example Scenarios
1Example 1
Input: nums = [3, 1, -2, -5, 2, -4]
Output: [3, -2, 1, -5, 2, -4]
Explanation:

Combining the input according to Rearrange array elements by sign logic yields [3, -2, 1, -5, 2, -4].

2Example 2
Input: nums = [-1, 1]
Output: [1, -1]
Explanation:

Combining the input according to Rearrange array elements by sign logic yields [1, -1].

Editor
Loading Editor...
nums =
[3, 1, -2, -5, 2, -4]
Output:Click "Run" above to execute and verify your code here.
[3,-2,1,-5,2,-4]