algoadvance

Leetcode 838. Push Dominoes

Problem Statement

You have n dominoes in a line, and each domino is either upright ('.'), tilting to the left ('L'), or tilting to the right ('R'). Given a string dominoes representing the initial state, return a string representing the final state of the dominoes after pushing and toppling over.

Clarifying Questions

  1. Can multiple R and L dominoes influence a single upright domino at the same time?
  2. How do dominoes behave when they are influenced by both L and R forces at the same time?
  3. Are the inputs guaranteed to be valid with only characters '.', 'L', and 'R'?

Assuming the answers:

  1. Yes, each upright domino can be influenced by its neighbors.
  2. If a domino is influenced by both L and R at the same time, it remains upright.
  3. Yes, the inputs are guaranteed to be valid.

Strategy

  1. Traverse the domino string and look for segments of continuous upright dominoes ('.') that are bounded by L and R.
  2. Identify the influences on each segment:
    • If a segment is only affected by R on the left, the dominoes fall right.
    • If a segment is only affected by L on the right, the dominoes fall left.
    • If a segment is affected by both R and L, balance the forces:
      • Dominoes equidistant from R and L remain upright.
      • Dominoes closer to R fall to the right, and those closer to L fall to the left.
  3. Construct the final string based on these influences.

Code

#include <iostream>
#include <string>
#include <vector>

std::string pushDominoes(std::string dominoes) {
    int n = dominoes.length();
    std::vector<int> forces(n, 0);
    
    int force = 0;
    // Traverse left to right to apply forces from 'R'
    for (int i = 0; i < n; ++i) {
        if (dominoes[i] == 'R') {
            force = n;  // start with the maximum force
        } else if (dominoes[i] == 'L') {
            force = 0;  // no force from right after an 'L'
        } else {
            force = std::max(force - 1, 0);  // decrease force gradually
        }
        forces[i] += force;
    }
    
    force = 0;
    // Traverse right to left to apply forces from 'L'
    for (int i = n - 1; i >= 0; --i) {
        if (dominoes[i] == 'L') {
            force = n;  // start with the maximum force
        } else if (dominoes[i] == 'R') {
            force = 0;  // no force from left after an 'R'
        } else {
            force = std::max(force - 1, 0);  // decrease force gradually
        }
        forces[i] -= force;
    }
    
    // Determine the final state of the dominoes
    std::string result(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 result;
}

int main() {
    std::string dominoes = ".L.R...LR..L..";
    std::string result = pushDominoes(dominoes);
    std::cout << "Result: " << result << std::endl;
    return 0;
}

Time Complexity

  1. Time Complexity: O(n)
    • We traverse the string a total of two times, once for each direction of force application.
    • Each traversal takes linear time O(n), making the total time complexity linear.
  2. Space Complexity: O(n)
    • We use an additional array to store forces acting on each domino, which results in an O(n) space complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI