Scale Engineer

Rearrange Array Elements by Sign

Med
#1958Time: O(N), where N is the length of the `nums` array. The first loop to segregate numbers takes O(N) time. The second loop to construct the result array takes O(N/2) = O(N) time. Thus, the total time complexity is O(N).Space: O(N), where N is the length of the `nums` array. We use two lists, `positives` and `negatives`, which together will store all N elements. The space required for these lists is O(N/2) + O(N/2) = O(N). This is considered auxiliary space.1 company
Patterns
Two Pointers
Data structures
Array
Companies
Infosys

Prompt

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:

  1. Every consecutive pair of integers have opposite signs.
  2. For all integers with the same sign, the order in which they were present in nums is preserved.
  3. The rearranged array begins with a positive integer.

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 * 105
  • nums.length is even
  • 1 <= |nums[i]| <= 105
  • nums consists of equal number of positive and negative integers.

 

It is not required to do the modifications in-place.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves two main steps. First, we iterate through the input array and segregate the positive and negative numbers into two separate lists, while preserving their original relative order. Second, we create a new result array and merge the numbers from the two lists by interleaving them, starting with a positive number.

Algorithm

  • Create two empty lists, positives and negatives.
  • Iterate through the input array nums.
  • If a number is positive, add it to the positives list.
  • If a number is negative, add it to the negatives list.
  • Create a new result array result of the same size as nums.
  • Iterate from i = 0 to n/2 - 1 (where n is the length of nums).
  • In each iteration, place the i-th element from positives at result[2 * i].
  • Place the i-th element from negatives at result[2 * i + 1].
  • Return the result array.

Walkthrough

The core idea is to first separate the positive and negative numbers into their own collections. This makes it easy to pick the next positive or negative number in their original relative order.

  1. Segregation: We initialize two dynamic arrays (or lists), one for positive numbers (positives) and one for negative numbers (negatives). We then iterate through the input nums array. Each positive number is appended to the positives list, and each negative number is appended to the negatives list. This pass ensures that the relative ordering within same-signed numbers is maintained.

  2. Merging: After segregation, we have two lists: [3, 1, 2] and [-2, -5, -4] for the first example. We create a new result array of size n. We then loop n/2 times. In each iteration i, we take the i-th element from the positives list and place it at the even index 2*i in the result array. Then, we take the i-th element from the negatives list and place it at the odd index 2*i + 1. This interleaving process builds the final array according to the problem's conditions.

import java.util.ArrayList;import java.util.List; class Solution {    public int[] rearrangeArray(int[] nums) {        int n = nums.length;        List<Integer> positives = new ArrayList<>();        List<Integer> negatives = new ArrayList<>();         // Segregate positive and negative numbers        for (int num : nums) {            if (num > 0) {                positives.add(num);            } else {                negatives.add(num);            }        }         int[] result = new int[n];        // Merge the two lists into the result array        for (int i = 0; i < n / 2; i++) {            result[2 * i] = positives.get(i);            result[2 * i + 1] = negatives.get(i);        }         return result;    }}

Complexity

Time

O(N), where N is the length of the `nums` array. The first loop to segregate numbers takes O(N) time. The second loop to construct the result array takes O(N/2) = O(N) time. Thus, the total time complexity is O(N).

Space

O(N), where N is the length of the `nums` array. We use two lists, `positives` and `negatives`, which together will store all N elements. The space required for these lists is O(N/2) + O(N/2) = O(N). This is considered auxiliary space.

Trade-offs

Pros

  • The logic is straightforward and easy to understand.

  • It correctly preserves the relative order of elements with the same sign.

Cons

  • Requires O(N) auxiliary space for the two lists, which is less space-efficient than the single-pass approach.

  • Involves two conceptual passes over the data: one to segregate and one to merge.

Solutions

class Solution {public  int[] rearrangeArray(int[] nums) {    int[] ans = new int[nums.length];    int i = 0, j = 1;    for (int num : nums) {      if (num > 0) {        ans[i] = num;        i += 2;      } else {        ans[j] = num;        j += 2;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem