Rearrange Array Elements by Sign - Solution & Explanation
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 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
numsis 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 * 105nums.lengthis even1 <= |nums[i]| <= 105numsconsists of equal number of positive and negative integers.
It is not required to do the modifications in-place.
Approach Overview
Problem Overview: You are given an array with equal numbers of positive and negative integers. Rearrange the elements so positives and negatives appear alternately, starting with a positive number, while preserving the relative order of elements.
Approach 1: Two Lists Approach (O(n) time, O(n) space)
Split the array into two separate lists: one for positive numbers and one for negative numbers. Iterate through the original array once and push values into the corresponding list. Then construct the result by alternating elements from both lists: positive at even indices and negative at odd indices. Since the problem guarantees equal counts of positives and negatives, both lists will be exhausted at the same time. This approach is straightforward and preserves relative order naturally because elements are appended in the order they appear. It’s commonly used when solving array rearrangement problems where stability matters.
Approach 2: In-place Rearrangement (O(n) time, O(1) extra space)
Instead of maintaining two auxiliary lists, place elements directly into their correct positions using index pointers. Maintain two indices: one pointing to the next even index (for positives) and another pointing to the next odd index (for negatives). Iterate through the array and place each value in the correct index based on its sign. After placing a number, move the corresponding pointer by two positions. The key insight is that positives must occupy even indices (0,2,4...) while negatives occupy odd indices (1,3,5...). This keeps the alternating pattern intact without storing intermediate lists. The technique resembles a controlled placement strategy often used with two pointers and simple simulation logic.
Both strategies run in linear time because each element is processed once. The difference is memory usage: the two-list solution trades space for clarity, while the in-place strategy minimizes auxiliary storage.
Recommended for interviews: The two lists approach is usually the first solution candidates implement because it clearly demonstrates understanding of the alternating constraint and order preservation. Interviewers often expect the O(n) time complexity solution quickly. After that, discussing the in-place rearrangement shows deeper optimization skills and awareness of space complexity tradeoffs.
Approach 1: Two Lists Approach
This approach involves creating two separate lists to store positive and negative numbers. After separating, we iterate through both lists simultaneously, placing elements alternatively from each into a new result list. This ensures that conditions for alternating signs and preserving order are met.
This C program separates the positive and negative numbers into two arrays, then fills the result array in alternating order.
Complexity
Time Complexity: O(n); Space Complexity: O(n).
Approach 2: In-place Rearrangement
This approach attempts to rearrange the array in-place with the help of two pointers: one for the next positive element and one for the next negative. Starting with the assumption that the first element should be positive, iterate over the array and swap elements to their correct positions as needed.
In this in-place C solution, pointers keep track of the correct next position for positive and negative elements, swapping where necessary.
Complexity
Time Complexity: O(n); Space Complexity: O(1).
Approach 3: Two Pointers
First, we create an array ans of length n. Then, we use two pointers i and j to point to the even and odd indices of ans, respectively, with initial values i = 0, j = 1.
We iterate through the array nums. If the current element x is a positive integer, then we place x into ans[i] and increase i by 2; otherwise, we place x into ans[j] and increase j by 2.
Finally, we return ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two Lists Approach | Time Complexity: O(n); Space Complexity: O(n). |
| In-place Rearrangement | Time Complexity: O(n); Space Complexity: O(1). |
| Two Pointers | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Lists Approach | O(n) | O(n) | Best for clarity and quick implementation when extra memory is acceptable. |
| In-place Rearrangement | O(n) | O(1) | Useful when memory is constrained or when interviewers ask for optimized space usage. |
| Two-Pointer Placement with Result Array | O(n) | O(n) | Good balance of simplicity and speed when directly filling even and odd indices. |
Video Solution
Rearrange Array Elements by Sign | 2 Varieties of same Problem • take U forward • 526,209 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Rearrange Array Elements by Sign easy or hard?
Rearrange Array Elements by Sign Python/Java solution
How to solve Rearrange Array Elements by Sign in O(n)?
What is the best approach for Rearrange Array Elements by Sign?
Is Rearrange Array Elements by Sign asked at Google/Amazon/Meta?
What data structure is used in Rearrange Array Elements by Sign?
What is the time complexity of Rearrange Array Elements by Sign?
Ready to solve this problem?
Practice Rearrange Array Elements by Sign with our built-in code editor and test cases.
Practice on FleetCode