LeetCode 2149 - Rearrange Array Elements by Sign

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Simulation

Solution

Problem Understanding

The problem asks us to rearrange a given integer array nums such that positive and negative numbers alternate, starting with a positive number. The array has an even length and contains an equal number of positive and negative integers. In addition to alternating signs, the relative order of positive numbers among themselves and negative numbers among themselves must remain the same as in the original array.

The input nums represents an initial sequence of integers, which may be interleaved or clustered in any order. The output is the rearranged array satisfying all conditions: it alternates in sign, preserves relative order, and starts with a positive integer.

Constraints tell us that the array can be fairly large, up to $2 \times 10^5$ elements, but the guarantees of equal positive and negative counts and even length simplify handling edge cases. We do not need to rearrange in-place, so extra space is allowed.

Important edge cases include arrays that already satisfy the conditions, arrays where all positives are clustered at the beginning, or negatives are clustered, and arrays with minimal length (2 elements).

Approaches

A brute-force approach would try to pick elements one by one from the array to form the alternating sequence, checking for sign at each step and scanning the remaining array. While correct, it would be inefficient due to repeated scans for the next positive or negative element. Its time complexity would be $O(n^2)$.

The optimal approach leverages the equal count of positives and negatives. We can split the array into two lists: one for positive numbers and one for negative numbers. Then, we construct the result array by alternating elements from these two lists, starting with a positive number. This preserves relative order and guarantees alternating signs in a single pass. This approach runs in $O(n)$ time and uses $O(n)$ additional space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly scan for next positive/negative element
Optimal	O(n)	O(n)	Split array into positives/negatives, then alternate

Algorithm Walkthrough

Initialize two empty lists: positives and negatives.
Iterate through nums. For each number, append it to positives if it is positive, or negatives if it is negative. This step preserves relative order within each sign group.
Initialize an empty list result and indices p_idx = 0 and n_idx = 0 to track the position in positives and negatives.
Iterate through the indices of the output array:
If the current index is even, append the next positive from positives[p_idx] and increment p_idx.
If the current index is odd, append the next negative from negatives[n_idx] and increment n_idx.
Return the result array after filling all positions.

Why it works: The algorithm alternates elements by design, starting with a positive number. Splitting preserves original relative order. Because the array has equal numbers of positives and negatives, we will always exhaust both lists exactly when filling the result array.

Python Solution

from typing import List

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        positives = []
        negatives = []

        for num in nums:
            if num > 0:
                positives.append(num)
            else:
                negatives.append(num)
        
        result = []
        p_idx = 0
        n_idx = 0

        for i in range(len(nums)):
            if i % 2 == 0:
                result.append(positives[p_idx])
                p_idx += 1
            else:
                result.append(negatives[n_idx])
                n_idx += 1

        return result

The code first separates the input array into positive and negative lists while preserving their order. Then, it constructs the result array by alternating elements, starting with a positive. Using index pointers avoids repeated scanning, making this linear time and space.

Go Solution

func rearrangeArray(nums []int) []int {
    positives := make([]int, 0, len(nums)/2)
    negatives := make([]int, 0, len(nums)/2)

    for _, num := range nums {
        if num > 0 {
            positives = append(positives, num)
        } else {
            negatives = append(negatives, num)
        }
    }

    result := make([]int, len(nums))
    pIdx, nIdx := 0, 0

    for i := 0; i < len(nums); i++ {
        if i%2 == 0 {
            result[i] = positives[pIdx]
            pIdx++
        } else {
            result[i] = negatives[nIdx]
            nIdx++
        }
    }

    return result
}

In Go, slices are used to store positives and negatives. Capacity is preallocated to avoid repeated resizing. The alternating construction mirrors the Python approach.

Worked Examples

Example 1: nums = [3,1,-2,-5,2,-4]

Split into positives = [3,1,2], negatives = [-2,-5,-4].
Build result alternately:

Index 0: positive → 3
Index 1: negative → -2
Index 2: positive → 1
Index 3: negative → -5
Index 4: positive → 2
Index 5: negative → -4

Result: [3,-2,1,-5,2,-4].

Example 2: nums = [-1,1]

positives = [1], negatives = [-1]
Alternating: [1,-1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass to split array and single pass to merge
Space	O(n)	Additional lists for positives and negatives

The linear time is guaranteed because each element is touched only twice. Space is linear because we store half of the elements in two separate lists.

Test Cases

# Provided examples
assert Solution().rearrangeArray([3,1,-2,-5,2,-4]) == [3,-2,1,-5,2,-4]
assert Solution().rearrangeArray([-1,1]) == [1,-1]

# Minimal input
assert Solution().rearrangeArray([1,-1]) == [1,-1]

# Already alternating
assert Solution().rearrangeArray([1,-1,2,-2]) == [1,-1,2,-2]

# All positives first, all negatives last
assert Solution().rearrangeArray([1,2,3,-1,-2,-3]) == [1,-1,2,-2,3,-3]

# Larger array
assert Solution().rearrangeArray([5,3,-2,-4,6,-1,7,-3]) == [5,-2,3,-4,6,-1,7,-3]

Test	Why
`[3,1,-2,-5,2,-4]`	Standard mixed order example
`[-1,1]`	Minimal array of length 2
`[1,-1,2,-2]`	Already alternating array
`[1,2,3,-1,-2,-3]`	All positives then all negatives
`[5,3,-2,-4,6,-1,7,-3]`	Larger array with multiple positives and negatives

Edge Cases

Minimal array: With only two elements, the algorithm must simply swap if needed. Our approach correctly handles this because it alternates starting from index 0 and assumes the first positive exists.

Array already alternating: The algorithm still works because splitting preserves relative order and rebuilding the array alternates elements correctly.

Clustered positives and negatives: When positives and negatives are not interleaved, naive scanning approaches could fail. By splitting and using index pointers, we guarantee proper alternating arrangement regardless of initial clustering.

This solution is robust for all inputs that meet the problem constraints.