DSA Tracker

Visualize

Rearrange Array Elements by Sign

Two write cursors stepping by two

time O(n)space O(n) for the output

The output shape is fixed before a single value is read: even slots must hold positives, odd slots must hold negatives. So the sign of an element already tells you which slot family it belongs to, and the only question left is which slot in that family — always the next unused one. Two cursors answer that: pos starts at 0, neg starts at 1, and each advances by 2 after a write, so they walk disjoint parities and can never overwrite each other. Scanning the input left to right and appending into the matching cursor preserves relative order automatically, because neither cursor ever moves backwards. One pass, one write per element, and no sorting.

Details

Animated on: nums = [3, 1, -2, -5, 2, -4, -1, 6] holds equal counts of positives and negatives. Rebuild it so the signs alternate starting with a positive, keeping the relative order within each sign. Answer: [3, -2, 1, -5, 2, -4, 6, -1].

Problem:Rearrange Array Elements by SignMedium

Two write cursors stepping by two

step 1 / 10

_
[0]
_
[1]
_
[2]
_
[3]
_
[4]
_
[5]
_
[6]
_
[7]

The answer has to alternate starting positive, so slot parity already decides every sign: even slots 0, 2, 4... are positive and odd slots 1, 3, 5... are negative. That means no sorting and no comparing — just two write cursors, pos=0 on the first even slot and neg=1 on the first odd slot, each jumping two at a time so it never lands on the other's parity.

  • pos=0· arr[0] = _
  • neg=1· arr[1] = _
Pseudocode
1FUNCTION rearrangeBySign(nums)
2  out <- ARRAY OF LENGTH(nums)
3  pos <- 0
4  neg <- 1
5  FOR i <- 0 TO LENGTH(nums) - 1
6    IF nums[i] > 0
7      out[pos] <- nums[i]
8      pos <- pos + 2
9    ELSE
10      out[neg] <- nums[i]
11      neg <- neg + 2
12  RETURN out

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. The answer has to alternate starting positive, so slot parity already decides every sign: even slots 0, 2, 4... are positive and odd slots 1, 3, 5... are negative. That means no sorting and no comparing — just two write cursors, pos=0 on the first even slot and neg=1 on the first odd slot, each jumping two at a time so it never lands on the other's parity.
  2. Reading the input left to right, nums[0]=3 is positive, so it takes the next free EVEN slot 0. Because the input is scanned in order and pos only ever moves forward, the positives land in exactly the order they appeared — that is what keeps the relative order intact for free. pos jumps to 2, skipping slot 1, which is reserved for a negative.
  3. Reading the input left to right, nums[1]=1 is positive, so it takes the next free EVEN slot 2. Because the input is scanned in order and pos only ever moves forward, the positives land in exactly the order they appeared — that is what keeps the relative order intact for free. pos jumps to 4, skipping slot 3, which is reserved for a negative.
  4. nums[2]=-2 is negative, so it ignores pos entirely and takes the next free ODD slot 1. The two cursors never collide because they start one apart and both step by 2, so a negative can never overwrite a positive already parked at an even index. neg jumps to 3.
  5. nums[3]=-5 is negative, so it ignores pos entirely and takes the next free ODD slot 3. The two cursors never collide because they start one apart and both step by 2, so a negative can never overwrite a positive already parked at an even index. neg jumps to 5.
  6. Reading the input left to right, nums[4]=2 is positive, so it takes the next free EVEN slot 4. Because the input is scanned in order and pos only ever moves forward, the positives land in exactly the order they appeared — that is what keeps the relative order intact for free. pos jumps to 6, skipping slot 5, which is reserved for a negative.
  7. nums[5]=-4 is negative, so it ignores pos entirely and takes the next free ODD slot 5. The two cursors never collide because they start one apart and both step by 2, so a negative can never overwrite a positive already parked at an even index. neg jumps to 7.
  8. nums[6]=-1 is negative, so it ignores pos entirely and takes the next free ODD slot 7. The two cursors never collide because they start one apart and both step by 2, so a negative can never overwrite a positive already parked at an even index. neg jumps to 9.
  9. Reading the input left to right, nums[7]=6 is positive, so it takes the next free EVEN slot 6. Because the input is scanned in order and pos only ever moves forward, the positives land in exactly the order they appeared — that is what keeps the relative order intact for free. pos jumps to 8, skipping slot 7, which is reserved for a negative.
  10. Every one of the 8 inputs was read exactly once and written exactly once, so the result [3, -2, 1, -5, 2, -4, 6, -1] alternates sign from the first slot. pos=8 and neg=9 both walked off the end together, which is the built-in check that the input really did hold equal counts of each sign. Building a separate positives list and a negatives list and zipping them costs the same O(n) time but two extra passes — the parity trick does it in one.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Rearrange Array Elements by Sign in the editorAll Arrays problemsBack to roadmap