Push Dominoes

Problem Description

Given a string representing dominoes where each character is either 'L' (pushed left), 'R' (pushed right), or '.' (upright), determine the final state after all dominoes have fallen. Each second, a domino falling to the left pushes the adjacent left domino, and a domino falling to the right pushes the adjacent right domino. When a domino receives forces from both sides, it remains upright.

Key Insights

• The forces from dominoes falling right propagate to the right, while forces from dominoes falling left propagate to the left.
• By simulating these forces in two passes (left-to-right and right-to-left) and then comparing the net force at each domino, we determine its final direction.
• Use an array (or list) to store the cumulative force from both directions.
• Edge cases occur when forces cancel out, resulting in a domino staying upright.

Space and Time Complexity

Time Complexity: O(n) because each pass over the string takes linear time.
Space Complexity: O(n) for storing the forces for each domino.

Solution

The solution uses two passes:

1. In the left-to-right pass, simulate the force from dominoes falling right. When a domino 'R' is encountered, assign maximum force (using n as a high constant), and decrement the force by 1 for each subsequent domino until a 'L' is found (which resets the force).
2. In the right-to-left pass, simulate force from dominoes falling left similarly.
3. For each domino, the net force is the difference between the rightward and leftward forces. If positive, the domino falls right ('R'); if negative, it falls left ('L'); if zero, it remains upright ('.').

Data structures:

• An array (or list) to store net forces.
• Simple iteration with constant time operations per domino.

Code Solutions