Push Dominoes

Problem Statement

The problem involves a sequence of n dominoes, each positioned vertically upright. We initially push some of the dominoes either to the left ('L') or to the right ('R'). Those dominoes that are not pushed remain in the upright position, denoted by '.'.

This initiating action sets off a cascade where every second, dominos already tilting exert force on their immediate neighbors. If a domino falls to the left, it tends to push the domino directly to its left (if any) in the same direction, and similarly for the right. If a domino is subjected to forces from both the left and the right, it remains upright due to the equilibrium of these opposing forces. It is also worth noting that once a domino starts falling or has fallen, it doesn't exert any additional force on others that are already falling in its direction.

Given a string representing the initial state of the domino array, the goal is to compute the final state of the dominoes after all movements have ceased due to the cascading impact.

Examples

Example 1

Input:

dominoes = "RR.L"

Output:

"RR.L"

Explanation:

The first domino expends no additional force on the second domino.

Example 2

Input:

dominoes = ".L.R...LR..L.."

Output:

"LL.RR.LLRRLL.."

Constraints

• n == dominoes.length
• 1 <= n <= 105
• dominoes[i] is either 'L', 'R', or '.'.

Approach and Intuition

To solve this problem, the main idea is to simulate the sequential tipping of dominoes influenced by their neighbors. Here's the natural approach broken down:

1. Traverse the string representing the initial domino state from left to right to propagate rightward forces. Keep track of the last seen 'R' domino; when encountering a '.', decide its state based on its distance from the last 'R' without any intervening 'L'.
2. Similarly, traverse the domino string from right to left to propagate leftward forces. Track the last seen 'L' domino and determine the state of '.' based on its proximity to this 'L', given no intervening 'R'.
3. Consider positions with conflicting instructions from step 1 and 2. For example, if a domino receives a leftward push from one side and a rightward push from the other, it will ultimately stay upright.
4. For untouched dots ('.'), any dot that remains a '.' even after both traversals does not get pushed by any domino, so it remains upright.

Using the two examples provided:

• For "RR.L", the result directly is "RR.L" as the first two 'R's only affect themselves, and 'L' remains unaffected by anything to its right.
• In ".L.R...LR..L..", traversing from left bring the influences of 'L' and 'R' into coordination, tipping some dominoes based on their proximity to the nearest push, and multiple passes ensure every domino falls as per the influence exerted by its neighbors. The result is a cascading effect, ultimately stabilizing at "LL.RR.LLRRLL..".

Solutions

class Solution {
    public String pushDominoes(String dominoes) {
        char[] dominoArray = dominoes.toCharArray();
        int len = dominoArray.length;
        int[] impact = new int[len];
    
        // Fill impact array from left to right
        int currentForce = 0;
        for (int i = 0; i < len; ++i) {
            if (dominoArray[i] == 'R') currentForce = len;
            else if (dominoArray[i] == 'L') currentForce = 0;
            else currentForce = Math.max(currentForce - 1, 0);
            impact[i] += currentForce;
        }
    
        // Fill impact array from right to left
        currentForce = 0;
        for (int i = len - 1; i >= 0; --i) {
            if (dominoArray[i] == 'L') currentForce = len;
            else if (dominoArray[i] == 'R') currentForce = 0;
            else currentForce = Math.max(currentForce - 1, 0);
            impact[i] -= currentForce;
        }
    
        StringBuilder resultBuilder = new StringBuilder();
        for (int f: impact)
            resultBuilder.append(f > 0 ? 'R' : f < 0 ? 'L' : '.');
        return resultBuilder.toString();
    }
}