How to solve the 2 crystal balls problem in JS

The 2 crystal balls (or the 2 balls, or the 2 glass balls, or the 2 eggs, or the 2 fragile things) problem is a maths challenge that goes like this:

Given I have two crystal balls and a building with n number of floors, find out the maximum height from which a ball can be dropped without breaking.

In other words, find the first floor that a ball will smash if dropped from.

Let's define our assumptions and constraints

1. The balls' integrity does not diminish when dropped
2. Don't break both balls before you've found out which floor will break them
3. The floors will be represented by a boolean array, where false represents a floor that won't smash our ball and true represents a floor that will smash our ball. E.g. [false, false, false, false, true, true, true, true].

Our plan

If we only had 1 ball, we would only have one option: we'd have to drop the ball from each floor until it smashed. Doing it any other way to improve our running time would mean the ball would smash before we could determine the exact floor that would smash it. Doing it in this way would be linear time, or O(n).

Because we have 2 balls (cough), we can get a much better running time. Our plan is to use the first ball to walk the array in chunks and if our ball smashes, then we use our 2nd ball to walk the array from the start of the previous chunk to our known breakage point. The 'chunk' unit we'll use (I'll explain why at the end) is the sqrt(n) where n is the length of our array.

So, our plan is to walk the array with our first ball by sqrt(n), and if our ball breaks, we go back by sqrt(n) and walk the array with our 2nd ball linearly until that one breaks.

Let's explain with some pseudo code...

Some psuedo code

jumpAmount = square root of array length

i = jumpAmount

loop from i while i < array.length
    if array[i] = smash
        exit loop
    increment i by jumpAmount

decrement i by jumpAmount

loop from 0 to jumpAmount
    if (array[i]) = smash
        return i

return no smash

Real Code

// function takes in a boolean array and returns the
// index at which a ball will smash, or -1
function twoCrystalBalls(floors: boolean[]): number {

    // define our jump / chunk amount as the square root
    // of the array length
    const jumpAmount = Math.floor(Math.sqrt(floors.length));

    // loop through array starting with our jumpAmount
    // and increment by our jumpAmount
    let i = jumpAmount;
    for (; i < floors.length; i += jumpAmount) {

        // if we find a floor where the ball smashes
        // break out the loop
        if (floors[i]) break;
    }

    // decrement our iterator by our jumpAmount
    i -= jumpAmount;

    // walk the array linearly from i
    // a maximum of [jumpAmount] times
    for (let j = 0; j <= jumpAmount && i < floors.length; ++j, ++i) {
        if floors[i] {
            // if we find the floor that breaks our ball
            // return the index
            return i;
        }
    }

    // the ball didn't smash so return -1
    return -1;
}

Time complexity

The biggest question I had with this algorithm was, 'why divide the array by its square root, why not divide in half, or by 10?'. WELL... it's because, if we divided by a fraction, for example 0.25, then our time complexity would be O(1/2n), in which case, we drop our constants so our running time would be O(n) which takes us back to linear time. By dividing the array by its square root, our time complexity becomes O(sqrt(n)). Neat huh? 🤓