Data Structures Notes - Page 3

Data Structures

H-Index II

H-Index II (LeetCode 275): binary search on sorted citations to find the h-index in O(log n).

Data Structures

Guess Number Higher or Lower

Guess Number Higher or Lower (LeetCode 374): classic binary search against a guess API in O(log n).

Data Structures

Time Based Key-Value Store

Time Based Key-Value Store (LeetCode 981): store sorted (timestamp, value) pairs per key and binary-search the latest value at or before a query time.

Data Structures

Count of Smaller Numbers After Self

Count of Smaller Numbers After Self (LeetCode 315): scan right to left and binary-search each value into a sorted list to count smaller elements.

Data Structures

Binary Search on a Function (Ternary Search Alternative)

Binary search on a function: find the maximum of a unimodal function by comparing neighbouring values — a discrete alternative to ternary search.

Data Structures

Find the Smallest Divisor Given a Threshold

Find the Smallest Divisor Given a Threshold (LeetCode 1283): binary search the divisor using ceiling-division sums, O(n log max).

Data Structures

Single Element in a Sorted Array

Single Element in a Sorted Array (LeetCode 540): binary search on even indices to find the one non-duplicated element in O(log n).

Data Structures

Allocate Minimum Number of Pages

Allocate Minimum Number of Pages: binary search the minimum possible maximum pages per student with a greedy allocation check, O(n log sum).

Data Structures

Aggressive Cows (Binary Search on Answer)

Aggressive Cows: binary search the largest minimum distance between cows placed in stalls, with a greedy feasibility check, O(n log range).

Data Structures

Kth Smallest Element in a Sorted Matrix

Kth Smallest Element in a Sorted Matrix (LeetCode 378): binary search on value, counting elements <= mid in O(n log(range)).

Data Structures

Find K Closest Elements

Find K Closest Elements (LeetCode 658): binary search the best window start so the k-length window is closest to x, in O(log(n-k)+k).

Data Structures

Search a 2D Matrix II

Search a 2D Matrix II (LeetCode 240): staircase search from the top-right corner eliminates a row or column each step, in O(m+n).