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.
Time Complexity: O(n); Space Complexity: O(n).
1#include <iostream>
2#include <vector>
3using namespace std;
4
5vector<int> rearrangeArray(vector<int>& nums) {
6 vector<int> pos, neg, result(nums.size());
7
8 for (int num : nums) {
9 if (num > 0) pos.push_back(num);
10 else neg.push_back(num);
11 }
12
13 int posIndex = 0, negIndex = 0;
14 for (int i = 0; i < nums.size(); i += 2) {
15 result[i] = pos[posIndex++];
16 result[i + 1] = neg[negIndex++];
17 }
18 return result;
19}
20
21int main() {
22 vector<int> nums = {3, 1, -2, -5, 2, -4};
23 vector<int> result = rearrangeArray(nums);
24 for (int num : result) cout << num << " ";
25 return 0;
26}This C++ program uses vectors to store positive and negative numbers separately, then merges them in alternating order.
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.
Time Complexity: O(n); Space Complexity: O(1).
1import java.util.Arrays;
2
3public class RearrangeArray {
4 public static void rearrangeArray(int[] nums) {
5 int pos = 0, neg = 1;
6 while (pos < nums.length && neg < nums.length) {
7 if (nums[pos] > 0) pos += 2;
8 else if (nums[neg] < 0) neg += 2;
9 else {
10 int temp = nums[pos];
11 nums[pos] = nums[neg];
12 nums[neg] = temp;
13 }
14 }
15 }
16
17 public static void main(String[] args) {
18 int[] nums = {3, 1, -2, -5, 2, -4};
19 rearrangeArray(nums);
20 System.out.println(Arrays.toString(nums));
21 }
22}This Java implementation swaps elements directly in the array to achieve the desired order, using separate pointers for positive and negative elements.