Rearrange Array Elements by Sign

Medium
354.

Rearrange Array Elements by Sign

Rearrange Array Elements by Sign is a medium coding problem on arrays, two pointers and simulation, asked in Amazon and Adobe interviews.

You are given a 0-indexed integer array nums of even length, holding an equal number of positive and negative integers.

Rearrange it so that consecutive elements have opposite signs, the array starts with a positive integer, and the relative order within the positives and within the negatives is preserved.

Example 1

Input
nums = [3,1,-2,-5,2,-4]
Output
[3,-2,1,-5,2,-4]

Example 2

Input
nums = [-1,1]
Output
[1,-1]

Example 3

Input
nums = [1,-1,2,-2]
Output
[1,-1,2,-2]

Constraints

  • 2 <= nums.length <= 40
  • nums.length is even.
  • Equal counts of positive and negative values.
  • -1000 <= nums[i] <= 1000, and nums[i] != 0
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var rearrangeArray = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Rearrange Array Elements by Sign — Problem & Solution

Rearrange Array Elements by Sign solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Rearrange Array Elements by Sign is a medium coding problem on arrays, two pointers and simulation, asked in Amazon and Adobe interviews.

  • Difficulty: Medium
  • Topics: Arrays, Two Pointers, Simulation
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a 0-indexed integer array nums of even length, holding an equal number of positive and negative integers.

Rearrange it so that consecutive elements have opposite signs, the array starts with a positive integer, and the relative order within the positives and within the negatives is preserved.

Example 1

Input: nums = [3,1,-2,-5,2,-4]
Output: [3,-2,1,-5,2,-4]

Example 2

Input: nums = [-1,1]
Output: [1,-1]

Example 3

Input: nums = [1,-1,2,-2]
Output: [1,-1,2,-2]

Constraints

  • 2 <= nums.length <= 40
  • nums.length is even.
  • Equal counts of positive and negative values.
  • -1000 <= nums[i] <= 1000, and nums[i] != 0

Hints for Rearrange Array Elements by Sign

  1. Hint 1

    Split into a list of positives and a list of negatives, each in original order.

  2. Hint 2

    Then interleave them, positives at the even indices.

  3. Hint 3

    Two cursors over the original array achieve the same in one pass, writing directly into the output.

How to solve Rearrange Array Elements by Sign

Split positives and negatives in original order and interleave, positives at even indices.

Approach

  1. Filter positives and negatives.
  2. Emit pos[k], neg[k] for each k.

Why it works

Equal counts guarantee the interleave is exact, and filtering preserves relative order.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Two cursors over the original array writing into a preallocated output achieve the same in one pass.

Reference solution

Python

def rearrangeArray(nums):
    pos = [x for x in nums if x > 0]
    neg = [x for x in nums if x < 0]
    out = []
    for p, n in zip(pos, neg):
        out.append(p)
        out.append(n)
    return out

Java

public static int[] rearrangeArray(int[] nums) {
    int[] out = new int[nums.length];
    int p = 0, n = 1;
    for (int x : nums) {
        if (x > 0) {
            out[p] = x;
            p += 2;
        } else {
            out[n] = x;
            n += 2;
        }
    }
    return out;
}

C++

vector<int> rearrangeArray(vector<int>& nums) {
    vector<int> out(nums.size(), 0);
    int p = 0, n = 1;
    for (int x : nums) {
        if (x > 0) {
            out[p] = x;
            p += 2;
        } else {
            out[n] = x;
            n += 2;
        }
    }
    return out;
}

JavaScript

var rearrangeArray = function(nums) {
    const pos = [], neg = [];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) pos.push(nums[i]);
        else neg.push(nums[i]);
    }
    const out = [];
    for (let i = 0; i < pos.length; i++) {
        out.push(pos[i]);
        out.push(neg[i]);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Two Pointers Technique