Rearrange Array Elements by Sign
A medium Arrays interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Arrays
- Sheets
- 1
- Core for
- 26 roles
The problem
Rearrange the array so that positive and negative numbers alternate, preserving their original relative order within each group.
Example 1
- Input
- [-2,6,-5,3,8,-1]
- Output
- [6,-2,3,-5,8,-1]
Example 2
- Input
- [-1,1,-2,2]
- Output
- [1,-1,2,-2]
Example 3
- Input
- [1,-1]
- Output
- [1,-1]
Constraints
- 1 <= n <= 10^5
- -10^9 <= arr[i] <= 10^9
How to think about it
Updated 2026-09-29Positive values belong at even indices (0, 2, 4...) and negative values belong at odd indices (1, 3, 5...). Walking the array once and dispatching numbers directly into their next designated even or odd slots in a target buffer preserves their original encounter order without any pairwise shuffling.
Approaches, worst first
Separate partition lists
time O(n) · space O(n)
Filter positive numbers into one list and negative numbers into another. Then iterate from 0 to n / 2 - 1, interleaving elements back into the main array or an output array. Requires two intermediate lists, taking 2n auxiliary space.
Direct index dispatchWrite this one
time O(n) · space O(n)
Allocate a result array of length n with positiveIndex = 0 and negativeIndex = 1. Iterate through arr: place positive values at positiveIndex and advance it by 2; place negative values at negativeIndex and advance it by 2. Fills the result in a single pass.
Where people lose marks · 3
- Advancing index pointers by 1 instead of 2 overwrites alternate signs and misaligns polarity.
- Zero can be categorized arbitrarily if sign conditions are not strictly defined; checking `> 0` vs `< 0` requires confirming how non-negative zeros are grouped.
- Attempting in-place swapping with two pointers destroys the original relative ordering demanded by the problem statement.
The theory behind it
Arrays — the ground this problem stands on. All Arrays problems
What Arrays is
An array is a row of fixed boxes laid side by side in computer memory, like numbered lockers in a hallway. Because each box occupies identical space and sits directly next to its neighbors, jumping to locker zero or locker ten thousand takes the exact same tiny fraction of time. Every box holds an item of the same type, addressed by an offset number called an index.
When to reach for it
Reach for an array when items arrive in a known sequence and need immediate retrieval by position number. Problems asking for running totals, prefix accumulations, cyclic rotations, or in-place rearrangements signal array mechanics. Whenever constraints require constant-time random lookups or contiguous cache scans across fixed collections, a flat sequence is the default container.
How the pattern works
Visualize a tape with zero-indexed slots stretching from start to end. Keep track of write and read cursors when modifying contents without allocating helper buffers. For running computations, maintain an invariant such as having processed all elements left of the current index while pending elements wait to the right. When modifying entries in place, consider scanning backwards from the end so unread data is not overwritten.
More Arrays problems
Target Roles
Core requirement for 26 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .