The Two Crystal Balls Problem 🔮

The problem

Given two crystal balls that will break if dropped from a high enough distance, determine the exact height in which they will break in the most optimized way.

Some of you may have encountered this problem while interviewing or studying DSA. Let’s discuss it and some of its various solutions!

Modelling

Let’s deliberate how we might model this problem with a computer program. We could imagine we have some function with an input list of booleans where the index represents the height and the element’s value at that index indicates whether a ball breaks at that distance.

We also should be aware of the constraints of our problem:

1. we only have two balls
2. once a ball is broken, we cannot break it again

We can model these constraints within our program by translating them to the following rule:

1. At most, we can check only two indices which evaluate to true

Solutioning

At first glance, a naive approach may be to solve this problem with a linear search. We start at the beginning of the list and walk up it one member at a time. Taking a look at each value along the way. Once we find a value that is evaluated as true, then we return the index.

One of the benefits of this solution is that we only have to utilize one of our two balls. The issue however is that, in the worst case, we have to look at every single element of the entire input list — this is not the most optimal approach. The worst-case runtime complexity here is O(n).

function findFirstBreak(levels: boolean[]): number {
    for (let i = 0; i < levels.length; i++) {
        const isBroken = levels[i];
        if (isBroken) {
            return i;
        }
    }

    return -1;
}

Let’s dig deeper…

Upon further thought, we might realize that something like binary search would allow us to come to a more optimal approach. We can’t utilize binary search as it does not lend itself well to the constraints of our problem — at most, we can check only two indices that evaluate to true. Binary search provides no guarantees that the first two checks will peak into a truthy value.

What if we checked the list in jumps? Aha! We are getting closer. Let’s suppose we jump a portion of the list and check the value at that index. If the value at our jumped index is true, then we know the first truthy value must be somewhere between our last check and the new jumped index. This means we could linearly search the range between our last check and our most recent jump to find that first true value. If the value is at the jumped index is false, then we know we need to jump again.

Suppose our jump is 10% of the list. That means we need to linearly search .1n elements. What’s the time complexity of that? It’s O(n) since we will drop the constants. Darn, the runtime complexity is the same as our naive solution.

What if we set our jumps to be a non-proportional amount of the input? Aha! Now, we got it. Checking the list in sqrt(n) jumps means we only have to linearly search sqrt(n) of the list — meaning our solution can achieve a runtime complexity of O(sqrt(n)).

We can implement this in both a recursive and iterative manner. I will provide a recursive implementation, however.

function findFirstBreak(levels: boolean[]): number {
    const jump = Math.floor(Math.sqrt(levels.length));

    function helper(searchStart: number, interval: number): number {
        const currIdx = searchStart + interval;

        if (currIdx >= levels.length) {
            return -1;
        }

        const didBreak = levels[currIdx];
        if (didBreak && interval === 1) {
            return currIdx;
        } else if (didBreak && interval !== 1) {
            return helper(searchStart, 1);
        }

        return helper(currIdx, interval);
    }

    return helper(0, jump);
}