Alternate Gains and Losses
MediumArrays & Hashing
Problem
A trading journal lists daily price changes in changes. There are exactly as many gains (positive values) as losses (negative values), and no zeros.
Rearrange the changes so that they alternate gain, loss, gain, loss, … starting with a gain, while gains keep their original relative order and losses keep theirs. Return the rearranged array.
Example 1
- Input:
- changes = [3, 1, -2, -5, 2, -4]
- Output:
- [3, -2, 1, -5, 2, -4]
Gains 3, 1, 2 go to even slots and losses -2, -5, -4 to odd slots, each in original order.
Example 2
- Input:
- changes = [-1, 1]
- Output:
- [1, -1]
Constraints
- 2 ≤ changes.length ≤ 2 · 10^5, and the length is even
- 1 ≤ |changes[i]| ≤ 10^5
- Gains and losses are equal in number.
Hint
Show the first hint
In the output, which slots hold gains and which hold losses? Is that fixed in advance?
Walkthrough
How to approach it
01Clarify before coding
- Must the order inside each sign be preserved? Yes, stable for both.
- Does the output always start with a gain? Yes.
- Is the output a new array? Yes; an in-place stable version is a much harder follow-up.
02Brute force
Repeatedly scan for the next value of the needed sign and move it forward by shifting the elements in between.
Cost: O(n²) time from all the shifting.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.