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 ( ).
• The second line contains integers , separated by a space, where denots the height of the -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 causes all tiles at positions such that to fall as well.
• Constraints:
• You should give an algorithm that returns the solution in 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 .

We have to somehow find the amount of fallen dominoes after we topple the left-most domino. An initial idea would be to traverse from left to right and, at position , 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 falls. This would look something like this: The problem with this approach is that we cannot just consider the right-most domino that topples after domino fell. This is because there might be another domino between and (lets call it ) that obviously topples as well if every domino up to topples. And might be that big that it “reaches” further than . Let’s visualize this problem for better understanding:

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 and that reaches the furthest to the right. We can easily modify our formula to take account of that 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, heightSequence.length);

for(int i = 1; i<toppledUpTo; i++) {
toppledUpTo = rightmostFallingDomino(i, heightSequence)
}

}

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 array and returning 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 array linearly from left to right. For each element we update the variable, which takes some basic arithmetic operations and therefore takes . So we have a total runtime of 