Skip to main content

O(log N), O(sort)

The pure logarithmic-time family: classic search, the bisect boundary toolkit, and the dozens of variants that are really just one of those templates with a twist. When the input isn't sorted, an O(N log N) sort first still keeps us in this bucket.

The Classic Binary Search Algorithm​

The single lower-bound template that solves almost everything else on this page.

702. Search in a Sorted Array of Unknown Size​

Medium·
Explanation

This is still the standard lower-bound binary search, but the array length is hidden behind an ArrayReader interface - we can only call reader.get(i), and out-of-range indices return a sentinel large value. So the problem splits into two phases.

Phase 1 - locate a boundary by doubling:

  • Start with a tiny window lo, hi = 0, 1.
  • While reader.get(hi) is still smaller than target, the target lies further right, so jump the window forward: lo = hi then hi <<= 2 (multiply by four).
  • Doubling (here quadrupling) grows the window exponentially, so after O(log T) steps the target is guaranteed to sit inside [lo, hi], where T is the target's index.

Phase 2 - ordinary binary search:

  • With a valid [lo, hi] range, run the familiar lower-bound loop: mid = lo + (hi - lo) // 2, move lo = mid + 1 when reader.get(mid) < target, otherwise hi = mid.
  • When the loop ends, lo is the leftmost index whose value is >= target; a final equality check confirms whether it is actually the target.
Analysis
Time
O(2 log T)
  • T is the index of the target value.
  • The boundary-doubling phase takes O(log T) jumps, and the binary search over the found range is a separate O(log T) pass - two same-order phases, O(2 log T).
Space
O(1)
  • Only the lo, hi, and mid indices are tracked.
FIG. 702 SEARCH IN A SORTED ARRAY OF UNKNOWN SIZE● INTERACTIVE
visualization loads as you reach it
class Solution:
def search(self, reader: "ArrayReader", target: int) -> int:
lo, hi = 0, 1
# Find the boundary indices such that the target lies in-between (low, high)
while target > reader.get(hi):
lo = hi
hi <<= 2
# Typical binary search
while lo < hi:
mid = lo + (hi - lo) // 2
if reader.get(mid) < target:
lo = mid + 1
else:
hi = mid
return lo if reader.get(lo) == target else -1

74. Search a 2D Matrix​

Medium·
Explanation

The matrix is row-sorted and each row's first value exceeds the previous row's last value - which means the row-major flattening of the matrix is itself one fully sorted 1D array. So we can run a single binary search over the virtual range [0, rows * cols - 1] without ever materializing the flat array.

The trick:

  • A flat offset i maps back to a cell with matrix[i // col][i % col] - integer division picks the row, the remainder picks the column.
  • With that accessor, the problem collapses to the exact lower-bound template from 704: shrink [lo, hi] until one candidate remains, then check equality.
Analysis
Time
O(log(M·N))
  • M and N are the row and column counts.
  • Binary search runs over M·N virtual cells, halving the range each step.
Space
O(1)
  • The flat array is never built; only lo, hi, and mid offsets are stored.
FIG. 74 SEARCH A 2D MATRIX● INTERACTIVE
visualization loads as you reach it
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
row, col = len(matrix), len(matrix[0])
get = lambda i: matrix[i // col][
i % col
] # access an element of matrix using offset 'i'
lo, hi = 0, row * col - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if get(mid) < target:
lo = mid + 1
else:
hi = mid
return get(lo) == target

Bisect Algorithms​

Four reusable insert-position primitives. Everything in the next sections calls one of these.

Bisect Left​

Easy·

Bisect Left

Explanation

bisect_left returns the position at which target should be inserted to keep the array sorted, choosing the leftmost valid slot when duplicates of target are already present. It is the lower-bound form of binary search returning an index rather than a boolean.

What the answer means:

  • If target is present, the result is the index of its first (leftmost) occurrence.
  • If target is smaller than every element, the result is 0.
  • If target is greater than every element, the result is len(arr) (one past the end).

How it works:

  • hi arrives exclusive and is turned into an inclusive bound hi = (hi or len(arr)) - 1.
  • An empty range (lo == hi + 1) returns -1.
  • A quick check arr[hi] < target short-circuits the "greater than all" case to hi + 1.
  • The core loop runs the standard lower-bound invariant: when arr[mid] < target move right (lo = mid + 1), otherwise keep mid as a candidate (hi = mid).
Analysis
Time
O(log N)
  • N is the number of elements in the array.
  • Each iteration halves the candidate range.
Space
O(1)
  • Only the lo, hi, and mid indices are tracked.
FIG. BISECT LEFT● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo

Bisect Left Reverse​

Easy·

Bisect Left Reverse

Explanation

bisect_left_rev is the lower-bound insert for a descending array. It mirrors bisect_left, but every comparison flips direction because larger values now sit to the left.

What the answer means:

  • If target is present, the result is the index of its leftmost occurrence within the descending order.
  • If target is larger than every element, the result is 0.
  • If target is smaller than every element, the result is len(arr).

How it works:

  • hi arrives exclusive and becomes inclusive via hi = (hi or len(arr)) - 1.
  • An empty range (lo == hi + 1) returns -1.
  • The short-circuit becomes arr[hi] > target (the descending equivalent of "beyond all elements").
  • In the loop the decision flips: when arr[mid] > target move right (lo = mid + 1), otherwise keep mid (hi = mid).
Analysis
Time
O(log N)
  • N is the number of elements in the array.
  • Each iteration halves the candidate range.
Space
O(1)
  • Only the lo, hi, and mid indices are tracked.
FIG. BISECT LEFT REVERSE● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_left_rev(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] > target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] > target:
lo = mid + 1
else:
hi = mid
return lo

Bisect Right​

Easy·

Bisect Right

Explanation

