Domino Chain Toppling
MediumOnline Assessment
Push some dominoes along a table and report which ones end up lying down.
Domino i stands at positions[i] (strictly increasing) and is heights[i] tall. Time moves in whole ticks.
- When a domino falls at tick
ttoward higher positions (right), it strikes every dominojwithpositions[i] < positions[j] <= positions[i] + heights[i]; dominojis struck at tickt + (positions[j] - positions[i]). Falling toward lower positions (left) is symmetric: it strikes everyjwithpositions[i] - heights[i] <= positions[j] < positions[i], at tickt + (positions[i] - positions[j]). The reach is the whole height, so a tall domino can strike dominoes beyond a shorter neighbour directly. - A standing domino that is struck falls at that very tick, in the direction it was struck: a domino struck by one falling right falls right, and one struck by one falling left falls left. If a domino receives strikes from both directions at the same tick, it falls right.
- A domino that is already down ignores everything, including strikes that were scheduled before it fell.
pushesis a list of[tick, index, direction]where direction is"R"or"L". A push acts exactly like a strike from that direction at that tick on dominoindex(so it can tie with other strikes). A push on a domino that is already down at that tick does nothing.
Input: positions, heights, pushes.
Output: [fallen, last_tick, standing]: how many dominoes fell, the tick at which the last one fell (0 if none fell), and the sorted indices of the dominoes still standing.
Example 1
- Input:
- [[0,2,3,7,9,12],[3,2,4,2,3,1],[[0,0,"R"]]]
- Output:
- [6,12,[]]
- Explanation
- Domino 0 falls right at tick 0 and reaches positions up to 3, striking domino 1 (tick 2) and domino 2 (tick 3). Domino 1 (height 2) only reaches position 4, so domino 2 is also struck by it at tick 3, but it is already falling. Domino 2 (height 4) reaches position 7, striking domino 3 at tick 7 and domino 4 at tick 9 directly. Domino 4 reaches position 12 and strikes domino 5 at tick 12. All 6 fall and the last falls at tick 12.
Example 2
- Input:
- [[0,3,5,6,9],[4,3,2,3,4],[[0,0,"R"],[1,4,"L"]]]
- Output:
- [5,5,[]]
- Explanation
- Domino 0 is pushed right at tick 0 and hits domino 1 at tick 3; domino 4 is pushed left at tick 1 and hits domino 3 at tick 4 (so it falls left) and domino 2 at tick 5. Domino 1 falls right at tick 3 and reaches domino 2 at tick 5 too. Domino 3 falls left at tick 4 and also reaches domino 2 at tick 5. Domino 2 is struck at tick 5 from both directions, so it falls right. All 5 fall, last at tick 5.
Example 3
- Input:
- [[0,2,4,6,9,15],[2,2,2,2,2,5],[[0,0,"R"],[3,1,"L"],[8,5,"L"]]]
- Output:
- [5,8,[4]]
- Explanation
- A chain of height-2 dominoes with gaps of 2 falls 0, 1, 2, 3 at ticks 0, 2, 4, 6 (an exact reach counts). The push on domino 1 at tick 3 is ignored because it is already down. Domino 3 reaches position 8, which falls short of the domino at 9, and the domino at 15 pushed left at tick 8 reaches only position 10. Domino 4 stays standing: 5 fall, last tick 8.
Constraints
- 1 ≤ positions.length ≤ 150; positions.length == heights.length
- 0 ≤ positions[i] ≤ 109, strictly increasing; 1 ≤ heights[i] ≤ 109
- 0 ≤ pushes.length ≤ 20; 0 ≤ tick ≤ 109; 0 ≤ index < positions.length