Problem says X → Think Y

Sorted input, or any predicate that flips from false to true exactly once over an ordered range, means every comparison can discard half of the candidates. The "search space" need not be an array: it can be the answer itself (a speed, a capacity, a day) as long as feasibility is monotonic in that value.

Example: Koko can eat at most k bananas per hour; find the minimum k so that all piles are finished within h hours.

When order gives you a way to decide which of two ends to move, you can replace an O(n^2) double loop by a single pass. Opposite-direction pointers exploit sortedness (move the side that must change); same-direction pointers maintain a "written so far" prefix for in-place compaction.

Example: Given a sorted array and a target, return the indices of two numbers whose sum equals the target, in O(1) extra space.

Two pointers moving at different speeds along a sequence of next links meet if and only if the sequence loops (Floyd). The same trick locates the middle in one pass and finds the cycle entry, all in O(1) space. Any function f: [1..n] -> [1..n] iterated from a start is an implicit linked list.

Example: Given an array of n + 1 integers each in [1, n], find the one duplicate without modifying the array and using constant extra space.

A question about contiguous ranges whose validity is monotonic (extending a valid window can only break it; shrinking an invalid window can only fix it) can be answered with two indices that both only move right. Each element enters and leaves the window once, giving O(n) instead of O(n^2) enumeration of subarrays.

Example: Return the length of the longest substring that contains at most two distinct characters.

Whenever a brute force re-scans earlier elements to check membership, count, or a complement, a hash table answers the same question in expected O(1) and turns O(n^2) into O(n). Grouping problems reduce to choosing a canonical key (a sorted string, a character-count tuple) and bucketing by it.

Example: Given an array of strings, group the anagrams together.

If many queries ask for an aggregate over [l, r] and the aggregate has an inverse (sum, XOR, product without zeros), precompute P[i] = agg(a[0..i)) once so every query becomes P[r+1] - P[l]. Combined with a hash map of seen prefix values it counts subarrays with a given sum in one pass; the inverse trick (difference array) makes range updates O(1).

Example: Given an integer array and k, count the number of contiguous subarrays whose sum equals k.

Asking, for every element, about the nearest element to its left or right that is larger or smaller is a signal to keep a stack whose values are sorted. Each element is pushed once and popped once, and the moment it is popped you know exactly who its "next greater" is: the element doing the popping.

Example: For each day in a list of temperatures, output how many days you have to wait for a warmer temperature (0 if never).

Nesting and "last opened must be first closed" are LIFO by definition, so a stack tracks the currently open context. Any recursive process can also be flattened onto an explicit stack, which is how iterative DFS and expression parsers work.

Example: Given a string of brackets ()[]{}, determine whether every opening bracket is closed by the same type in the correct order.

When you repeatedly need the minimum or maximum of a changing collection, a heap gives O(log n) insert and extract instead of re-sorting. "Top k" problems keep a heap of size k for O(n log k); a "median of stream" balances a max-heap of the lower half against a min-heap of the upper half.

Example: Given an integer array and k, return the k most frequent elements.

BFS explores in rings of increasing distance, so the first time it reaches a node it has found a shortest path in terms of edge count. "Minimum number of moves" on any state space where each move costs 1 is BFS, whether the states are grid cells, words, or puzzle configurations.

Example: In a grid of fresh and rotten oranges, every minute rot spreads to adjacent fresh oranges; return the minimum minutes until no fresh orange remains, or -1.

DFS follows one branch to exhaustion before backtracking, which makes it the natural tool for "which cells/nodes belong together", for enumerating complete paths, and for cycle detection via the recursion stack (gray nodes). It needs only the graph plus a visited set and is easily written recursively.

Example: Count the number of islands in a grid of 1s (land) and 0s (water), where an island is 4-directionally connected land.

Once edges have different costs, BFS order is wrong and you need to expand nodes by accumulated distance: Dijkstra with a min-heap for non-negative weights. Negative weights or a "at most k edges" bound push you to Bellman-Ford (k rounds of relaxation); "every pair" on a small dense graph is Floyd-Warshall.

Example: Given n cities with flight prices, find the cheapest price from src to dst using at most k stops.

Constraints of the form "A before B" are edges in a directed graph; a valid schedule exists exactly when the graph has no cycle, and any topological order is a valid schedule. Kahn's algorithm (peel off zero in-degree nodes) also detects impossibility: if it stops before emitting every node, a cycle remains.

