Rearrange Array Elements by Sign

Med

#1958Time: O(N), where N is the length of the `nums` array. The first loop to segregate numbers takes O(N) time. The second loop to construct the result array takes O(N/2) = O(N) time. Thus, the total time complexity is O(N).Space: O(N), where N is the length of the `nums` array. We use two lists, `positives` and `negatives`, which together will store all N elements. The space required for these lists is O(N/2) + O(N/2) = O(N). This is considered auxiliary space.1 company

Patterns

Two Pointers

Data structures

Array

Companies

Infosys

Prompt

You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers.

You should return the array of nums such that the the array follows the given conditions:

Every consecutive pair of integers have opposite signs.
For all integers with the same sign, the order in which they were present in nums is preserved.
The rearranged array begins with a positive integer.

Return the modified array after rearranging the elements to satisfy the aforementioned conditions.

Example 1:

Input: nums = [3,1,-2,-5,2,-4]
Output: [3,-2,1,-5,2,-4]
Explanation:
The positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4].
The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4].
Other ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.

Example 2:

Input: nums = [-1,1]
Output: [1,-1]
Explanation:
1 is the only positive integer and -1 the only negative integer in nums.
So nums is rearranged to [1,-1].

Constraints:

2 <= nums.length <= 2 * 10⁵
nums.length is even
1 <= |nums[i]| <= 10⁵
nums consists of equal number of positive and negative integers.

It is not required to do the modifications in-place.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves two main steps. First, we iterate through the input array and segregate the positive and negative numbers into two separate lists, while preserving their original relative order. Second, we create a new result array and merge the numbers from the two lists by interleaving them, starting with a positive number.

Algorithm

Create two empty lists, positives and negatives.
Iterate through the input array nums.
If a number is positive, add it to the positives list.
If a number is negative, add it to the negatives list.
Create a new result array result of the same size as nums.
Iterate from i = 0 to n/2 - 1 (where n is the length of nums).
In each iteration, place the i-th element from positives at result[2 * i].
Place the i-th element from negatives at result[2 * i + 1].
Return the result array.

Walkthrough

The core idea is to first separate the positive and negative numbers into their own collections. This makes it easy to pick the next positive or negative number in their original relative order.

Segregation: We initialize two dynamic arrays (or lists), one for positive numbers (positives) and one for negative numbers (negatives). We then iterate through the input nums array. Each positive number is appended to the positives list, and each negative number is appended to the negatives list. This pass ensures that the relative ordering within same-signed numbers is maintained.
Merging: After segregation, we have two lists: [3, 1, 2] and [-2, -5, -4] for the first example. We create a new result array of size n. We then loop n/2 times. In each iteration i, we take the i-th element from the positives list and place it at the even index 2*i in the result array. Then, we take the i-th element from the negatives list and place it at the odd index 2*i + 1. This interleaving process builds the final array according to the problem's conditions.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int[] rearrangeArray(int[] nums) {6        int n = nums.length;7        List<Integer> positives = new ArrayList<>();8        List<Integer> negatives = new ArrayList<>();9 10        // Segregate positive and negative numbers11        for (int num : nums) {12            if (num > 0) {13                positives.add(num);14            } else {15                negatives.add(num);16            }17        }18 19        int[] result = new int[n];20        // Merge the two lists into the result array21        for (int i = 0; i < n / 2; i++) {22            result[2 * i] = positives.get(i);23            result[2 * i + 1] = negatives.get(i);24        }25 26        return result;27    }28}

Complexity

Time

O(N), where N is the length of the `nums` array. The first loop to segregate numbers takes O(N) time. The second loop to construct the result array takes O(N/2) = O(N) time. Thus, the total time complexity is O(N).

Space

O(N), where N is the length of the `nums` array. We use two lists, `positives` and `negatives`, which together will store all N elements. The space required for these lists is O(N/2) + O(N/2) = O(N). This is considered auxiliary space.

Trade-offs

Pros

The logic is straightforward and easy to understand.
It correctly preserves the relative order of elements with the same sign.

Cons

Requires O(N) auxiliary space for the two lists, which is less space-efficient than the single-pass approach.
Involves two conceptual passes over the data: one to segregate and one to merge.

This is a more optimized approach that constructs the result array in a single pass through the input array. It uses two pointers to keep track of the next available positions for positive and negative numbers in the result array, eliminating the need for intermediate storage.

Algorithm

Create a new result array ans of size n.
Initialize a pointer for positive numbers, posIndex = 0.
Initialize a pointer for negative numbers, negIndex = 1.
Iterate through each number num in the input array nums.
If num is positive:
- Place it at ans[posIndex].
- Increment posIndex by 2.
If num is negative:
- Place it at ans[negIndex].
- Increment negIndex by 2.
Return the final ans array.

Walkthrough

This approach avoids creating intermediate lists by directly placing numbers into their correct positions in the final array in a single pass.

We start by creating a result array ans of the same size as the input. We then use two pointers: posIndex to track the next available even index (starting at 0) for a positive number, and negIndex to track the next available odd index (starting at 1) for a negative number.

We iterate through the input nums array from beginning to end. When we encounter a positive number, we place it in ans[posIndex] and then update posIndex by adding 2 to it, so it points to the next even index. Similarly, when we encounter a negative number, we place it in ans[negIndex] and update negIndex by adding 2.

Because we iterate through nums in its original order, the relative ordering of positive numbers and negative numbers is naturally preserved. Since the problem guarantees an equal number of positive and negative integers, the pointers will fill the ans array completely without going out of bounds.

1class Solution {2    public int[] rearrangeArray(int[] nums) {3        int n = nums.length;4        int[] ans = new int[n];5        int posIndex = 0; // Pointer for the next positive number position (even indices)6        int negIndex = 1; // Pointer for the next negative number position (odd indices)7 8        for (int num : nums) {9            if (num > 0) {10                ans[posIndex] = num;11                posIndex += 2;12            } else {13                ans[negIndex] = num;14                negIndex += 2;15            }16        }17        return ans;18    }19}

Complexity

Time

O(N), where N is the length of the `nums` array. We iterate through the input array only once to place all elements in their correct positions.

Space

O(N) for the output array. The auxiliary space complexity (space used besides the input and output) is O(1), as we only use a few variables as pointers. This is more space-efficient than the segregation approach.

Trade-offs

Pros

Highly efficient, completing the task in a single pass over the input array.
Minimal auxiliary space usage (O(1)), making it very space-efficient.
Combines segregation and placement into one loop, simplifying the overall process.

Cons

May be slightly less intuitive at first glance compared to the segregation approach, but is still straightforward.

Solutions

Solution

1class Solution {2public3  int[] rearrangeArray(int[] nums) {4    int[] ans = new int[nums.length];5    int i = 0, j = 1;6    for (int num : nums) {7      if (num > 0) {8        ans[i] = num;9        i += 2;10      } else {11        ans[j] = num;12        j += 2;13      }14    }15    return ans;16  }17}

1class Solution {2public:3  vector<int> rearrangeArray(vector<int> &nums) {4    vector<int> ans(nums.size());5    int i = 0, j = 1;6    for (int num : nums) {7      if (num > 0) {8        ans[i] = num;9        i += 2;10      } else {11        ans[j] = num;12        j += 2;13      }14    }15    return ans;16  }17};

1class Solution:2    def rearrangeArray(self, nums: List[int]) -> List[int]: ans = [0] * len(nums) i, j = 0, 1 for num in nums: if num > 0: ans[i] = num i += 2 else: ans[j] = num j += 2 return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem