Given two crystal balls that will break if dropped from a high enough distance, determine the exact spot in which it will break in the most optimised way.

Prerequisite: Binary Search, Big-O Notation

Let’s consider the collection of various distances as a boolean array. In this array, an entry is true if the crystal ball will break at that distance, and false if the ball will not break. The false and true entries are contiguous, so the array will be like this, [false, false, false, true, true] or [false, true, true], and true entries will always come after false entries (if true entries exist). We have to find the index of the first entry where the value is true.

Linear Search will work but needs O(n) time.

• We’ll go through each entry and check if it’s true. In the worst case, only the last entry is true, and we’ll have to go through the whole array.

// O(n)
function solution(breaks: boolean[]): number {
    for (let index = 0; index < breaks.length; index++) {
        if (breaks[index]) return index;
    }

    return -1;
}

Binary Search will also need O(n) time.

• Consider an array like this [false, false, false, true, true]. In typical Binary Search fashion, let's halve the array and check the entry.

  1. If the entry is true, how can we determine if this is the first true entry? We have to go backwards in the array from our current position until we find a false and the last true index is our result.

  2. If the value is false we’ll move to the right half. We keep doing this until we find a true value, and then move to step 1.

• To measure the complexity, let’s assume a worst-case where all the values are true. For such an array of length 1000, the loops will run exactly 502 times. For 10000, it becomes 5002, and it goes on proportionately. So we can see that the number of iterations is roughly half, so it’s O(n/2), which is equivalent to O(n) without the constant factor.

// O(n/2) => O(n)
function solution(breaks: boolean[]): number {
    let lo = 0;
    let resultIndex = null;

    while (lo < breaks.length - 1) {
        const mid = Math.floor(lo + (breaks.length - lo) / 2);
        if (!breaks[mid]) {
            lo = mid;
            continue;
        }

        resultIndex = mid;
        while (breaks[resultIndex]) {
            --resultIndex;
        }
        break;
    }

    return resultIndex ? resultIndex + 1 : -1;
}

Optimised Linear Search can do this in O(√n) time!

• Strategy: What if, unlike linear search where we go over the entries one by one, we jump a certain distance in each iteration, and then go back a bit if we already crossed the first true entry? The happy path would look like this,

  • We’ll start iterating from the beginning of the array and jump a certain amount (√n) in each iteration.

    • If we find a true entry, we know for sure that the entry itself or some other entry before it will be the first true entry.

      • We iterate from our current index to the last iteration index where we found the false entry, and the first true entry will be somewhere in between.

• Example: Let’s say we have an array like [false, false, false, true, true, true]. Here, if we jump by √n each time from the 0th index, we’ll find a true entry at 4th index in the 2nd iteration. As the entry itself isn’t the first true entry, we can iterate backwards from 4th index to the last false index. This inner iteration will run √n times at worst-case, but we'll find the result, guaranteed!

• Complexity: As we’re jumping √n distance each time, the maximum number of iterations can be n/√n. If the jump is successful, that is we’ve found a true value, then we’re iterating a partial array with a length of √n. So the total number of iterations is (n/√n) + √n, which denotes the complexity is O(√n). This is significantly less than the Linear/Binary Search approach.

// O(√n)
function solution(breaks: boolean[]): number {
    const jumpAmount = Math.floor(Math.sqrt(breaks.length));

    for (
        let outerIndex = 0;
        outerIndex < breaks.length;
        outerIndex += jumpAmount
    ) {
        if (!breaks[outerIndex]) continue;
        for (
            let innerIndex = outerIndex;
            innerIndex >= outerIndex - jumpAmount;
            innerIndex--
        ) {
            if (!breaks[innerIndex]) {
                return innerIndex + 1;
            }
        }
    }

    return -1;
}