Example: There are n courses and a list of pairs [a, b] meaning course b must be taken before a; return an order in which all courses can be finished, or an empty list.

When connectivity is built up incrementally by unions and queried repeatedly, disjoint sets with path compression and union by rank answer both in near-constant amortized time, without rebuilding anything. It is the right tool whenever DFS would have to be rerun after each new edge, and it is the engine of Kruskal's MST.

Example: A tree of n nodes had one extra edge added; return the edge that can be removed so the result is a tree again.

Enumerating every arrangement is exponential, so tiny bounds plus "all" or "any valid" wording mean search the decision tree: choose, recurse, un-choose. Pruning invalid partial states early (a queen already attacked, a sum already exceeded) is what makes it practical.

Example: Given distinct candidates and a target, return all unique combinations (with reuse allowed) that sum to the target.

Counting or optimizing over choices where a brute-force recursion revisits the same state signals DP: define the state so the answer to a state depends only on smaller states, then memoize or fill a table bottom-up. Subsequence (not subarray) wording, "number of ways", and "minimum/maximum over all choices" are the classic tells.

Example: Given coins of given denominations and an amount, return the fewest coins needed to make the amount, or -1.

When a locally best choice (earliest finish time, largest ratio, farthest reach) can be proved never to hurt the global optimum, you can commit to it without exploring alternatives and get O(n log n) from sorting. The proof usually comes via an exchange argument; if you cannot sketch one, suspect DP instead.

Example: Given intervals, return the minimum number to remove so the rest are non-overlapping.

Prefix questions over a set of strings are answered by walking a tree keyed by characters, costing O(L) per query regardless of how many words are stored. It also lets a grid DFS abort as soon as the current path is not a prefix of any word, which is what makes multi-word search feasible.

Example: Implement a data structure with insert(word), search(word), and startsWith(prefix).

Sort by start (or end) time and sweep: two intervals overlap iff the next start is before the current end, and after sorting each interval only needs comparing with the one being built. Counting concurrent intervals is a sweep over sorted endpoints, or a min-heap of end times.

Example: Given meeting time intervals, return the minimum number of conference rooms required.

If a problem on n items can be solved from solutions on two halves plus linear-time combination work, the recurrence T(n) = 2T(n/2) + O(n) gives O(n log n). Merge sort's merge step is the template; counting inversions and merging k lists pairwise are direct instances.

Example: Given k sorted linked lists, merge them into one sorted list.

XOR cancels pairs, so "every element appears twice except one" is a single XOR pass with no extra memory. Sets of at most ~20 items fit in an integer bitmask, turning subset enumeration and "which nodes have been visited" states into cheap arithmetic that DP and BFS can index directly.

Example: Every element in the array appears twice except one; find it in linear time and constant space.

Prefix sums break the moment the array changes, since every prefix after the update shifts. A Fenwick or segment tree stores partial aggregates over power-of-two ranges so both a point update and a range query touch only O(log n) nodes. Use a sparse table instead when the array is static and the operation is idempotent (min, max, gcd).

Example: Design a structure supporting update(i, val) and sumRange(l, r) on an array of up to 3 * 10^4 elements with 3 * 10^4 operations.

The best subarray ending at index i is either the element alone or the element appended to the best subarray ending at i - 1; a negative running sum is never worth carrying. This is a one-variable DP over "best ending here", which generalizes to product subarrays (track min and max) and stock problems.

Example: Find the contiguous subarray with the largest sum and return that sum.

Pointer surgery problems are about maintaining prev, curr, and next so no node becomes unreachable, and a dummy head removes the special case of modifying the first node. Doubly linked lists paired with a hash map give O(1) move-to-front, which is the basis of LRU caches.

Example: Reverse a singly linked list iteratively and recursively.

Nearly every tree problem is a traversal with the right information passed down (bounds, depth) or returned up (height, best path through this node). Inorder on a BST yields sorted order, which solves kth-smallest and validation; BFS with a queue yields levels.

Example: Return the maximum path sum in a binary tree, where a path may start and end at any nodes.

An answer "modulo a prime" says intermediate values overflow and you must reduce at every step, and that division becomes multiplication by a modular inverse. Bounds like 10^18 rule out iteration and point to O(log n) exponentiation or Euclid; "all primes up to n" is a sieve.

Example: Compute x^n for a real x and an integer n that may be negative, in O(log n).