Two Pointers Rearranging in place

165. Rearrange Array Elements by Sign

Medium

You are given an array of integers nums of even length. Half of its numbers are positive and half are negative. There are no zeros.

Return the numbers arranged so that the signs alternate, starting with a positive number. The positive numbers must keep the order they have in nums, and so must the negative numbers.

These two rules fix every position, so there is exactly one right answer.

Example 1

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

Output: [3,-2,1,-5,2,-4]

Explanation: The positives, in order, are 3, 1 and 2. The negatives, in order, are −2, −5 and −4. They take turns, starting with 3.

Example 2

Input: nums = [-4, -7, 6, 9]

Output: [6,-4,9,-7]

Explanation: nums starts with a negative, but the answer must start with a positive, so 6 comes first.

Example 3

Input: nums = [-1000000000, 1000000000]

Output: [1000000000,-1000000000]

Check your understanding

Work out the answer for this input before you write any code.

nums = [5, 8, 1, -2, -6, -9]

Constraints

2 ≤ nums.length ≤ 2 × 10⁵
nums.length is even.
-10⁹ ≤ nums[i] ≤ 10⁹, and nums[i] ≠ 0
nums has as many positive numbers as negative numbers.

Clarifying questions

What you would ask an interviewer before writing any code.