First Failing Build

EasyBinary Search

Problem

A CI system ran its test suite on a long sequence of builds. Once a regression was introduced, every later build also failed. The results are given as failed, where failed[i] is true if build i failed.

The array is therefore some false values followed by some true values. Return the index of the first failing build, or -1 if every build passed.

Example 1

Input:
failed = [false, false, true, true]
Output:
2

Builds 0 and 1 passed; build 2 is the first failure.

Example 2

Input:
failed = [false, false]
Output:
-1

Example 3

Input:
failed = [true]
Output:
0

Constraints

  • 0 ≤ failed.length ≤ 10^5
  • failed is a run of false followed by a run of true (either run may be empty).

Hint

Show the first hint

In a real bisect you pay for every build you check. How few can you look at?

Walkthrough

How to approach it

01Clarify before coding

  • Is it guaranteed that a failure is never followed by a pass? Yes, that is what makes binary search valid.
  • What if nothing failed? Return -1.
  • Can the list be empty? Yes: -1.

02Brute force

Scan from the start and return the first index where failed[i] is true.

Cost: O(n) checks. If checking a build means running a 20-minute test suite, a scan over 10^5 builds is out of the question; binary search needs 17.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.