Rearrange Array Elements by Sign
Problem link: https://leetcode.com/problems/rearrange-array-elements-by-sign/
Problem Statement
You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers.
You should rearrange the elements of nums such that the modified array follows these conditions:
- Every consecutive pair of integers have opposite signs.
- For all integers with the same sign, the relative order in which they were present in
numsis preserved. - The rearranged array begins with a positive integer.
Input
An integer array nums with equal positive and negative integers.
Output
The rearranged array meeting the sign and order conditions.
Example
Input: nums = [3,1,-2,-5,2,-4] Output: [3,-2,1,-5,2,-4]
Explanation
Positive integers: [3, 1, 2]. Negative integers: [-2, -5, -4]. We interleave them starting with positive, maintaining their original order.
Brute Force
Intuition
Separate the positive and negative numbers into two distinct lists, then loop through both and pick one from each to fill a new result array.
Approach
- Create two lists:
posandneg. - Traverse
numsand add positive numbers toposand negative numbers toneg. - Use a loop to fill the result array by alternating elements from
posandneg.
Dry Run
nums = [1, -1] pos = [1], neg = [-1] Result[0] = pos[0], Result[1] = neg[0] Result = [1, -1]
Code (Java)
class Solution {
public int[] rearrangeArray(int[] nums) {
List<Integer> pos = new ArrayList<>();
List<Integer> neg = new ArrayList<>();
for (int x : nums) {
if (x > 0) pos.add(x);
else neg.add(x);
}
int[] ans = new int[nums.length];
for (int i = 0; i < nums.length / 2; i++) {
ans[2 * i] = pos.get(i);
ans[2 * i + 1] = neg.get(i);
}
return ans;
}
}
Complexity Analysis
We iterate through the array twice and use extra space to store separated lists.
Optimal Solution
Intuition
We know positive integers will always occupy even indices (0, 2, 4...) and negative integers will occupy odd indices (1, 3, 5...). We can use two pointers to fill the result array in a single pass.
Approach
- Initialize
posIdx = 0andnegIdx = 1. - Create a result array
ansof the same size asnums. - Iterate through
numsonce. - If the current number is positive, place it at
ans[posIdx]and incrementposIdxby 2. - If the current number is negative, place it at
ans[negIdx]and incrementnegIdxby 2. - Return
ans.
Dry Run
nums = [3, -2, 1, -5]
- 3 is positive: ans[0]=3, posIdx=2
- -2 is negative: ans[1]=-2, negIdx=3
- 1 is positive: ans[2]=1, posIdx=4
- -5 is negative: ans[3]=-5, negIdx=5
Code (Java)
class Solution {
public int[] rearrangeArray(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
int posIdx = 0, negIdx = 1;
for (int i = 0; i < n; i++) {
if (nums[i] > 0) {
ans[posIdx] = nums[i];
posIdx += 2;
} else {
ans[negIdx] = nums[i];
negIdx += 2;
}
}
return ans;
}
}
Complexity Analysis
We traverse the array once. The result array takes O(N) space, which is required for the output.
Quick Revision (Brute Force)
- Separate positives and negatives into lists
- Fill result by alternating
- Two passes over data
Quick Revision (Optimal)
- Single pass with two pointers
- posIdx starts at 0, negIdx starts at 1
- Increment pointers by 2 after placement
- Maintain relative order automatically