bisect_right returns the position at which target should be inserted to keep the array sorted, choosing the rightmost valid slot when duplicates of target are already present. It is the upper-bound form of binary search.

What the answer means:

  • If target is present, the result is one past its last (rightmost) occurrence.
  • If target is smaller than every element, the result is 0.
  • If target is greater than every element, the result is len(arr).

How it works:

  • hi stays inclusive here (hi = hi or len(arr)), because the answer can legitimately be len(arr).
  • An empty range (lo == hi) returns -1.
  • A short-circuit arr[hi - 1] < target handles the "greater than all" case by returning hi.
  • The key difference from bisect_left: we advance lo even when equal (arr[mid] <= target), so the search slides past every duplicate to the rightmost boundary.
Analysis
Time
O(log N)
  • N is the number of elements in the array.
  • Each iteration halves the candidate range.
Space
O(1)
  • Only the lo, hi, and mid indices are tracked.
FIG. BISECT RIGHT● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_right(self, arr, target, lo: int = 0, hi: int = None):
# hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
hi = hi or len(arr)
if lo == hi: # if array is empty
return -1
if arr[hi - 1] < target:
return hi
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo

Bisect Right Reverse​

Easy·

Bisect Right Reverse

Explanation

bisect_right_rev is the upper-bound insert for a descending array. It mirrors bisect_right, but every comparison flips direction because larger values now sit to the left.

What the answer means:

  • If target is present, the result is one past its rightmost occurrence within the descending order.
  • If target is larger than every element, the result is 0.
  • If target is smaller than every element, the result is len(arr).

How it works:

  • hi stays inclusive (hi = hi or len(arr)), since the answer can be len(arr).
  • An empty range (lo == hi) returns -1.
  • The short-circuit becomes arr[hi - 1] > target, returning hi.
  • The descending decision advances lo even when equal (arr[mid] >= target), sliding past every duplicate to the rightmost boundary.
Analysis
Time
O(log N)
  • N is the number of elements in the array.
  • Each iteration halves the candidate range.
Space
O(1)
  • Only the lo, hi, and mid indices are tracked.
FIG. BISECT RIGHT REVERSE● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_right_rev(self, arr, target, lo: int = 0, hi: int = None):
# hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
hi = hi or len(arr)
if lo == hi: # if array is empty
return -1
if arr[hi - 1] > target:
return hi
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] >= target:
lo = mid + 1
else:
hi = mid
return lo

Bisect Derivatives​

One bisect call, lightly post-processed.

744. Find Smallest Letter Greater Than Target​

Easy·
Explanation

We want the smallest letter strictly greater than target in a sorted letters array, wrapping back to the front if target is at or past the last letter. Because duplicates are allowed, we must glide past every copy of target and land just to its right - exactly what bisect_right does.

The two steps:

  • bisect_right(letters, target) returns the index one past the rightmost occurrence of target (or the lower bound when target is absent), which is the first letter strictly greater than target.
  • That index can equal len(letters) when target is at or beyond the last letter, so index % len(letters) wraps around to the first element.
Analysis
Time
O(log N)
  • N is the number of letters.
  • A single bisect_right runs in logarithmic time.
Space
O(1)
  • Only scalar indices are tracked.
FIG. 744 FIND SMALLEST LETTER GREATER THAN TARGET● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_right(self, arr, target, lo: int = 0, hi: int = None):
# hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
hi = hi or len(arr)
if lo == hi: # if array is empty
return -1
if arr[hi - 1] < target:
return hi
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
index = self.bisect_right(letters, target)
return letters[index % len(letters)]

35. Search Insert Position​

Easy·
Explanation

Given a sorted array with distinct values, return the index of target if present, otherwise the index where it would be inserted to keep the array sorted. Since duplicates are not allowed, the leftmost and rightmost insert positions coincide, so a single bisect_left answers the question directly.

Why bisect_left:

  • When target is present, bisect_left returns its exact index.
  • When target is absent, it returns the first index whose value is >= target - precisely the slot where target belongs.
  • If target exceeds every element, the result is len(nums) (insert at the end).
Analysis
Time
O(log N)
  • N is the number of elements in nums.
  • A single bisect_left runs in logarithmic time.
Space
O(1)
  • Only scalar indices are tracked.
FIG. 35 SEARCH INSERT POSITION● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def searchInsert(self, nums: List[int], target: int) -> int:
return self.bisect_left(nums, target)

362. Design Hit Counter​

Medium·
Explanation

We design a counter that records hit timestamps and reports how many hits happened in the past 300 seconds (the window [timestamp - 299, timestamp]). Because timestamps arrive in chronological order, the internal hits list is always sorted, which lets us answer each query with binary search instead of a scan.

The operations:

  • hit(timestamp) simply appends to self.hits. Since timestamps are monotonically non-decreasing, the list stays sorted - an O(1) operation.
  • getHits(timestamp) finds the first hit still inside the window using bisect_left(self.hits, timestamp - 300 + 1). Everything from that index to the end of the list is within the last 300 seconds, so the count is len(self.hits) - index.

Why bisect_left:

  • It returns the leftmost index whose value is >= timestamp - 299, i.e. the oldest hit that still counts. Hits older than the window sit to its left and are excluded.

This is a stateful design class whose behavior depends on a sequence of method calls, so the playground replays a scripted sequence of hit/getHits calls and shows the timestamp list growing and the binary-search window sliding.

Analysis
Time
O(log N)
  • hit is O(1) - a single append, and the list stays sorted because timestamps are monotonically increasing.
  • getHits is O(log N) - it locates the window start with binary search, which dominates the class's worst-case per-call cost.
Space
O(N)
  • N is the number of recorded hits stored in self.hits.
FIG. DESIGN HIT COUNTER● INTERACTIVE
visualization loads as you reach it
class HitCounter:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def __init__(self):
self.hits = []
 
def hit(self, timestamp: int) -> None:
self.hits.append(timestamp)
 
