Loading page…
Practice problem · medium
A video app lets viewers react with a thumbs up or a thumbs down. For each video, the app keeps the reactions in the order they arrived: 1 for a thumbs up and 0 for a thumbs down.
The team wants to see where opinion was evenly split. They ask for the longest stretch of consecutive reactions that holds as many thumbs up as thumbs down.
Write longest_balanced(bits).
bits[i] is 1 for a thumbs up and 0 for a thumbs down.0 when no stretch is balanced.Input: bits = [1, 0, 1, 1, 0, 0, 1]
Output: 6The trace keeps a balance: a 1 adds one and a 0 subtracts one. It also keeps the first position where each balance occurred. Position 0 is before any reaction, with balance 0. When a balance occurs again, the reactions in between are balanced.
| Position | Reaction | Balance | Seen before at | Run length | Best |
|---|---|---|---|---|---|
| 0 | start | 0 | 0 | ||
| 1 | 1 | 1 | not seen, store position 1 | 0 | |
| 2 | 0 | 0 | position 0 | 2 | 2 |
| 3 | 1 | 1 | position 1 | 2 | 2 |
| 4 | 1 | 2 | not seen, store position 4 | 2 | |
| 5 | 0 | 1 | position 1 | 4 | 4 |
| 6 | 0 | 0 | position 0 | 6 | 6 |
| 7 | 1 | 1 | position 1 | 6 | 6 |
The first six reactions, 1, 0, 1, 1, 0, 0, hold three 1s and three 0s. The output is 6.
Input: bits = [1, 1, 1]
Output: 0There are no 0s, so no stretch is balanced.
Input: bits = [0, 1]
Output: 2The whole list holds one 0 and one 1.
0 ≤ bits.length ≤ 100,000 (reactions to one video)bits[i] is 0 or 1Trying every start and extending the stretch one reaction at a time costs about n × n / 2 steps. For 100,000 reactions that is about 5 × 10^9, far over the budget of about 10^8 a second. One pass with a table of balances costs n steps.
longest_balanced · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.