Array Unlock Sequence
MediumGreedy · Amazon
You are given an integer array values of length n, a binary string state of the same length, and an integer operations. Index i is available if state[i] == '1' and blocked if state[i] == '0'.
Perform exactly operations operations, building a sequence S. Each operation has two steps:
- Append to
Sthe largestvalues[i]over all currently available indicesi. Values are not used up: the same index can supply the maximum again in later operations. - Unlock: every blocked index
iwhose left neighbori - 1was available at the start of this operation becomes available. Unlocking spreads one index to the right per operation and never spreads to the left.
Return S as a list of length operations.
Example 1
- Input:
- values = [3, 8, 2, 9, 4, 1], state = '100010', operations = 4
- Output:
- [4, 8, 8, 9]
- Explanation
- Indices 0 and 4 start available, so the first pick is max(3, 4) = 4, and indices 1 and 5 unlock. Then 8 becomes the best, and stays best while index 2 (value 2) unlocks. By the fourth operation index 3 has unlocked, so 9 is picked.
Example 2
- Input:
- values = [5, 1, 7], state = '010', operations = 3
- Output:
- [1, 7, 7]
- Explanation
- Only index 1 starts available, so the first value is 1. Index 2 unlocks next, so 7 is picked twice. Index 0 has no available left neighbor, so its 5 is never reachable.
Constraints
1 <= values.length <= 10^5state.length == values.length, andstatecontains at least one'1'1 <= values[i] <= 10^91 <= operations <= 10^5