NeetCode #210LC-2149MediumTwo Pointers
← Back to All Problems#210 · #2149 · Rearrange Array Elements by Sign(按符号重排数组)
📌 Problem Statement & Constraints
Given an integer array
nums with an equal number of positive and negative integers, rearrange it so that positives occupy the even indices and negatives the odd indices, preserving their relative order. Constraints: 2 <= nums.length <= 2 * 10^5, nums.length is even, nums[i] != 0.💡 Core Algorithmic Approaches
- Two write pointers: one at index 0 for positives (advancing by 2) and one at index 1 for negatives.
- Scan the array in order, writing each value into its group's next slot.
- Because the scan is in order and the write pointers advance monotonically within each group, the relative order is preserved automatically.
- The result array is a fresh allocation, so the input is not modified.
💻 Benchmark Python3 Implementation
class Solution:
def rearrangeArray(self, nums: List[int]) -> List[int]:
res = [0] * len(nums)
pos, neg = 0, 1 # even slots for positives, odd for negatives
for x in nums:
if x > 0:
res[pos] = x
pos += 2
else:
res[neg] = x
neg += 2
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(n) for the result. In-place rearrangement with order preservation is not possible in a single pass, which is why the extra array is needed.
⚠️ Interview Pitfalls & Follow-ups
- Using a single write pointer with swaps: the relative order would be lost.
- Advancing by 1 instead of 2: the groups would collide.
- Assuming the counts differ: the constraints guarantee an equal number of positives and negatives, so no slot is left unfilled.
- Treating 0 as positive: the constraints exclude 0, but if it occurred it would need an explicit decision.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.