def getHits(self, timestamp: int) -> int:
index = self.bisect_left(self.hits, timestamp - 300 + 1)
return len(self.hits) - index if 0 <= index < len(self.hits) else 0

Bisect Left & Right​

Call both boundaries and work with the [left, right) span between them.

34. Find First and Last Position of Element in Sorted Array​

Medium·
Explanation

The whole range of target occupies a contiguous block in the sorted array. Pin down its two edges with two lower-bound searches and the answer falls out.

Two boundary searches:

  • bisect_left returns the leftmost index where target could sit - the first occurrence if target exists.
  • bisect_right returns the index one past the last occurrence of target.

Reading the result:

  • When target is absent, both searches land on the same insertion point, so left == right. That single equality covers every miss: below the smallest element, above the largest, or in a gap.
  • When target is present, [left, right - 1] is exactly the inclusive first/last index pair.
Analysis
Time
O(log N)
  • N is the number of elements in the array.
  • Both bisect_left and bisect_right run a halving loop, so each takes log N steps.
Space
O(1)
  • Only scalar indices are tracked, independent of input size.
FIG. 34 FIND FIRST AND LAST POSITION OF ELEMENT IN SORTED ARRAY● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
 
def bisect_right(self, arr, target, lo: int = 0, hi: int = None):
# hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
hi = hi or len(arr)
if lo == hi: # if array is empty
return -1
if arr[hi - 1] < target:
return hi
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo
def searchRange(self, nums: List[int], target: int) -> List[int]:
left = self.bisect_left(nums, target)
right = self.bisect_right(nums, target)
if not nums or left == right: # left==right when the element is not present
return [-1, -1]
return [left, right - 1]

2089. Find Target Indices After Sorting Array​

Easy·
Explanation

After sorting, every copy of target lands in one contiguous block. The "target indices" are exactly the positions of that block, so we just need its two edges.

Sort, then bound:

  • nums = sorted(nums) puts all equal values together.
  • bisect_left gives the index of the first target.
  • bisect_right gives the index one past the last target.

Building the answer:

  • range(left, right) enumerates every index occupied by target.
  • If target is absent, left == right, so the range is empty and the result is [].
Analysis
Time
O(2 log N + N log N)
  • N is the number of elements in the array.
  • sorted(nums) costs N log N, then bisect_left and bisect_right each binary search the sorted array in log N - two separate O(log N) passes plus the sort, 2 log N + N log N.
Space
O(sort + N)
  • sorted(nums) allocates a new list of N elements, and list(range(left, right)) holds at most N indices.
  • Sorting algorithms are typically O(log n) space (in-place, recursion stack only), but Python's list.sort() (used internally by sorted()) is Timsort, which allocates up to O(n) auxiliary space in the worst case - that's what sort stands for here.
FIG. 2089 FIND TARGET INDICES AFTER SORTING ARRAY● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
 
def bisect_right(self, arr, target, lo: int = 0, hi: int = None):
# hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
hi = hi or len(arr)
if lo == hi: # if array is empty
return -1
if arr[hi - 1] < target:
return hi
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo
def targetIndices(self, nums: List[int], target: int) -> List[int]:
nums = sorted(nums)
left = self.bisect_left(nums, target)
right = self.bisect_right(nums, target)
return list(range(left, right))

1150. Check If a Number Is Majority Element in a Sorted Array​

Easy·
Explanation

A value is the majority element when it occupies more than half the array. In a sorted array every copy of target is contiguous, so counting them is just measuring the width of that block.

Bound the block:

  • bisect_left gives the index of the first target.
  • bisect_right gives the index one past the last target.
  • count = right - left is how many times target appears.

The majority test:

  • Return count > len(nums) / 2. If target is absent the block is empty, so count == 0 and the test fails naturally.
Analysis
Time
O(log N)
  • N is the number of elements in the array.
  • Both bisect_left and bisect_right run a halving loop, so each takes log N steps.
Space
O(1)
  • Only scalar indices and a count are tracked.
FIG. 1150 CHECK IF A NUMBER IS MAJORITY ELEMENT IN A SORTED ARRAY● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
 
def bisect_right(self, arr, target, lo: int = 0, hi: int = None):
# hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
hi = hi or len(arr)
if lo == hi: # if array is empty
return -1
if arr[hi - 1] < target:
return hi
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo
def isMajorityElement(self, nums: List[int], target: int) -> bool:
left = self.bisect_left(nums, target)
right = self.bisect_right(nums, target)
count = right - left
return count > len(nums) / 2

Element Occurrence​

Easy·
Explanation

The number of times target appears in a sorted array is the width of its contiguous block. Find the two edges of that block and subtract.

Bound the block:

  • bisect_left gives the index of the first target.
  • bisect_right gives the index one past the last target.
  • count = right - left is the number of occurrences.

Reporting absence:

  • When target is missing both boundaries coincide, so count == 0; the solution returns -1 to signal "not found".
Analysis
Time
O(2 log n)
  • n = len(nums). findCount calls bisect_left and bisect_right once each, and both run their own halving while lo < hi loop - two separate O(log n) searches, giving 2 log n.
Space
O(1)
  • Only scalar indices (left, right, lo, hi, mid) and count are tracked.
