Push Dominoes
There are n dominoes in a line, and each domino is initially placed vertically upright. At the beginning, some dominoes are simultaneously pushed either to the left or to the right.
After each second:
- Each domino falling to the left pushes the adjacent domino on its left.
- Each domino falling to the right pushes the adjacent standing domino on its right.
When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.
For this problem, a falling domino expends no additional force on a domino that is falling or already fallen.
You are given a string dominoes representing the initial state:
dominoes[i] = 'L'if thei^thdomino has been pushed to the left.dominoes[i] = 'R'if thei^thdomino has been pushed to the right.dominoes[i] = '.'if thei^thdomino has not been pushed.
Return a string representing the final state.
Example 1
Input
dominoes = "RR.L"Output
"RR.L"The first domino expends no additional force on the second domino.
Example 2
Input
dominoes = ".L.R...LR..L.."Output
"LL.RR.LLRRLL.."The pushes propagate through the standing dominoes to produce the final stable state.
Constraints
- n == dominoes.length
- 1 <= n <= 10^5
- dominoes[i] is either 'L', 'R', or '.'.
Asked at 5 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.