Statement

The latest version of a software product has failed the quality check. Because each version builds on the previous one, all versions developed after a bad version are also considered bad. You are given n versions identified by integers $[1, 2,3, \dots, n]$ , and an API function isBadVersion(version) that returns TRUE if a given version is bad.

Your task is to find the first bad version that causes all subsequent versions to fail while minimizing the number of API calls.

Constraints:

$1 \leq$ first bad version $\leq$ n $\leq 10^5$

Sliding Window

Two Pointers

Fast and Slow Pointers

Merge Intervals

In-place Reversal of a Linked List

Two Heaps

K-way merge

Top K Elements

Modified Binary Search

Subsets

Greedy Techniques

Backtracking

Dynamic Programming

Cyclic Sort

Topological Sort

Matrices

Stacks

Graphs

Tree Depth First Search

Tree Breadth First Search

Trie

Hash Maps

Knowing What to Track

Union Find

Custom Data Structures

Bitwise Manipulation

Challenge Yourself

Conclusion

First Bad Version

Statement

Examples