Where will the crystal ball break?

Let’s consider the collection of various distances as a boolean array. In this array, an entry is true if the crystal ball breaks at that distance, and false if it doesn’t. 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 at all). Why so? Because if a ball breaks at a certain distance, it’ll surely break in distances greater than the previous one. We have to find the index of the first entry where the value is true.

Let’s try linear search

For linear search, we’ll need to check each entry to see if it’s true, one after another. In the worst case, only the last entry is true, and we’ll have to go through the whole array. While this works, the complexity is O(n) in the worst case.

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

  return -1;
}

How about binary search?

It may look like a binary search will be considerably better, but the array being boolean has a major impact on the performance. Let’s say we have an array like this [false, false, false, true, true]. In typical Binary Search fashion, let’s halve the array and check the entry.

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.
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 increases proportionately. So it’s evident that the number of iterations is roughly half of the array, so O(n/2), which is equivalent to O(n) without considering the constant factor of 1/2.

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;
}

Can we optimize this?

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 of (√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.
If we find a false entry, we can iterate from our current index to the last iteration index where we found the false entry, and the first true entry should be somewhere in between.

For 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 the 4th index in the 2nd iteration. As the entry itself isn’t the first true entry, we can iterate backwards from the 4th index to the last false index. This inner iteration will run √n times at worst-case, but we’ll find the result, guaranteed!

In terms of complexity, as we’re jumping the√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.

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;
}

Final words

This hybrid approach balances the trade-off between speed and precision, making it ideal for problems where a critical threshold must be identified efficiently.