Plus, Minus, Plus

Medium

You get an array values of even length: exactly half of its numbers are positive and the other half are negative, with no zeros. Reorder the numbers so that: - the array starts with a positive number; - any two neighbouring numbers have different signs; - the positive numbers keep the order they had in values, and so do the negative ones. There is exactly one such arrangement. Return it as a new array.

Example 1

values=[-7, 2, 9, -1, -3, 4] → [2, -7, 9, -1, 4, -3]

The positives in order are 2, 9, 4 and the negatives are -7, -1, -3. Interleave them, starting with a positive.

Example 2

values=[-5, 8] → [8, -5]

The answer has to start with the positive number: [8, -5].

Constraints

2 ≤ len(values) ≤ 2 · 10⁵, and the length is even
1 ≤ |values[i]| ≤ 10⁵
There are as many positive numbers as negative ones

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers Simulation

Similar problems

Match-Three Cascade Medium Two Gardeners and Their Refills Medium Split Text at the Marks Medium Sort Into Three Piles Around a Mark Medium Hiring From Both Ends of the Line Medium

Input

values=[-7, 2, 9, -1, -3, 4]

Expected

[2, -7, 9, -1, 4, -3]

Run checks the first 3 tests in your browser. Submit checks all 99 tests on the server, hidden ones included.