Problem Statement
Given an integer array nums of even length consisting of an equal number of positive and negative integers.Return the answer array in such a way that the given conditions are met:
- 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.
LeetCode
Examples
Example 1:
Input: nums = [2, 4, 5, -1, -3, -4]
Output: [2, -1, 4, -3, 5, -4]
Explanation: The positive number 2, 4, 5 maintain their relative positions and -1, -3, -4 maintain their relative positions.Example 2:
Input: nums = [1, -1, -3, -4, 2, 3]
Output: [1, -1, 2, -3, 3, -4]
Explanation: The positive number 1, 2, 3 maintain their relative positions and -1, -3, -4 maintain their relative positions.Different Approaches
1️⃣ Brute Force Approach
Intuition:
As the array contains positive and negative elements, we can think of segregating the array elements into two parts. The first array will contain only positive elements and the second array will contain only negative elements. After this, we can just put the elements back in the original array alternatively. As the question states that positive elements should come first, so put positive element first and then negative one and so on. At the end of the process the original array will contain the desired result.
Code:
vector<int> rearrangeArray(vector<int>& nums) {
// Arrays, one for storing positive
// and other for storing negative elements.
vector<int> positive;
vector<int> negative;
for(int i = 0; i < nums.size(); i++) {
if (nums[i] > 0) {
// It is positive element.
positive.push_back(nums[i]);
} else {
// It is negative element.
negative.push_back(nums[i]);
}
}
int evenIndex = 0;
int oddIndex = 0;
for (int i = 0; i < nums.size(); i++) {
if (i % 2 == 0) {
// Index is for the positive element.
nums[i] = positive[evenIndex];
evenIndex++;
} else {
// Index is for the negative element.
nums[i] = negative[oddIndex];
oddIndex++;
}
}
return nums;
}Complexity Analysis:
- Time Complexity:
O(N+N), whereNis the size of the array.O(N)for traversing the array once for segregating positives and negatives and anotherO(N)for adding those elements alternatively to the array. - Space Complexity:
O(N/2 + N/2)=O(N),N/2space required to store each of the positive and negative elements in separate arrays.
2️⃣ Optimal Approach
Approach
- Initialize two variable
posIndexas 0 andnegIndexas 1 initially. - Declare and initialize array of size
nwith 0. - Now iterate in the array, check if it negative or positive.
- If positive:
- Insert element in the
ansarray at indexposIndex. - Increment
posIndexby 2.
- Insert element in the
- If negative:
- Insert element in the
ansarray at indexnegIndex. - Increment
negIndexby 2.
- Insert element in the
- If positive:
- Return
ansarray.
Dry Run:
Initialization:
+-----+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 4 | -5 | -6 | -7 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
+-----+-----+-----+-----+-----+-----+
ans = | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+
posIndex = 0
negIndex = 0First Iteration:
+-----+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 4 | -5 | -6 | -7 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
+-----+-----+-----+-----+-----+-----+
ans = | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
| negIndex
posIndex
since nums[i] > 0
1 > 0
ans[posIndex] = nums[i]
ans[0] = 1
Increment posIndex by 2.Second Iteration:
+-----+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 4 | -5 | -6 | -7 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
+-----+-----+-----+-----+-----+-----+
ans = | 1 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
negIndex |
posIndex
since nums[i] > 0
2 > 0
ans[posIndex] = nums[i]
ans[2] = 2
Increment posIndex by 2.Third Iteration:
+-----+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 4 | -5 | -6 | -7 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
+-----+-----+-----+-----+-----+-----+
ans = | 1 | 0 | 2 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
negIndex |
posIndex
since nums[i] > 0
4 > 0
ans[posIndex] = nums[i]
ans[4] = 4
Increment posIndex by 2.Fourth Iteration:
+-----+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 4 | -5 | -6 | -7 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
+-----+-----+-----+-----+-----+-----+
ans = | 1 | 0 | 2 | 0 | 4 | 0 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
negIndex |
posIndex
now nums[i] < 0 (negative number)
-5 < 0
ans[negIndex] = nums[i]
ans[1] = -5
Increment negIndex by 2.Fifth Iteration:
+-----+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 4 | -5 | -6 | -7 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
+-----+-----+-----+-----+-----+-----+
ans = | 1 | -5 | 2 | 0 | 4 | 0 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
negIndex |
posIndex
now nums[i] < 0 (negative number)
-6 < 0
ans[negIndex] = nums[i]
ans[3] = -6
Increment negIndex by 2.Sixth Iteration:
+-----+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 4 | -5 | -6 | -7 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
+-----+-----+-----+-----+-----+-----+
ans = | 1 | -5 | 2 | -6 | 4 | 0 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
negIndex |
posIndex
now nums[i] < 0 (negative number)
-6 < 0
ans[negIndex] = nums[i]
ans[5] = -7
Increment negIndex by 2.Loop Termination:
+-----+-----+-----+-----+-----+-----+
nums = | 1 | 2 | 4 | -5 | -6 | -7 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
+-----+-----+-----+-----+-----+-----+
ans = | 1 | -5 | 2 | -6 | 4 | -7 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
negIndex |
posIndex
Since i has passed the bounds, the loop would be terminated.
Return the ans array.Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
//Function to rearrange elements by their sign
vector<int> rearrangeArray(vector<int>& nums) {
int n = nums.size();
// Initialize a result vector of size n
vector<int> ans(n, 0);
// Initialize indices for positive and negative elements
int posIndex = 0, negIndex = 1;
// Traverse through each element in nums
for (int i = 0; i < n; i++) {
if (nums[i] < 0) {
/* If current element is negative, place
it at the next odd index in ans*/
ans[negIndex] = nums[i];
// Move to the next odd index
negIndex += 2;
} else {
ans[posIndex] = nums[i];
// Move to the next even index
posIndex += 2;
}
}
// Return the rearranged array
return ans;
}
};
int main() {
vector<int> A = {1, 2, -4, -5};
// Create an instance of the Solution class
Solution sol;
vector<int> ans = sol.rearrangeArray(A);
// Print the rearranged array
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N), for traversing the array only once where N is the length of the array. - Space Complexity:
O(N)to store the resultant array.