Toppling Dominoes

Toppling Dominoes is a quite simple yet interesting little puzzle i’ve encountered as a programming exercise in one of my algorithm courses. It is one of those problems that seem complicated at first but have an intuitive and short solution. The problem description is as follows:

You are dealing with a domino set, in which the tiles are of different height. Given an arrangement of tiles, determine how many dominoes will fall after toppling the first (left-most) domino.

  • Input
    • The input starts with an integer that contains the number of dominoes (1 \leq n \leq 10^6).
    • The second line contains n integers h_1,h_2,\hdots,h_n, separated by a space, where h_i denots the height of the i-th domino in the sequence
  • Output
    • You should output a single integer denoting the number of dominoes that fell over assuming that toppling the tile of height h_i causes all tiles at positions j > i such that j-i < h to fall as well.
  • Constraints:
    • You should give an algorithm that returns the solution in O(n)

Ok, now that we know what we have to do lets sketch the problem so we can deduce a solution. We are given some sequence of dominoes and their heights. Lets assume they are given as an array of integers heights[].

We have to somehow find the amount of fallen dominoes after we topple the left-most domino. An initial idea would be to traverse heights[] from left to right and, at position i, move to the rightmost position that we can reach. We could recursively call some fall-distance function that tells us how far the dominoes fall if domino i falls. This would look something like this:

    \begin{align*}fallDist[i] &= fallDist[j]  \;\;\;  \text{with} \;\;\; j = \max_{j' - i < h_i}\{j'>i\}\\fallDist[n'] &= n \;\;\; \forall n' \geq n\end{align*}

The problem with this approach is that we cannot just consider the right-most domino that topples after domino i fell. This is because there might be another domino between i and j (lets call it k) that obviously topples as well if every domino up to j topples. And k might be that big that it “reaches” further than j. Let’s visualize this problem for better understanding:

Assume that we want to find the fall-distance here
Our approach would only consider the rightmost domino and therefore ignore the green one
But that the green one falls as well is crucial since it leads to more dominoes falling on the right

So as we’ve seen it is not sufficient to only consider the falling domino furthest to the right. We have to find the one domino between i and j that reaches the furthest to the right. We can easily modify our formula to take account of that

    \begin{align*}fallDist[i] &= fallDist[j]  \;\;\;  \text{with} \;\;\; j \;\; \text{s.d} \;\; j \in  \{j' : j' - i < h_i \wedge  j'>i \} \;\; \text{and} \; j' + h_{j'} \;\; \text{max.}\\fallDist[n'] &= n \;\;\; \forall n' \geq n \end{align*}

Below is a java implementation of the fallDist method that we have specified above. Note that i’ve chosen an iterative implementation over a recursive one to prevent stack-overflows for bigger domino sequences. The main idea however, remains the same.

//Stores the position of the leftmost domino that did not fall, it is crucial to always limit
//by the amount of dominoes that we actually have
private static int toppledUpTo

public static int dominoFallDistance(int[] heightSequence) {
      toppledUpTo = Math.min(heightSequence[0], heightSequence.length);
      
      for(int i = 1; i<toppledUpTo; i++) {
        toppledUpTo = rightmostFallingDomino(i, heightSequence)
      }
      
      return toppledUpTo;
}

private static int rightmostFallingDomino(int fallStartPosition, int[] heightSequence) {
      int rightmostPosition = Math.max(fallStartPosition + heightSequence[fallStartPosition], toppledUpTo);
      int rightmostClamped = Math.min(rightmostPosition, heightSequence.length);
      return rightmostClamped                
}

All that is left to do now is to handle I/O by building the heights[] array and returning fallDist(int[] heights) and we are done.

Runtime analysis:
Just to make sure that we’ve met the constraints of the exercise, lets quickly analyze runtime of our solution. We traverse the heights[] array linearly from left to right. For each element we update the toppledUpTo variable, which takes some basic arithmetic operations and therefore takes O(1). So we have a total runtime of

    \begin{align*}n * O(1) = O(n)\end{align*}