Given an integer array nums of even length with equal numbers of positive and negative values, arrange its values so the first value is positive and adjacent values have opposite signs. Return the rearranged array, preserving the relative order of the values within each sign.
Example 1
Input: nums = [-5, -2, 4, 7, -8, 4, 1, -6]
Output: [4, -5, 7, -2, 4, -8, 1, -6]
Explanation: The positives appear in the order [4, 7, 4, 1] and the negatives in the order [-5, -2, -8, -6]. The output takes one value from each sequence in turn, starting with the first 4.
Example 2
Input: nums = [-9, 2]
Output: [2, -9]
Explanation: The only positive value, 2, must come first. The only negative value, -9, follows it.
Brute Force Approach
The answer interleaves the positive values in their original order with the negative values in their original order. Collecting each sign in a separate list keeps those two orders intact.
Both lists have the same length, so each positive value can be paired with the negative value at the same position in its list. Taking the positive value first in every pair makes the answer alternate across pair boundaries as well as within each pair.
Algorithm
Create one empty list for positives and another for negatives.
Read the input from left to right and append each value to the list for its sign.
Create an answer array with the same length as the input.
Take the two lists in order and write each pair into the next two answer positions, with the positive value first.
Return the answer after all pairs have been written. An input of length two produces exactly one pair.
Dry Run
Rearrange Array Elements by Sign
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the array with alternating signs and stable order within each sign. vector<int> rearrangeArray(vector<int>& nums) { int n = nums.size(); vector<int> positives; vector<int> negatives; // Collect each sign in the same order as in the input. for (int value : nums) { // Append positive values to the list for even output indices. if (value > 0) { positives.push_back(value); } // Append negative values to the list for odd output indices. else { negatives.push_back(value); } } vector<int> result(n); // Write one positive and one negative into each consecutive pair. for (int i = 0; i < n / 2; i++) { result[2 * i] = positives[i]; result[2 * i + 1] = negatives[i]; } return result; }};// Driver codeint main() { vector<int> nums = {-5, -2, 4, 7, -8, 4, 1, -6}; // instance for class Solution Solution sol; vector<int> result = sol.rearrangeArray(nums); // Print the values in their rearranged order. for (int value : result) { cout << value << ' '; } cout << '\n';}Complexity Analysis
Time Complexity: O(N), because the method collects all N values and then writes N / 2 pairs.
Space Complexity: O(N) auxiliary space for the two sign lists combined, plus O(N) for the returned array.
Optimal Approach
As the answer starts positive, every even index belongs to a positive value and every odd index belongs to a negative value. A value's destination is the first unfilled index for its sign. Filling those positions in input order preserves the order of each sign, and the equal counts ensure every position gets filled.
Two write indices are enough to track those positions, so each value can go straight into the answer without the temporary sign lists or the separate interleaving pass. Writing all n values takes linear time, so the method meets that lower bound.
Algorithm
Allocate an answer array with the same length as the input.
Set the next positive and negative positions to indices
0and1, respectively. These are the only two slots when the input has length two.Read the input values from left to right.
For a positive value, write it to the next positive position and move that position forward by two.
For a negative value, write it to the next negative position and move that position forward by two.
Return the answer after all input values have been read.
Dry Run
Rearrange Array Elements by Sign
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the array with alternating signs and stable order within each sign. vector<int> rearrangeArray(vector<int>& nums) { int n = nums.size(); vector<int> result(n); int positiveIndex = 0; int negativeIndex = 1; // Read each value in encounter order and fill its sign's next slot. for (int value : nums) { // Use the next even index for a positive value. if (value > 0) { result[positiveIndex] = value; positiveIndex += 2; } // Use the next odd index for a negative value. else { result[negativeIndex] = value; negativeIndex += 2; } } return result; }};// Driver codeint main() { vector<int> nums = {-5, -2, 4, 7, -8, 4, 1, -6}; // instance for class Solution Solution sol; vector<int> result = sol.rearrangeArray(nums); // Print the values in their rearranged order. for (int value : result) { cout << value << ' '; } cout << '\n';}Complexity Analysis
Time Complexity: O(N), because each input value is read and placed once.
Space Complexity: O(1) auxiliary space for the write indices and other scalar variables, plus O(N) for the returned array.
Interview follow-up Questions
Yes. Its first slot must contain the first positive from nums, its second slot must contain the first negative, and each subsequent pair must use the next value of each sign. The starting sign and the two fixed encounter orders determine every position.
Be the first to add a comment.