FIG. ELEMENT OCCURRENCE● INTERACTIVE
visualization loads as you reach it
def bisect_left(arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
 
 
def bisect_right(arr, target, lo: int = 0, hi: int = None):
# hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
hi = hi or len(arr)
if lo == hi: # if array is empty
return -1
if arr[hi - 1] < target:
return hi
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo
def findCount(nums: List[int], target: int):
left = bisect_left(nums, target)
right = bisect_right(nums, target)
count = right - left
return count if count != 0 else -1

Slight Variants​

The classic template with the comparison swapped for a derived predicate.

1064. Fixed Point​

Easy·
Explanation

A fixed point is an index where arr[i] == i, and we want the smallest such index. Because the array is sorted with distinct integers, the quantity arr[i] - i is non-decreasing, which makes this a lower-bound search.

The decision:

  • If arr[mid] < mid, the value is still lagging behind its index, so any fixed point must lie strictly to the right -> lo = mid + 1.
  • Otherwise (arr[mid] >= mid), mid could be the first index where the value catches up to its index -> hi = mid.

Confirming the survivor:

  • When the loop ends, lo is the leftmost candidate. Return it only if arr[lo] == lo; otherwise there is no fixed point and we return -1.
Analysis
Time
O(log N)
  • N is the number of elements in the array.
  • Each iteration halves the search range, so the loop runs at most log2(N) times.
Space
O(1)
  • Only the lo, hi, and mid indices are tracked.
FIG. 1064 FIXED POINT● INTERACTIVE
visualization loads as you reach it
class Solution:
def fixedPoint(self, arr: List[int]) -> int:
lo, hi = 0, len(arr) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < mid:
lo = mid + 1
else:
hi = mid
return lo if arr[lo] == lo else -1

374. Guess Number Higher or Lower​

Easy·
Explanation

The search space is the integer range [0, n], and the pre-supplied guess API replaces a direct array comparison. The lower-bound template still applies cleanly.

The probe:

  • guess(mid) returns 1 when our pick is too low, and -1 or 0 when it is too high or exactly right.
  • guess(mid) == 1 means the target lies strictly to the right -> lo = mid + 1.
  • Otherwise mid could be the answer -> hi = mid.

Termination:

  • The loop runs while lo < hi, collapsing to the single surviving candidate, which is the picked number.
Analysis
Time
O(log N)
  • N is the size of the guessing range [1, n].
  • Each call to guess halves the remaining range.
Space
O(1)
  • Only the lo, hi, and mid values are tracked.
FIG. 374 GUESS NUMBER HIGHER OR LOWER● INTERACTIVE
visualization loads as you reach it
class Solution:
def guessNumber(self, n: int) -> int:
lo, hi = 0, n
while lo < hi:
mid = lo + (hi - lo) // 2
if guess(mid) == 1: # 1 if guess is lower than the target
lo = mid + 1
else: # -1 or 0 if guess is greater than or equal to the target
hi = mid
return lo

278. First Bad Version​

Easy·
Explanation

Versions are monotone: once a version is bad, every later version is bad too. That turns the problem into finding the leftmost True in a False...False True...True sequence - exactly the lower-bound template, with the isBadVersion API standing in for an array read.

The probe:

  • isBadVersion(mid) == False means every bad version is strictly to the right -> lo = mid + 1.
  • Otherwise mid is bad and could be the first one -> hi = mid.

Termination:

  • When lo == hi, the survivor is the first bad version.
Analysis
Time
O(log N)
  • N is the number of versions.
  • Each isBadVersion call halves the candidate range.
Space
O(1)
  • Only the lo, hi, and mid values are tracked.
FIG. 278 FIRST BAD VERSION● INTERACTIVE
visualization loads as you reach it
first_bad = 4 # hidden first bad version the judge knows
 
 
def isBadVersion(version):
return version >= first_bad
class Solution:
def firstBadVersion(self, n: int) -> int:
lo, hi = 0, n
while lo < hi:
mid = lo + (hi - lo) // 2
if isBadVersion(mid) == False:
lo = mid + 1
else:
hi = mid
return lo

441. Arranging Coins​

Easy·
Explanation

A full staircase of k rows uses coins(k) = k * (k + 1) / 2 coins. We want the largest k whose staircase still fits inside n, so we binary search the row count over [0, n].

The probe:

  • coins(mid) <= n means mid rows fit, so a taller staircase might also fit -> lo = mid + 1.
  • Otherwise mid overflows -> hi = mid.

Reading the survivor:

  • After the loop lo is the first row count that is too tall (or exactly n).
  • If coins(lo) == n it is a perfect fit; otherwise the last complete row count is lo - 1.
Analysis
Time
O(log n)
  • n is the given coin count.
  • The while lo < hi loop halves the [lo, hi] range of candidate row counts each iteration: O(log n).
Space
O(1)
  • Only the lo, hi, and mid values are tracked.
FIG. 441 ARRANGING COINS● INTERACTIVE
visualization loads as you reach it
class Solution:
def arrangeCoins(self, n: int) -> int:
coins = lambda i: i * (i + 1) / 2
lo, hi = 0, n
while lo < hi:
mid = lo + (hi - lo) // 2
if coins(mid) <= n:
lo = mid + 1
else:
hi = mid
return lo if coins(lo) == n else lo - 1

287. Find the Duplicate Number​

Medium·
Explanation

The values lie in the range [1, n], so in a clean array of length n the element at index i would be exactly i + 1. A duplicate breaks this alignment and shifts everything after it, which makes the mismatch detectable by a lower-bound search.

Sort and compare to expected:

  • nums = sorted(nums) arranges the values in order.
  • expected(i) is the value that index i would hold with no duplicates: i + 1.

The decision:

  • If expected(mid) == nums[mid], no duplicate has appeared at or before mid, so it must lie to the right -> lo = mid + 1.
  • Otherwise the alignment has already broken -> hi = mid.

When the loop ends, lo is the first index where the value no longer matches its expected slot, and nums[lo] is the repeated number.

Analysis
Time
O(log N + N log N)
  • N is the number of elements in the array.
  • sorted(nums) costs O(N log N), and the while lo < hi binary search that follows adds its own O(log N) pass over the sorted array - a distinct, slower-growing term that doesn't collapse into the sort.
Space
O(sort + N)
  • sorted(nums) allocates a new list of size N.
  • Sorting algorithms are typically O(log n) space (in-place, recursion stack only), but Python's list.sort()/sorted() is Timsort, which allocates up to O(n) auxiliary space in the worst case - that's what sort stands for here.
FIG. 287 FIND THE DUPLICATE NUMBER● INTERACTIVE
visualization loads as you reach it
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
nums = sorted(nums)
expected = lambda i: i + 1
lo, hi = 0, len(nums)
while lo < hi:
mid = lo + (hi - lo) // 2
if expected(mid) == nums[mid]:
lo = mid + 1
else:
hi = mid
return nums[lo]

Single Element in a Sorted Array​

Medium·
Explanation

Every element appears twice except one, so the array always has an odd length. The lone element is detectable by the parity of the segment to the right of mid: a clean run of pairs has an even count, and the single element flips that parity.

Aligning mid to a pair boundary:

  • If nums[mid] == nums[mid + 1], mid is the left half of a pair. Step it back with mid -= 1 so the pair is counted whole and the parity argument stays valid.

The decision:

  • right_len = hi - mid measures the right segment.
  • If right_len is odd, the single element lies to the right -> lo = mid + 1.
  • If it is even, the single element is at mid or to its left -> hi = mid.

When the loop ends, lo points at the unique element.

Analysis
Time
O(log n)
  • n is the number of elements in nums.
  • The while lo < hi loop halves the [lo, hi] range each iteration, so it runs at most log2(n) times.
Space
O(1)
  • Only the lo, hi, mid, and right_len scalars are tracked.
FIG. SINGLE ELEMENT IN A SORTED ARRAY● INTERACTIVE
visualization loads as you reach it
def singleNonDuplicate(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] == nums[mid + 1]:
mid -= 1
right_len = hi - mid
if right_len % 2 == 1:
lo = mid + 1
else:
hi = mid
return nums[lo]

Math - Square​

Binary search over a numeric answer range to invert a monotone math function.

69. Sqrt(x)​

Easy·
Explanation

The integer square root is the largest k with k * k <= x. We binary search k over [0, x] using the lower-bound template.

The probe:

  • square(mid) <= x keeps mid as a valid candidate and pushes for a larger root -> lo = mid + 1.
  • Otherwise mid * mid overshoots -> hi = mid.

Reading the survivor:

  • The <= test means lo lands on the first integer whose square is strictly greater than x.
  • If square(lo) == x it is a perfect square; otherwise the floor of the root is lo - 1.
Analysis
Time
O(log N)
  • N is the given number x.
  • Each iteration halves the candidate range of roots.
Space
O(1)
  • Only the lo, hi, and mid values are tracked.
FIG. 69 SQRTX● INTERACTIVE
visualization loads as you reach it
class Solution:
def mySqrt(self, x: int) -> int:
square = lambda i: i * i
lo, hi = 0, x
while lo < hi:
mid = lo + (hi - lo) // 2
if square(mid) <= x:
lo = mid + 1
else:
hi = mid
return lo if square(lo) == x else lo - 1

367. Valid Perfect Square​

Easy·
Explanation

This mirrors finding an integer square root: binary search the candidate root k over [0, num], then check whether the floor of the root squares back to num.

The probe:

  • square(mid) <= num keeps mid valid and reaches for a larger root -> lo = mid + 1.
  • Otherwise mid * mid overshoots -> hi = mid.

The final check:

  • lo lands one past the floor root, so reduce it to the floor: lo if square(lo) == num else lo - 1.
  • The answer is whether that floor root squared equals num.
Analysis
Time
O(log num)
  • num is the input value. Each while lo < hi iteration compares square(mid) against num and halves the [lo, hi] candidate range.
Space
O(1)
  • Only the lo, hi, and mid values are tracked.
FIG. 367 VALID PERFECT SQUARE● INTERACTIVE
visualization loads as you reach it
class Solution:
def isPerfectSquare(self, num: int) -> bool:
square = lambda i: i * i
lo, hi = 0, num
while lo < hi:
mid = lo + (hi - lo) // 2
if square(mid) <= num:
lo = mid + 1
else:
hi = mid
lo = lo if square(lo) == num else lo - 1
return square(lo) == num

633. Sum of Square Numbers​

Medium·
Explanation

We want non-negative integers a and b with a*a + b*b == c. Once a is fixed, b*b is forced to be c - a*a, so the only freedom is the choice of a.

Enumerate a:

  • Since a*a <= c, it is enough to try every a in [0, sqrt(c)].
  • For each a, compute the required b = c - a*a.

Test the complement:

  • b is a valid square iff it is a perfect square, which the folded isPerfectSquare helper decides by binary searching its integer root.
  • If any complement is a perfect square, the answer is True; otherwise False.
Analysis
Time
O(sqrt(c) * log c)
  • c is the given number.
  • The loop runs O(sqrt(c)) times, and each perfect-square check is O(log c).
Space
O(1)
  • Only scalar values are tracked.
FIG. 633 SUM OF SQUARE NUMBERS● INTERACTIVE
visualization loads as you reach it
class Solution:
def isPerfectSquare(self, num: int) -> bool:
square = lambda i: i * i
lo, hi = 0, num
while lo < hi:
mid = lo + (hi - lo) // 2
if square(mid) <= num:
lo = mid + 1
else:
hi = mid
lo = lo if square(lo) == num else lo - 1
return square(lo) == num
def judgeSquareSum(self, c: int) -> bool:
for a in range(0, int(c**0.5) + 1):
b = c - a * a
if self.isPerfectSquare(b):
return True
return False

Missing Elements​

Bisect on a "how many are missing so far" predicate.

268. Missing Number​

Easy·
Explanation

The array holds n distinct values drawn from [0, n], so exactly one value is missing. After sorting, a complete prefix satisfies nums[i] == i; the missing number is the first index where that equality breaks.

Invariant:

  • For every index before the gap, nums[mid] == mid, so mid >= nums[mid].
  • At and after the gap, values are shifted up by one, so mid < nums[mid].

The decision:

  • mid >= nums[mid] means the prefix is still intact, so the gap is to the right -> lo = mid + 1.
  • Otherwise the gap is at or before mid -> hi = mid.

The hi pointer:

  • hi starts at len(nums) because the missing value can be n itself (when 0..n-1 are all present). The hi marker may render one slot past the array, which is expected.
Analysis
Time
O(log n + n log n)
  • n is the number of elements. The binary search over lo/hi/mid is a separate O(log n) phase from the O(n log n) sort - the sort dominates but the binary search is still its own pass.
Space
O(sort)
  • Only the lo, hi, and mid indices are tracked beyond the sort's own working memory.
  • Sorting algorithms are typically O(log n) space (in-place, recursion stack only), but Python's list.sort() is Timsort, which allocates up to O(n) auxiliary space in the worst case - that's what sort stands for here.
FIG. 268 MISSING NUMBER 2● INTERACTIVE
visualization loads as you reach it
class Solution:
def missingNumber(self, nums: List[int]) -> int:
nums.sort()
lo, hi = 0, len(nums)
while lo < hi:
mid = lo + (hi - lo) // 2
if mid >= nums[mid]:
lo = mid + 1
else:
hi = mid
return lo

1060. Missing Element in Sorted Array​

Medium·
Explanation

In a gap-free run starting at nums[0], index i would hold nums[0] + i. The number of values missing up to index i is therefore missing(i) = nums[i] - nums[0] - i, a non-decreasing quantity. We binary search for the first index where the running count of missing numbers reaches k.

The decision:

  • missing(mid) < k means the k-th missing value still lies further right -> lo = mid + 1.
  • Otherwise the count is at least k, so the boundary is at or before mid -> hi = mid.

Reading the answer:

  • After the loop, index lo - 1 is the last position before the count reaches k.
  • The k-th missing number is nums[lo - 1] plus the remaining shortfall k - missing(lo - 1).

The hi pointer:

  • hi starts at len(nums) because the answer can exceed nums[-1]. The hi marker may render one slot past the array, which is expected.
Analysis
Time
O(log N)
  • N is the number of elements.
  • Each iteration halves the candidate index range.
Space
O(1)
  • Only the lo, hi, and mid indices are tracked.
FIG. 1060 MISSING ELEMENT IN SORTED ARRAY● INTERACTIVE
visualization loads as you reach it
class Solution:
def missingElement(self, nums: List[int], k: int) -> int:
missing = (
lambda i: nums[i] - nums[0] - i
) # Return the number of missing numbers
lo, hi = 0, len(nums)
# find first greatest `missing` that is <= k
while lo < hi:
mid = lo + (hi - lo) // 2
if missing(mid) < k:
lo = mid + 1
else:
hi = mid
return nums[lo - 1] + (k - missing(lo - 1))

1539. Kth Missing Positive Number​

Easy·
Explanation

The positive integers start at 1, so in a gap-free array index i would hold i + 1. The number of positives missing up to index i is missing(i) = arr[i] - 1 - i, a non-decreasing quantity. We binary search for the first index where that count reaches k.

The decision:

  • missing(mid) < k means the k-th missing positive is still further right -> lo = mid + 1.
  • Otherwise the count is at least k, so the boundary is at or before mid -> hi = mid.

Reading the answer:

  • Index lo - 1 is the last position before the count hits k.
  • The answer is arr[lo - 1] plus the leftover shortfall k - missing(lo - 1).

The hi pointer:

  • hi starts at len(arr) because the answer can exceed arr[-1]. The hi marker may render one slot past the array, which is expected.
Analysis
Time
O(log N)
  • N is the number of elements.
  • Each iteration halves the candidate index range.
Space
O(1)
  • Only the lo, hi, and mid indices are tracked.
FIG. 1539 KTH MISSING POSITIVE NUMBER● INTERACTIVE
visualization loads as you reach it
class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
missing = lambda i: arr[i] - 1 - i # Return the number of missing numbers
lo, hi = 0, len(arr)
# find first greatest `missing` that is <= k
while lo < hi:
mid = lo + (hi - lo) // 2
if missing(mid) < k:
lo = mid + 1
else:
hi = mid
return arr[lo - 1] + (k - missing(lo - 1))

Rotated Sorted Array​

Locate the pivot (minimum), then search the right half.

Find the Pivot (Minimum)​

Find the Pivot (Minimum)

Explanation

A rotated sorted array is just a sorted array cut at one point and swapped, so the pivot (the minimum) is the only place where the order breaks. This template finds that pivot even when duplicates are present.

The comparison anchor:

  • We never compare against nums[lo] to decide where to move - we compare nums[mid] against nums[hi]. The right end is a reliable reference for the lower-bound invariant.

The three cases:

  • If nums[hi] < nums[mid], the dip is strictly to the right of mid -> lo = mid + 1.
  • If nums[hi] > nums[mid], mid could still be the minimum -> hi = mid.
  • If they are equal we cannot tell which side holds the pivot, so we shrink the window conservatively with hi -= 1. This is what makes duplicates safe (at the cost of O(n) in the worst case).

When the loop ends, lo == hi points at the minimum element's index.

Analysis
Time
O(log N) avg, O(N) worst
  • N is the number of elements in the array.
  • Each iteration normally halves the range. With many duplicates the hi -= 1 branch only shrinks by one, degrading to O(N).
Space
O(1)
  • Only the lo, hi, and mid indices are tracked.
FIG. FIND PIVOT● INTERACTIVE
visualization loads as you reach it
class Solution:
def findPivot(self, nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[hi] < nums[mid]:
lo = mid + 1
elif nums[hi] > nums[mid]:
hi = mid
else:
hi -= 1
return lo

154. Find Minimum in Rotated Sorted Array II​

Hard·
Explanation

The minimum of a rotated sorted array sits exactly at the pivot - the point where the ascending order breaks. Once we know the pivot's index, the answer is just the value there.

Reusing the pivot finder:

  • findPivot runs the lower-bound search comparing nums[mid] against the right end nums[hi], returning the index of the minimum.
  • findMin simply returns nums[pivot].

Why duplicates make this Hard:

  • When nums[mid] == nums[hi] we cannot decide which half holds the minimum, so the pivot finder falls back to hi -= 1. This keeps correctness but degrades the worst case to O(N) (e.g. an array of all equal values).
Analysis
Time
O(log n) avg, O(n) worst
  • n is len(nums).
  • When nums[hi] != nums[mid], each step of findPivot halves the [lo, hi] range: O(log n).
  • When nums[hi] == nums[mid], the hi -= 1 fallback only shrinks the range by one, which can degrade the whole search to O(n) (e.g. an array of all equal values).
Space
O(1)
  • Only the lo, hi, and mid indices are tracked.
FIG. 154 FIND MINIMUM IN ROTATED SORTED ARRAY II● INTERACTIVE
visualization loads as you reach it
class Solution:
def findPivot(self, nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[hi] < nums[mid]:
lo = mid + 1
elif nums[hi] > nums[mid]:
hi = mid
else:
hi -= 1
return lo
def findMin(self, nums: List[int]) -> int:
pivot = self.findPivot(nums)
return nums[pivot]

153. Find Minimum in Rotated Sorted Array​

Medium·
Explanation

With unique elements, finding the minimum of a rotated sorted array collapses to a clean two-way lower-bound search. The minimum is the only element smaller than its predecessor - the pivot where the rotation wraps.

The comparison anchor:

  • We compare nums[mid] against the right end nums[hi], never the left.
  • If nums[mid] > nums[hi], the dip is strictly to the right -> lo = mid + 1.
  • Otherwise mid could still be the minimum -> hi = mid.

No duplicate fallback needed:

  • Because all values are distinct, the equal-to case never happens, so we drop the hi -= 1 branch entirely. That keeps the search strictly O(log N). When the loop ends, nums[lo] is the minimum.
Analysis
Time
O(log n)
  • n = len(nums). Each while lo < hi iteration compares nums[mid] against nums[hi] and halves the [lo, hi] range.
Space
O(1)
  • Only the lo, hi, and mid indices are tracked.
FIG. 153 FIND MINIMUM IN ROTATED SORTED ARRAY● INTERACTIVE
visualization loads as you reach it
class Solution:
def findMin(self, nums: List[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
return nums[lo]

33. Search in Rotated Sorted Array​

Medium·
Explanation

A rotated sorted array is two ascending runs glued together at the pivot (the minimum). If we locate that pivot, the array becomes two ordinary sorted segments and a plain binary search handles each.

Step 1 - find the pivot:

  • findPivot returns the index of the minimum, which is also the boundary between the two ascending runs.

Step 2 - search both halves:

  • Run bisect_left on the left run [0, pivot); if the landing index holds target, return it.
  • Otherwise run bisect_left on the right run [pivot, len(nums)) and check again.
  • If neither lands on target, it is absent -> return -1.

Each binary search is O(log N), so even with the pivot pass the whole thing stays logarithmic.

Analysis
Time
O(log N)
  • N is the number of elements in the array.
  • One pivot search plus two bounded binary searches, each O(log N).
Space
O(1)
  • Only index scalars are tracked.
FIG. 33 SEARCH IN ROTATED SORTED ARRAY● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
 
def findPivot(self, nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[hi] < nums[mid]:
lo = mid + 1
elif nums[hi] > nums[mid]:
hi = mid
else:
hi -= 1
return lo
def search(self, nums: List[int], target: int) -> int:
pivot = self.findPivot(nums)
left = self.bisect_left(nums, target, lo=0, hi=pivot)
if left < len(nums) and nums[left] == target:
return left
right = self.bisect_left(nums, target, lo=pivot, hi=len(nums))
if right < len(nums) and nums[right] == target:
return right
return -1

Peaks in an Array​

Walk uphill: compare the midpoint to its neighbor and move toward the larger side.

162. Find Peak Element​

Medium·
Explanation

A peak is any element strictly greater than both neighbors, and the boundaries are treated as -infinity. We don't need to see the whole array - we only need to follow the local slope uphill, which binary search can do.

The slope test:

  • Compare nums[mid] with its right neighbor nums[mid + 1].
  • If nums[mid] < nums[mid + 1], the slope rises to the right, so a peak must exist there -> lo = mid + 1.
  • Otherwise the slope falls (or mid is itself a peak), so a peak lies at mid or to its left -> hi = mid.

Because lo < hi keeps mid + 1 in range, this never reads out of bounds. When the loop ends, lo indexes a valid peak.

Analysis
Time
O(log N)
  • N is the number of elements in the array.
  • Each iteration discards half the range.
Space
O(1)
  • Only the lo, hi, and mid indices are tracked.
FIG. 162 FIND PEAK ELEMENT● INTERACTIVE
visualization loads as you reach it
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] < nums[mid + 1]:
lo = mid + 1
else:
hi = mid
return lo

852. Peak Index in a Mountain Array​

Medium·
Explanation

A mountain array strictly rises to a single peak and then strictly falls. This is a special case of finding any peak - there is exactly one - so the same slope-following binary search applies.

The slope test:

  • Compare arr[mid] with its right neighbor arr[mid + 1].
  • If arr[mid] < arr[mid + 1], we are still on the ascending side, so the peak is to the right -> lo = mid + 1.
  • Otherwise we are on (or at the top of) the descending side -> hi = mid.

Since the mountain guarantees a single peak, the loop converges to its index in lo.

Analysis
Time
O(log N)
  • N is the number of elements in the array.
  • Each iteration discards half the range.
Space
O(1)
  • Only the lo, hi, and mid indices are tracked.
FIG. 852 PEAK INDEX IN A MOUNTAIN ARRAY● INTERACTIVE
visualization loads as you reach it
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
lo, hi = 0, len(arr) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < arr[mid + 1]:
lo = mid + 1
else:
hi = mid
return lo

1095. Find in Mountain Array​

Hard·
Explanation

A mountain array rises to one peak and then falls. Finding a target splits into locating that peak and then binary-searching each monotone slope - the ascending left side normally, the descending right side in reverse.

Step 1 - find the peak:

  • peakIndexInMountainArray returns the index of the single maximum, the boundary between the two runs.

Step 2 - search the ascending half:

  • Run bisect_left over [0, peakIndex); if it lands on target, that is the leftmost (and answer-priority) match.

Step 3 - search the descending half:

  • Run bisect_left_rev (the reverse-order variant) over [peakIndex, len - 1]; if it lands on target, return it.
  • If neither side matches, the target is absent -> return -1.

The wrapper trick:

  • The judge passes a MountainArray object that only exposes .get(i) and .length(), not normal indexing. CustomMountainArray wraps it so len(...) and arr[i] work, letting the generic bisect_left, bisect_left_rev, and peak finder be reused unchanged.
Analysis
Time
O(log N)
  • N is the number of elements in the array.
  • One peak search plus two bounded binary searches, each O(log N).
Space
O(1)
  • Only the wrapper handle and index scalars are tracked.
FIG. 1095 FIND IN MOUNTAIN ARRAY● INTERACTIVE
visualization loads as you reach it
class Solution:
def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] < target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
 
def bisect_left_rev(self, arr, target, lo: int = 0, hi: int = None):
# hi is exclusive. The insert position can never be >= len(arr)
hi = (hi or len(arr)) - 1
if lo == hi + 1: # if array is empty
return -1
if arr[hi] > target:
return hi + 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] > target:
lo = mid + 1
else:
hi = mid
return lo
 
def peakIndexInMountainArray(self, arr: List[int]) -> int:
lo, hi = 0, len(arr) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < arr[mid + 1]:
lo = mid + 1
else:
hi = mid
return lo
def findInMountainArray(self, target: int, mountain_arr: "MountainArray") -> int:
mountain_arr = CustomMountainArray(mountain_arr)
peakIndex = self.peakIndexInMountainArray(mountain_arr)
left = self.bisect_left(mountain_arr, target, lo=0, hi=peakIndex)
if mountain_arr[left] == target:
return left
right = self.bisect_left_rev(
mountain_arr, target, lo=peakIndex, hi=len(mountain_arr) - 1
)
if right < len(mountain_arr) and mountain_arr[right] == target:
return right
return -1
 
 
class CustomMountainArray:
def __init__(self, ma):
self.mountain_arr = ma
 
def __len__(self):
return self.mountain_arr.length()
 
def __getitem__(self, key):
return self.mountain_arr.get(key)

H-Index​

Find the crossover point where citations meet the rank-from-the-end count.

275. H-Index II​

Medium·
Explanation

With citations already sorted ascending, the h-index is the largest h such that at least h papers have >= h citations. At index i there are exactly len(citations) - i papers from i to the end, so we binary-search for the crossover point.

The helper:

  • cited = lambda i: len(citations) - i is the count of papers at index i or later - the candidate h-value.

The decision:

  • If cited(mid) > citations[mid], this paper's citation count can't support that many papers, so the valid h must come from the right -> lo = mid + 1.
  • Otherwise mid is still feasible -> hi = mid.

After the loop, lo is the crossover index. We return cited(lo) if citations[lo] actually supports it, else 0.

Analysis
Time
O(log N)
  • N is the number of papers (length of citations).
  • The array is pre-sorted, so a single binary search suffices.
Space
O(1)
  • Only the lo, hi, and mid indices are tracked.
FIG. 275 H INDEX II● INTERACTIVE
visualization loads as you reach it
class Solution:
def hIndex(self, citations: List[int]) -> int:
cited = lambda i: len(citations) - i
lo, hi = 0, len(citations) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if cited(mid) > citations[mid]:
lo = mid + 1
else:
hi = mid
return cited(lo) if citations[lo] >= cited(lo) else 0

274. H-Index​

Medium·
Explanation

The h-index is the largest h such that at least h papers have >= h citations. The only difference from the sorted variant is that the input arrives unsorted, so we sort first and then run the identical boundary search.

Sort first:

  • After sorted(citations), the array is ascending and the index-based counting argument holds.

The helper:

  • cited = lambda i: len(citations) - i is the number of papers from index i onward - the candidate h-value at that position.

The decision:

  • If cited(mid) > citations[mid], that paper can't back this many papers -> lo = mid + 1.
  • Otherwise mid stays feasible -> hi = mid.

After the loop, return cited(lo) if citations[lo] supports it, else 0.

Analysis
Time
O(log N + N log N)
  • N is the number of papers (length of citations).
  • The while lo < hi binary search halves its range each step - O(log N) - on top of the O(N log N) sort.
Space
O(sort + N)
  • citations = sorted(citations) builds a brand-new list of N elements, on top of the sort's own working memory.
  • Sorting algorithms are typically O(log N) space (in-place, recursion stack only), but Python's sorted() is Timsort, which allocates up to O(N) auxiliary space in the worst case - that's what sort stands for here.
FIG. 274 H INDEX● INTERACTIVE
visualization loads as you reach it
class Solution:
def hIndex(self, citations: List[int]) -> int:
citations = sorted(citations)
cited = lambda i: len(citations) - i
lo, hi = 0, len(citations) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if cited(mid) > citations[mid]:
lo = mid + 1
else:
hi = mid
return cited(lo) if citations[lo] >= cited(lo) else 0