Generated by Codex with GPT-5

Quick facts

Problem gist

The input is an even-length array with exactly the same number of positive and negative integers. The task is to return a new ordering that starts with a positive number, alternates signs at every index, and keeps the relative order of the positive numbers and the relative order of the negative numbers.

For example, the first positive number in the input must become the first positive number in the output. The first negative number in the input must become the first negative number in the output. The rearrangement is not allowed to sort or otherwise reshuffle values inside the same sign group.

Core idea

Because the output must start with a positive number and alternate signs, the index pattern is fixed:

  • positives go to indices 0, 2, 4, ...;
  • negatives go to indices 1, 3, 5, ....

That turns the problem into a stable distribution step. Scan the input from left to right. When a positive value appears, write it to the next available even index. When a negative value appears, write it to the next available odd index.

This preserves order automatically. The first positive encountered gets the first positive slot, the second positive gets the second positive slot, and so on. The same logic holds for negatives.

How to derive it

A tempting first solution is to collect all positives into one list, all negatives into another list, and then weave those two lists together. That works, but it makes the underlying pattern clearer: positives and negatives are independent streams, and the final array simply alternates between those streams.

The direct solution skips the two temporary sign lists. It keeps only two write positions:

  • next_positive_slot, initially 0;
  • next_negative_slot, initially 1.

Every time a value is written, the matching slot moves forward by 2 because the next value with that sign must land at the next index of the same parity. Since the problem guarantees equal counts, both streams fill exactly half of the result array.

Python solution

from typing import List


class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        return self._build_stable_alternating_order(nums)

    def _build_stable_alternating_order(self, nums: List[int]) -> List[int]:
        arranged = [0] * len(nums)

        # The answer must start positive, so each sign owns one parity lane.
        next_positive_slot = 0
        next_negative_slot = 1

        for value in nums:
            if value > 0:
                arranged[next_positive_slot] = value
                # Move to the next even slot reserved for positives.
                next_positive_slot += 2
            else:
                arranged[next_negative_slot] = value
                # Move to the next odd slot reserved for negatives.
                next_negative_slot += 2

        return arranged

The time complexity is O(n) because each input value is inspected once. The returned array uses O(n) space. Apart from the returned array itself, the algorithm only uses O(1) extra state.

Interview follow-ups

What if positives and negatives are not equally frequent?

The fixed even-index and odd-index pattern no longer always fits. A practical solution is to first split the values into two stable queues or lists, then choose the sign that should start the output, often the sign with more values. The algorithm alternates while both groups still have values and appends the leftover group at the end.

This works because the equal-count guarantee was the reason every slot could be predetermined. Once that guarantee is removed, the algorithm needs to reason about availability. The time complexity stays O(n), but the implementation usually uses O(n) auxiliary space for the two groups unless the problem allows reordering values within each sign.

Can this be done in place while preserving relative order?

It can be done, but not as cleanly in O(n) time with O(1) extra space. Stable in-place rearrangement usually requires rotating segments when the next needed sign is found later in the array. Each rotation can shift many elements, so the simple version can degrade to O(n^2).

If preserving relative order is not required, an in-place two-pointer partition-style approach becomes much easier: swap misplaced positives and negatives into alternating parity slots. That can be O(n) time and O(1) space, but it loses the original order within the positive and negative groups.

What if the output must start with a negative number?

The same two-lane idea applies. The only change is the initial slot assignment: negatives start at index 0, and positives start at index 1.

The correctness argument is unchanged. Each sign still owns one parity of indices, and scanning left to right still preserves the order inside each sign group.

What if zero appears in the input?

The original problem avoids this because every value is either positive or negative. If zero is allowed, the interviewer must define its sign behavior. It could be treated as positive, negative, or a third neutral category.

Once the rule is defined, the implementation follows that rule. If zero belongs to one of the two sign groups, it can use the same slot logic. If zero is neutral, a two-sign alternating pattern may no longer be enough, and the problem becomes a more general stable arrangement problem with three categories.

Why does the one-pass direct-placement solution preserve order?

The scan processes values in their original order. For positives, the algorithm writes the first positive to index 0, the second positive to index 2, the third positive to index 4, and so on. No later positive can jump ahead because it is not seen until after the earlier positive has already taken the next available positive slot.

The same reasoning applies to negatives with odd indices. Since the output index sequence for each sign is increasing, the relative order inside each sign group is preserved.