Leetcode 2149: Rearrange Array Elements by Sign
You are given an integer array ’nums’ of even length consisting of an equal number of positive and negative integers. Rearrange the array such that every consecutive pair of integers has opposite signs, the order of integers with the same sign is preserved, and the array begins with a positive integer.
Problem
Approach
Steps
Complexity
Input: The input consists of a 0-indexed integer array 'nums' of even length.
Example: nums = [6, 3, -1, -5, 2, -4]
Constraints:
• 2 <= nums.length <= 2 * 10^5
• nums.length is even
• 1 <= |nums[i]| <= 10^5
• nums consists of an equal number of positive and negative integers.
Output: Return the rearranged array where consecutive elements have opposite signs and the order of same-signed integers is preserved.
Example: Output: [6, -1, 3, -5, 2, -4]
Constraints:
• The array must start with a positive integer and alternate between positive and negative integers.
Goal: We need to rearrange the elements such that positive and negative integers alternate, and the order of elements with the same sign remains intact.
Steps:
• Iterate over the 'nums' array and segregate the positive and negative integers.
• Place positive integers at even indices and negative integers at odd indices.
• Return the rearranged array.
Goal: The input array length is guaranteed to be even, with an equal number of positive and negative integers.
Steps:
• 2 <= nums.length <= 2 * 10^5
• nums.length is even
• 1 <= |nums[i]| <= 10^5
• nums consists of equal numbers of positive and negative integers.
Assumptions:
• The array is guaranteed to contain an equal number of positive and negative integers.
• Input: Example 1: nums = [6, 3, -1, -5, 2, -4]
• Explanation: The positive integers are [6, 3, 2] and the negative integers are [-1, -5, -4]. The only valid rearrangement is [6, -1, 3, -5, 2, -4] which alternates signs while preserving the order of positive and negative integers.
Approach: The goal is to rearrange the array such that positive and negative integers alternate while keeping the order of the same-signed integers intact.
Observations:
• The input guarantees an equal number of positive and negative integers, which simplifies the process.
• We need a way to efficiently place the positive integers at even indices and negative integers at odd indices.
Steps:
• Iterate through the array and segregate the positive and negative integers.
• Place the positive integers at even indices starting from index 0.
• Place the negative integers at odd indices starting from index 1.
• Return the rearranged array.
Empty Inputs:
• An empty array is not possible based on the problem constraints.
Large Inputs:
• The solution should efficiently handle arrays with a length up to 2 * 10^5.
Special Values:
• Arrays with the minimum possible length of 2 will follow the same rearrangement logic.
Constraints:
• The input array is guaranteed to have an equal number of positive and negative integers.
vector<int> rearrangeArray(vector<int>& nums) {
vector<int> ans(nums.size(), 0);
int idxpos = 0, idxneg = 1;
for(int num: nums) {
if(num > 0) {
ans[idxpos] = num;
idxpos += 2;
}
if(num < 0) {
ans[idxneg] = num;
idxneg += 2;
}
}
return ans;
}
1 : Function Declaration
vector<int> rearrangeArray(vector<int>& nums) {
Function declaration to rearrange the array with positive numbers at even indices and negative numbers at odd indices.
2 : Variable Initialization
vector<int> ans(nums.size(), 0);
Initialize a vector 'ans' of the same size as the input 'nums', with all elements set to 0.
3 : Variable Initialization
int idxpos = 0, idxneg = 1;
Initialize two indices, 'idxpos' to place positive numbers at even indices and 'idxneg' to place negative numbers at odd indices.
4 : Loop
for(int num: nums) {
Iterate through each number in the input 'nums' array.
5 : Condition Check
if(num > 0) {
Check if the current number is positive.
6 : Array Assignment
ans[idxpos] = num;
Place the positive number at the current 'idxpos' index in the 'ans' array.
7 : Index Update
idxpos += 2;
Increment the 'idxpos' index by 2 to move to the next even index.
8 : Condition Check
if(num < 0) {
Check if the current number is negative.
9 : Array Assignment
ans[idxneg] = num;
Place the negative number at the current 'idxneg' index in the 'ans' array.
10 : Index Update
idxneg += 2;
Increment the 'idxneg' index by 2 to move to the next odd index.
11 : Return Statement
return ans;
Return the rearranged array 'ans' with positive numbers at even indices and negative numbers at odd indices.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is linear, as we are iterating through the array once.
Best Case: O(n)
Worst Case: O(n)
Description: We use an extra array of size n to store the rearranged elements.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus