838. Push Dominoes

Array Two Pointers String Dynamic Programming Simulation

Time: O(n)

Space: O(n)

Intuition

Simulate forces: propagate R forces rightward and L forces leftward. Each position gets (rightForce, leftForce); compare to determine final state.

Algorithm

1Compute forces[i] from left: R pushes positive force rightward, L resets to 0, L itself gets -INF.
2Compute from right: L pushes negative force leftward.
3Combine: if forces[i]>0 → R, <0 → L, ==0 → '.' (or if R+L, they cancel).

Common Pitfalls

•Forces decay: each step away from the domino, force decreases by 1. Or use two-pass approach treating forces as distances.

838.cs

// Approach: Two-pass force propagation; L→R assigns positive force for 'R', R→L assigns negative force for 'L'; final state determined by net force sign.
// Time: O(n) Space: O(n)

public class Solution
{
    public string PushDominoes(string dominoes)
    {
        int n = dominoes.Length;
        int[] forces = new int[n];

        // Left to Right: Apply 'R' forces
        int force = 0;
        for (int i = 0; i < n; i++)
        {
            if (dominoes[i] == 'R')
                force = n;  // Max possible force
            else if (dominoes[i] == 'L')
                force = 0;  // Reset on encountering 'L'
            else
                force = Math.Max(force - 1, 0);
            forces[i] += force;
        }

        // Right to Left: Apply 'L' forces
        force = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            if (dominoes[i] == 'L')
                force = n;  // Max possible force
            else if (dominoes[i] == 'R')
                force = 0;  // Reset on encountering 'R'
            else
                force = Math.Max(force - 1, 0);
            forces[i] -= force;
        }

        // Build final result based on net force
        char[] result = new char[n];
        for (int i = 0; i < n; i++)
        {
            if (forces[i] > 0)
                result[i] = 'R';
            else if (forces[i] < 0)
                result[i] = 'L';
            else
                result[i] = '.';
        }

        return new string(result);
    }
}

Was this solution helpful?