Watch 10 video solutions for Rearrange Array Elements by Sign, a medium level problem involving Array, Two Pointers, Simulation. This walkthrough by take U forward has 471,863 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
nums is preserved.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.length is even1 <= |nums[i]| <= 105nums consists of equal number of positive and negative integers.It is not required to do the modifications in-place.
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 | 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. |