AlgoViz
HomeArrays & Hashing

Rearrange array elements by sign

Medium

Two write pointers, even and odd slots

Problem

Given an integer array nums of even length consisting of an equal number of positive and negative integers.Return the answer array in such a way that the given conditions are met: 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.

In simple words

Drop positives into even slots and negatives into odd slots so signs alternate.

The idea

With equal counts of positives and negatives, positives belong at indices 0, 2, 4… and negatives at 1, 3, 5…. Keep one write index for each parity and place each element as you meet it, which preserves relative order in a single pass.

The trick

  • Two independent write pointers stepping by 2 from 0 and 1.
  • O(n) time and O(n) space for the result array.
  • The unequal-count variant needs the leftovers appended at the end.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

2
4
5
-1
-3
-4
0
1
2
3
4
5

Step 1 of 2. Here's the example — nums = [2, 4, 5, -1, -3, -4] Values: 2, 4, 5, -1, -3, -4.

1/2
Optimal
timeO(n)spaceO(n)
1res = new array of size n2pos = 0, neg = 1             // even slots positive, odd slots negative3for x in nums:4  if x > 0: res[pos] = x; pos += 25  else:     res[neg] = x; neg += 26return res

Input

array
[2, 4, 5, -1, -3, -4]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [3, 1, -2, -5, 2, -4]
Output:
[3, -2, 1, -5, 2, -4]
Explanation:
Positives and negatives alternate, starting positive.

Example 2

Input:
nums = [-1, 1]
Output:
[1, -1]
Explanation:
One of each → [1,-1].

Example 3

Input:
nums = [1, 2, -1, -2]
Output:
[1, -1, 2, -2]
Explanation:
Weave them: 1,-1,2,-2.

Constraints

  • 2 <= nums.length <= 10^5
  • 1 <= | nums[i] | <= 10^4
  • nums.length is an even number.
  • Number of positive and negative numbers are equal.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.