Data structures algorithms

A shortest-path search that guides exploration using f(n) = g(n) + h(n), where g is the cost so far and h is a heuristic estimate of the cost remaining. With an admissible heuristic that never overestimates, it finds an optimal path while exploring fewer nodes than Dijkstra.

Example. Navigation software can use straight-line distance to the destination as h, so it favours routes heading toward the goal.

Related: Dijkstra's algorithm, Heuristic, Priority queue

A description of a data structure by what operations it supports and how they behave, without saying how it is stored. Several concrete structures can implement the same one, which lets code depend on behaviour rather than layout.

Example. A queue promises 'add at the back, remove from the front'. You can build it from a linked list or a circular buffer without changing the code that uses it.

Related: Stack, Queue, Data structure

A way of storing a graph where each vertex keeps a list of its neighbours. It uses space proportional to vertices plus edges, making it the usual choice for sparse graphs.

Example. For edges A-B and A-C, the list is {A: [B, C], B: [A], C: [A]}, and visiting A's neighbours costs only its degree.

Related: Adjacency matrix, Graph, Breadth-first search

A way of storing a graph as an n by n table where the entry in row i, column j shows whether an edge connects vertex i to vertex j. Edge checks take one step, but the table needs n^2 space regardless of edge count.

Example. For 1,000 vertices the matrix has 1,000,000 cells. It suits dense graphs where most pairs are connected.

Related: Adjacency list, Graph, Floyd-Warshall algorithm

A finite, unambiguous sequence of steps that turns an input into a desired output. Good algorithms are judged by correctness and by how much time and memory they use as the input grows.

Example. Finding the largest number in a list by keeping a running maximum and scanning the list once is an algorithm that takes n steps for n items.

Related: Data structure, Time complexity, Heuristic

A way of measuring the average cost per operation over a worst-case sequence of operations, so an occasional expensive step is spread across many cheap ones. It differs from average-case analysis because it needs no probability assumptions.

Example. Appending to a dynamic array is O(1) amortized: an occasional resize copies all n items, but that cost is shared over the n cheap appends before it.

Related: Dynamic array, Worst-case analysis, Time complexity

An algorithm for a hard optimisation problem that runs in polynomial time and comes with a proven guarantee on how far its answer can be from the optimum, such as within a factor of 2. This differs from a heuristic, which has no such guarantee.

Example. A well-known simple method for vertex cover picks both ends of unmatched edges and returns a cover at most twice the size of the best one.

Related: Heuristic, NP-complete, Greedy algorithm

A fixed-size block of memory holding items of the same kind one after another, so any item can be reached directly from its position number. Reading or writing by index is very fast, but inserting in the middle requires shifting later items.

Example. In an array of 5 marks [72, 88, 65, 90, 79], marks[3] gives 90 in one step, but inserting a new value at position 1 moves four items.

Related: Dynamic array, Linked list

A self-balancing binary search tree that keeps the heights of the two subtrees of every node within 1 of each other, restoring balance with rotations after inserts and deletes. This guarantees O(log n) search, insert and delete.

Example. Inserting 1, 2, 3, 4, 5 in order into a plain search tree gives a chain of height 5. An AVL tree rotates as it goes and stays about 3 levels tall.

Related: Binary search tree, Red-black tree, B-tree

A balanced search tree where each node holds many keys and has many children, designed so that one node fits a disk page. Its low height means few disk reads per lookup, which is why databases and file systems use it for indexes.

Example. A B-tree node holding 100 keys can index 1 crore records in roughly four levels, so a lookup reads about four pages.

Related: Binary search tree, AVL tree

A search strategy that builds a solution one choice at a time and abandons a partial solution as soon as it cannot lead to a valid answer, then undoes the last choice and tries another. It is used for puzzles and constraint problems.

Example. In placing 8 queens on a chessboard so none attack, backtracking drops a placement immediately when a queen is attacked instead of finishing the board.

Related: Depth-first search, Recursion

The simplest input of a recursive function that is answered directly without a further self-call. Without one, or with a step that never reaches it, the calls never stop and the program runs out of stack space.

Example. In a function that sums a list, an empty list returns 0 immediately and ends the chain of calls.

Related: Recursion, Call stack

A shortest-path algorithm that repeatedly relaxes every edge up to V-1 times, where V is the number of vertices. It handles negative edge weights and can detect a negative cycle, at the cost of O(V*E) time.

Example. In a currency exchange graph with log-transformed rates, Bellman-Ford can reveal an arbitrage loop as a negative cycle.

Related: Dijkstra's algorithm, Floyd-Warshall algorithm, Weighted graph

A shorthand for describing how the running time or memory of an algorithm grows with input size n, keeping only the fastest-growing term and ignoring constant factors. It gives an upper bound and lets us compare algorithms independent of hardware.

Example. Checking every pair in a list of n items takes about n*n steps, so it is O(n^2). Doubling n makes it roughly four times slower.

Related: Time complexity, Space complexity, Big-Theta notation, Worst-case analysis

A notation giving an asymptotic lower bound on growth: f(n) is Omega(g(n)) if f eventually stays above a constant multiple of g(n). It states how much work an algorithm must do at least, or how much any algorithm for a problem must do.

Example. Any comparison-based sorting method needs Omega(n log n) comparisons in the worst case, so no such method can beat that bound.

Related: Big-O notation, Big-Theta notation, Comparison sort

A notation saying a function grows at the same rate as another, bounded both above and below by constant multiples for large inputs. It is a tight bound, more precise than an upper bound alone.

Example. Merge sort always takes about n log n steps, so its running time is Theta(n log n), not just O(n log n).

Related: Big-O notation, Big-Omega notation, Time complexity

A method of finding a value in a sorted array by comparing with the middle item and discarding the half that cannot contain it, repeating until found. It takes O(log n) time instead of O(n).

Example. Looking for 47 among 1,00,000 sorted IDs takes at most about 17 comparisons, since each step halves the range.

Related: Linear search, Array, Binary search tree

A binary tree where every node's left subtree holds smaller keys and its right subtree holds larger keys. Searching, inserting and deleting follow one path from the root, taking time proportional to the tree's height, about log n when balanced.

Example. Searching for 40 in a tree with root 50: 40 is smaller, so go left, reaching the answer without visiting the right side at all.

Related: Binary tree, AVL tree, Binary search

A tree in which each node has at most two children, called left and right. It is the base for search trees, heaps and expression trees, and is commonly traversed in preorder, inorder or postorder.

Example. An expression like (2 + 3) * 4 becomes a tree with '*' at the root, a '+' node with children 2 and 3 on the left, and 4 on the right.

Related: Tree, Binary search tree, Tree traversal

A graph whose vertices can be split into two groups so that every edge joins a vertex in one group to a vertex in the other. It can be tested by colouring vertices with two colours using traversal.

Example. Students on one side and courses on the other, with edges for enrolment, form a bipartite graph because no edge joins two students.

Related: Graph, Breadth-first search, Connected components

A compact probabilistic structure that tells whether an item is definitely absent or possibly present in a set. It uses a bit array and several hash functions, allows false positives but never false negatives, and saves memory compared with storing the items.

Example. A database checks a Bloom filter before reading disk: if it says 'absent' the disk read is skipped, and if it says 'present' the record is looked up to confirm.

Related: Hash function, Hash table

A graph traversal that visits all vertices at distance 1 from the start, then distance 2, and so on, using a queue. On graphs with equal edge costs it finds the path with the fewest edges.

Example. Finding the fewest hops between two people in a social network: expand friends, then friends of friends, until the target is reached.

Related: Depth-first search, Queue, Shortest path

A simple sorting method that repeatedly steps through the list, swapping adjacent items that are in the wrong order, until no swaps are needed. It takes O(n^2) time and is used mainly for teaching.

Example. On [5, 1, 4], one pass swaps 5 and 1, then 5 and 4, giving [1, 4, 5].

Related: Insertion sort, Selection sort, Stable sort

The region of memory that records active function calls, storing each call's local variables and return point on top of the previous one. Very deep recursion can fill it and cause a stack overflow error.

Example. A recursive function that calls itself 1 lakh times without returning can exceed Python's default recursion limit of roughly a thousand calls.

Related: Recursion, Stack

A fixed-size queue stored in an array where the read and write positions wrap around to the start when they reach the end. It avoids shifting items and never reallocates, so it is common in streaming and logging.

Example. A buffer holding the last 100 sensor readings overwrites the oldest reading when the 101st arrives, using one array and two moving indices.

Related: Queue, Array, Deque

The task of finding the fewest coins that add up to a target amount, or the number of ways to make it. Greedy choices can fail for unusual coin sets, so dynamic programming is used.

Example. For coins 1, 3, 4 and amount 6, greedy picks 4+1+1 (three coins) but the best is 3+3 (two coins).

Related: Dynamic programming, Greedy algorithm, Knapsack problem

The situation where two different keys are mapped to the same slot by a hash function. Since slots are fewer than possible keys, collisions are unavoidable and every hash table needs a strategy to resolve them.

Example. With 8 slots, keys 'cat' and 'act' are anagrams and would land in the same slot if the function only adds character codes.

Related: Separate chaining, Open addressing, Hash function

A sorting method that orders items only by comparing pairs of them. Any such method needs at least about n log n comparisons in the worst case, which is why merge sort and heap sort are considered optimal among these.

Example. Sorting 1,024 names by pairwise comparisons needs at least about 1,024 * 10 comparisons in the worst case.

Related: Merge sort, Quicksort, Big-Omega notation

The maximal groups of vertices in an undirected graph in which every vertex can reach every other through some path. They are found by running breadth-first or depth-first search from each unvisited vertex.

Example. A friendship graph with two separate clusters of people who never interact has 2 connected components.

Related: Union-find, Depth-first search, Graph

A scheme that places both servers and keys on a circular hash space and assigns each key to the next server clockwise. When servers are added or removed only a small fraction of keys move, unlike simple modulo assignment.

Example. With 4 cache servers, removing one moves only that server's keys to its neighbour, whereas key mod 4 to key mod 3 would remap almost every key.

Related: Hash function, Hash table, Load factor

A non-comparison sorting method for integers in a small known range that counts how many times each value occurs and then writes the values out in order. It runs in O(n + k) time, where k is the range size.

Example. Sorting 1 lakh exam marks between 0 and 100 needs only 101 counters and one pass, far faster than comparison sorting.

Related: Radix sort, Comparison sort, Array

Determining whether a graph contains a path that starts and ends at the same vertex. In directed graphs it is done with depth-first search by watching for an edge pointing back to a vertex on the current path.

Example. If task A needs B, B needs C and C needs A, cycle detection reports a circular dependency that blocks the build.

Related: Directed acyclic graph, Depth-first search, Topological sort

A way of organising values in memory so that particular operations, such as looking up, adding or removing items, are fast and easy to write. Different layouts favour different operations, so choosing one is a central design decision in every program.

Example. Storing 10,000 customer IDs in a hash-based set makes 'is this ID present?' take about one step, while a plain list needs up to 10,000 checks.

Related: Algorithm, Abstract data type, Time complexity

A graph or tree traversal that follows one path as far as possible before backing up to try another, using recursion or an explicit stack. It suits exploring all possibilities, detecting cycles and finding components.

Example. In a maze, DFS walks down a corridor until a dead end, then backtracks to the last junction and tries another turn.

Related: Breadth-first search, Stack, Backtracking, Cycle detection

A double-ended queue that supports adding and removing items efficiently at both the front and the back. It generalises both a stack and a queue and is handy for sliding-window problems.

Example. Python's collections.deque lets you call append and popleft in constant time, unlike a list where removing from the front shifts every item.

Related: Queue, Stack, Sliding window

An algorithm that finds the shortest paths from one start vertex to all others in a graph with non-negative edge weights. It repeatedly picks the unfinished vertex with the smallest known distance, using a priority queue, and updates its neighbours.

Example. From Delhi, it finalises the nearest city first, then relaxes routes through it, giving the shortest road distance to every other city.

Related: Priority queue, Bellman-Ford algorithm, A* search, Weighted graph

A graph whose edges have a direction and that has no path leading from a node back to itself. It represents ordered dependencies, such as tasks that must finish before others begin.

Example. A data pipeline where 'clean' must precede 'train' and 'train' must precede 'evaluate' forms a DAG, and any valid run order is a topological order.

Related: Topological sort, Graph, Cycle detection

A strategy that splits a problem into smaller independent subproblems of the same kind, solves each, and combines the answers. Its cost is often analysed with a recurrence relation. Merge sort and binary search are classic examples of the approach.

Example. Merge sort splits a list of 1,000 items into two of 500, sorts each, and merges, repeating until single items remain.

Related: Merge sort, Recursion, Recurrence relation

A linked list where every node points to both its next and previous node. This allows walking in either direction and removing a node in constant time when you already hold a reference to it.

Example. An LRU cache keeps its entries in a doubly linked list so a used entry can be unlinked and moved to the front in O(1).

Related: Linked list, LRU cache, Deque

An array that grows automatically: when it fills up, it allocates a larger block, usually double the size, copies the items over and continues. It keeps fast index access while allowing appends without knowing the size beforehand.

Example. Python's list behaves this way. Appending 1,000 items triggers only a handful of internal resizes, so each append averages constant time.

Related: Array, Amortized analysis, Linked list

A method for solving problems by breaking them into overlapping subproblems, solving each only once and storing the answers for reuse. It applies when an optimal solution is built from optimal solutions of smaller pieces.

Example. Computing the 40th Fibonacci number by storing each earlier value takes 40 steps, while naive recursion repeats work over a hundred million times.

Related: Memoization, Tabulation, Optimal substructure, Overlapping subproblems

The minimum number of single-character insertions, deletions and substitutions needed to turn one string into another. It is computed by dynamic programming and used in spell checking and fuzzy matching.

Example. Turning 'kitten' into 'sitting' takes 3 edits: replace k with s, replace e with i, and add g.

Related: Longest common subsequence, Dynamic programming, String matching

A compact structure stored in a single array that supports prefix-sum queries and single-element updates in O(log n) time by using the binary representation of indices. It is simpler and lighter than a segment tree for sums.

Example. After adding a sale to day 37, the total of days 1 to 100 is recomputed with about seven array reads instead of 100.

Related: Segment tree, Prefix sum, Array

A dynamic programming algorithm that computes shortest paths between every pair of vertices by gradually allowing more vertices as intermediate stops. It runs in O(V^3) time and works with negative edges but no negative cycles.

Example. For a 200-city network it produces a full 200 by 200 table of shortest distances in about 8 million steps.

Related: Dijkstra's algorithm, Dynamic programming, Adjacency matrix

A set of vertices (nodes) joined by edges (connections), used to model relationships such as roads, friendships or dependencies. Edges may be directed or undirected and may carry weights. It models networks such as roads, friendships or web links.

Example. Cities as vertices and roads as edges form a graph, where each edge's weight can be the distance in kilometres.

Related: Tree, Adjacency list, Directed acyclic graph

An algorithm that builds a solution step by step, always choosing the option that looks best right now and never reconsidering. It gives optimal answers for some problems, but for others only approximate ones.

Example. Giving change of 41 in coins 25, 10, 5, 1 by taking the largest coin each time gives 25, 10, 5, 1, which is optimal for this coin set.

Related: Dynamic programming, Kruskal's algorithm, Coin change problem

A structure that stores key-value pairs by running each key through a function that produces an array position, allowing lookup, insertion and deletion in about one step on average. It is the basis of Python dictionaries and sets.

Example. Storing phone numbers by name: looking up 'Asha' hashes the name to a slot and returns her number without scanning all contacts.

Related: Hash function, Collision, Load factor

A sorting method that builds a max-heap from the data and repeatedly removes the largest item to fill the result from the end. It runs in O(n log n) in every case and in place, but is not stable.

Example. Build a max-heap from [4, 10, 3, 5], swap the top 10 to the end, restore the heap, and repeat until sorted.

Related: Heap, Heapify, Merge sort

The procedure of turning an unordered array into a valid heap, or of restoring the heap property after one element changes, by moving elements down (sift down) or up. Building a heap from n items this way takes O(n) time.

Example. Turning [9, 4, 7, 1] into a min-heap by sifting down from the last parent yields [1, 4, 7, 9].

Related: Heap, Heap sort, Priority queue

A practical rule or shortcut that finds a good, though not guaranteed optimal, answer quickly. Heuristics are used when exact methods are too slow and can also guide searches such as A*.

Example. Always going to the nearest unvisited city is a simple heuristic for delivery routes that gives decent tours without checking all orders.

Related: Approximation algorithm, A* search, Greedy algorithm

A compression method that gives shorter binary codes to frequent symbols and longer codes to rare ones, built greedily by repeatedly merging the two least frequent items into a tree using a priority queue. It produces the best possible prefix code for known frequencies.

Example. In a text where 'e' is far more common than 'z', 'e' might get a 2-bit code and 'z' a 7-bit code, shrinking the file.

Related: Greedy algorithm, Priority queue, Binary tree

An algorithm that transforms its input using only a small, constant amount of extra memory rather than building a copy. It saves memory but often modifies the original data. This matters when memory is limited or the data set is very large.

Example. Reversing an array by swapping the first and last items, then moving inward, needs only one temporary variable.

Related: Space complexity, Quicksort, Two pointers

A sorting method that builds a sorted section one item at a time, inserting each new item into its correct place among the already sorted ones. It takes O(n^2) in general but is fast on nearly sorted data and small inputs.

Example. Sorting playing cards in your hand by picking up one card at a time and sliding it into the right spot is insertion sort.

Related: Bubble sort, Timsort, Stable sort

The problem of choosing the largest set of time intervals that do not overlap. A greedy rule of always picking the interval that ends earliest is provably optimal. This is a standard example of a greedy algorithm.

Example. From meetings 9-11, 10-12 and 11-13, choosing the one ending earliest (9-11) then 11-13 allows two meetings instead of one.

Related: Greedy algorithm, Sorting, Heap

A one-pass algorithm that finds the contiguous stretch of a numeric array with the largest sum by tracking the best sum ending at each position and the best seen overall. It runs in O(n) time and O(1) space.

Example. For [-2, 1, -3, 4, -1, 2, 1, -5, 4] the best stretch is 4, -1, 2, 1 with sum 6.

Related: Dynamic programming, Sliding window, Prefix sum

An optimisation problem: given items with weights and values and a bag with a weight limit, choose items to maximise total value without exceeding the limit. The 0/1 version is solved by dynamic programming in O(n*W) time.

Example. With capacity 5 kg and items (2 kg, ₹30), (3 kg, ₹40), (4 kg, ₹50), the best choice is the first two items for ₹70.

Related: Dynamic programming, Greedy algorithm, NP-complete

A string matching algorithm that precomputes, for the pattern, how far to fall back after a mismatch so that no text character is examined twice. It searches in O(n + m) time.

Example. Searching 'ABABC' in a text, after a mismatch it jumps using the pattern's prefix table rather than restarting from the next text character.

Related: String matching, Dynamic programming

An algorithm that builds a minimum spanning tree by sorting all edges by weight and adding each edge in turn unless it would create a cycle, which it checks with a union-find structure. Time is O(E log E).

Example. Edges of weight 1, 2, 3 are added first. A weight-4 edge joining two already connected cities is skipped to avoid a loop.

Related: Minimum spanning tree, Union-find, Prim's algorithm

Finding a value by checking items one by one from the start until it is found or the list ends. It needs no ordering of the data but takes O(n) time.

Example. Looking for a name in an unsorted list of 500 names may need up to 500 comparisons.

Related: Binary search, Array, Time complexity

A sequence of nodes where each node stores a value and a reference to the next node. Insertion or removal at a known node is fast because no shifting is needed, but reaching the k-th item requires walking through k nodes.

Example. To remove a node from a list of 50 items you only redirect the previous node's pointer, but to find the 40th item you must follow 40 links.

Related: Doubly linked list, Array, Stack

For a hash table, the ratio of stored entries to available slots: load factor = n / m. A high value means more collisions, so implementations resize and rehash the table when it crosses a threshold.

Example. A table with 75 entries in 100 slots has load factor 0.75. Adding entries beyond a chosen limit triggers doubling to 200 slots.

Related: Hash table, Collision, Open addressing

The longest sequence of items that appears in both of two sequences in the same order, though not necessarily side by side. It is solved by a dynamic programming table and underlies text comparison tools.

Example. For 'ABCBDAB' and 'BDCABA', one longest common subsequence is 'BCBA' with length 4.

Related: Edit distance, Dynamic programming, Longest increasing subsequence

The longest subsequence of a sequence whose values strictly increase from left to right, with items possibly not adjacent. It is solved in O(n^2) by dynamic programming or O(n log n) with binary search.

Example. In [10, 9, 2, 5, 3, 7, 101, 18] one longest increasing subsequence is 2, 3, 7, 18 with length 4.

Related: Longest common subsequence, Dynamic programming, Binary search

A fixed-size cache that, when full, removes the item that was used least recently. It is commonly built from a hash table plus a doubly linked list so both lookup and update take constant time.

Example. With capacity 3 holding pages A, B, C where A was used longest ago, adding D evicts A.

Related: Hash table, Doubly linked list

A formula that directly gives the asymptotic solution of divide and conquer recurrences of the form T(n) = aT(n/b) + f(n) by comparing f(n) with n^(log_b a). It saves solving each recurrence by hand.

Example. For T(n) = 2T(n/2) + n we have a = 2, b = 2, and f(n) matches n^1, so the result is Theta(n log n).

Related: Recurrence relation, Divide and conquer, Time complexity

A top-down optimisation that saves the result of each function call for given arguments and returns the saved value if the same call happens again. It turns exponential recursion into polynomial work when subproblems repeat.

Example. Wrapping a recursive Fibonacci function with functools.lru_cache makes fib(50) return immediately instead of repeating billions of calls.

Related: Dynamic programming, Tabulation, Recursion

A divide and conquer sorting method that splits the list in half, sorts each half recursively and then merges the two sorted halves. It runs in O(n log n) time in every case, is stable and needs O(n) extra memory.

Example. Sorting [8, 3, 5, 1]: split into [8, 3] and [5, 1], sort each to [3, 8] and [1, 5], then merge to [1, 3, 5, 8].

Related: Divide and conquer, Quicksort, Stable sort

For a connected weighted graph, a subset of edges that links all vertices with no cycles and the smallest possible total weight. It is used to connect places at the lowest cost, such as laying cable.

Example. Connecting 6 villages with the least total length of road: an MST uses exactly 5 roads and is the cheapest way to make all villages reachable.

Related: Kruskal's algorithm, Prim's algorithm, Weighted graph

A stack kept in increasing or decreasing order by removing items that violate the order before each new push. It answers 'next greater element' style questions for all positions in O(n) total time.

Example. For temperatures [30, 32, 31, 35], a stack finds that the next warmer day after 30 is 32 and after 31 is 35, each item pushed and popped once.

Related: Stack, Sliding window, Two pointers

A class of decision problems that are both checkable in polynomial time and at least as hard as every other problem in that class, so a fast solution to one would give a fast solution to all. Recognising one signals that exact fast algorithms are unlikely.

Example. Deciding whether a set of items fits the knapsack for a target value is NP-complete, so large exact instances may need heuristics.

Related: P versus NP, Knapsack problem, Approximation algorithm

A method of handling collisions where all entries live in the array itself, and a colliding key is placed in another slot found by a probing sequence such as trying the next slot. It saves pointer memory but degrades sharply when the table is nearly full.

Example. If slot 5 is taken, linear probing tries slot 6, then 7, until a free slot is found. Lookup follows the same path.

Related: Collision, Separate chaining, Load factor

The property that an optimal solution to a problem contains within it optimal solutions to its subproblems. It is what allows dynamic programming and greedy methods to build a global answer from local ones.

Example. A shortest route from Delhi to Chennai through Nagpur must use the shortest Delhi-Nagpur route as its first part.

Related: Dynamic programming, Overlapping subproblems, Greedy algorithm

The property that a recursive solution solves the same smaller problems many times. Recognising it signals that caching results, as in dynamic programming, will pay off. Recognising this property is the first sign that dynamic programming may help.

Example. The recursive call tree for fib(5) computes fib(3) twice and fib(2) three times.

Related: Dynamic programming, Memoization, Optimal substructure

The open question of whether every problem whose proposed answer can be checked quickly (in polynomial time) can also be solved quickly. Most experts believe not, but it is unproven, and it shapes how we judge hard problems.

Example. Checking a given Sudoku solution is fast, but no known method solves every large puzzle quickly, and nobody has proved that none exists.

Related: NP-complete, Polynomial time, Traveling salesman problem

Running time bounded by n raised to some fixed power, such as n, n^2 or n^3. Problems solvable this way are considered practically tractable, in contrast to exponential time, which becomes impossible even for moderate n.

Example. An O(n^2) algorithm handles 10,000 items in about 10^8 steps, while an O(2^n) algorithm is hopeless beyond roughly 50 items.

Related: P versus NP, Big-O notation, NP-complete

An array in which each entry holds the total of all items up to that position, computed once in O(n). The sum of any range is then found in O(1) as a difference of two prefix values.

Example. For [3, 1, 4, 2] the prefix sums are [3, 4, 8, 10]. The sum of positions 2 to 3 is 10 - 4 = 6.

Related: Fenwick tree, Segment tree, Sliding window

An algorithm that grows a minimum spanning tree from a start vertex, repeatedly adding the cheapest edge that connects the tree to a new vertex, usually using a priority queue. It works well on dense graphs.

Example. Starting at one village, it always adds the cheapest road to a village not yet connected until all are joined.

Related: Minimum spanning tree, Kruskal's algorithm, Priority queue

A collection where each item has a priority and the item with the highest priority is removed next, regardless of insertion order. It is usually built on a heap and powers schedulers and shortest-path search.

Example. A hospital triage system always calls the most urgent patient next, even if a less urgent patient arrived earlier.

Related: Heap, Dijkstra's algorithm, Queue

A collection where items are added at the back and removed from the front, so the oldest item leaves first (first in, first out). It models waiting lines and work that must be handled in arrival order.

Example. A ticket-booking system serves requests in arrival order: the request that arrived first is processed first, using a queue.

Related: Stack, Deque, Priority queue, Breadth-first search

An algorithm that finds the k-th smallest item of an unsorted array by partitioning around a pivot as in quicksort but continuing into only the side containing the target. It averages O(n) time.

Example. To find the median of 1 lakh values, partition around a pivot and recurse into only the half that holds the middle position.

Related: Quicksort, Top-K problem, Divide and conquer

A divide and conquer sorting method that picks a pivot, moves smaller items before it and larger items after it, then sorts each side recursively. It averages O(n log n) and works in place but degrades to O(n^2) with consistently bad pivots.

Example. For [7, 2, 9, 4] with pivot 7: smaller items [2, 4] go left, larger [9] goes right, then each side is sorted.

Related: Merge sort, Divide and conquer, Quickselect, Worst-case analysis

A non-comparison sorting method that sorts numbers or strings digit by digit, from least to most significant, using a stable sort such as counting sort at each stage. It runs in O(d * (n + k)) for d digits.

Example. Sorting PIN codes: first order all codes by the last digit, then by the fifth digit, and so on to the first, giving fully sorted six-digit codes.

Related: Counting sort, Stable sort, Comparison sort

An algorithm that uses random choices during execution, so its behaviour or running time can vary between runs. It often gives simple methods with good expected performance, or lets you avoid bad worst-case inputs.

Example. Choosing the quicksort pivot at random makes the O(n^2) worst case extremely unlikely for any given input.

Related: Quicksort, Reservoir sampling, Bloom filter

An equation that defines the running time of a recursive algorithm in terms of its running time on smaller inputs, such as T(n) = 2T(n/2) + n. Solving it gives a closed-form bound like O(n log n).

Example. Merge sort splits into two halves and merges in linear time, so T(n) = 2T(n/2) + n, which solves to O(n log n).

Related: Divide and conquer, Master theorem, Time complexity

A technique in which a function solves a problem by calling itself on a smaller version of the same problem until it reaches a case simple enough to answer directly. It suits trees, nested data and divide and conquer.

Example. factorial(4) = 4 * factorial(3), which continues down to factorial(1) = 1, then multiplies back up to give 24.

Related: Base case, Call stack, Divide and conquer

A self-balancing binary search tree in which each node is coloured red or black under rules that keep the longest path at most twice the shortest. It guarantees O(log n) operations with fewer rotations than an AVL tree on updates.

Example. Ordered map implementations in some standard libraries use red-black trees so inserts and lookups stay logarithmic even for sorted input.

Related: AVL tree, Binary search tree, B-tree

A randomized method for picking k items uniformly from a stream whose length is unknown, keeping only k items in memory. The i-th item replaces a stored one with probability k/i.

Example. To pick one random tweet from a live stream, keep the first, then replace it with the 2nd with probability 1/2, the 3rd with 1/3, and so on.

Related: Randomized algorithm, Queue, Space complexity

A tree built over an array where each node stores a summary, such as sum or minimum, of a range of positions. It answers range queries and applies point updates in O(log n) time.

Example. For daily sales of a year, a segment tree returns the total for any date range, such as 14 to 200, in about nine node visits, and updates one day quickly.

Related: Fenwick tree, Prefix sum, Binary tree

A sorting method that repeatedly finds the smallest remaining item and swaps it to the next position of the sorted part. It always performs about n^2/2 comparisons but only up to n swaps.

Example. On [64, 25, 12, 22], the smallest, 12, is swapped to the front giving [12, 25, 64, 22], then 22 is chosen next.

Related: Bubble sort, Insertion sort, In-place algorithm

A method of handling collisions where each slot of a hash table holds a small list of all entries that map to it. Lookup hashes to a slot, then searches that short list.

Example. If keys 'a' and 'q' both map to slot 2, slot 2 stores a list with both, and a lookup compares the key against each entry in that list.

Related: Collision, Open addressing, Linked list

The problem of finding a route between two vertices in a graph with the smallest number of edges or the smallest total edge weight. Different algorithms apply depending on whether edges are weighted and whether weights can be negative.

Example. Finding the quickest bus route from Kolkata's Howrah to Salt Lake by minimising travel time across a weighted graph of stops.

Related: Breadth-first search, Dijkstra's algorithm, Bellman-Ford algorithm

A technique that maintains a contiguous range of a sequence and moves it forward one step at a time, updating the answer by adding the new item and removing the old one rather than recomputing. It brings many subarray problems to O(n).

Example. The highest total of any 3 consecutive days of sales in [4, 2, 7, 1, 9] is found by updating a running sum: 13, 10, 17.

Related: Two pointers, Prefix sum, Deque

Arranging items in a defined order, such as smallest to largest, by some key. Sorted data enables binary search, easy duplicate removal and merging, so it is a fundamental step in many algorithms.

Example. Sorting exam scores [72, 88, 65] gives [65, 72, 88], and then the median is simply the middle value.

Related: Merge sort, Quicksort, Binary search, Stable sort

The amount of extra memory an algorithm needs as a function of input size, usually not counting the input itself. It matters when data is large or memory is limited, such as on a phone or a small server.

Example. Reversing a list by building a new list uses O(n) extra space. Swapping elements from both ends within the same list uses O(1) extra space.

Related: Time complexity, In-place algorithm, Space-time trade-off

The common choice of using more memory to save computation time, or spending more time to save memory. Caching results and precomputed tables are typical examples. Engineers choose a point on this trade-off according to which resource is scarcer.

Example. Storing a prefix-sum array costs O(n) memory but makes each range-sum query O(1) instead of O(n).

Related: Memoization, Prefix sum, Space complexity

A sorting method that keeps items with equal keys in the same relative order as in the input. This lets you sort by one field and then by another without losing the first ordering.

Example. Sort orders by date first, then stably by city: each city's orders stay in date order.

Related: Merge sort, Timsort, Insertion sort

The problem of finding where a short pattern occurs within a longer text. The naive method compares at every position in O(n*m) time, while smarter algorithms reduce this using precomputed information or hashing.

Example. Finding 'error' in a 10 MB log file can be done in one pass using algorithms such as KMP.

Related: Knuth-Morris-Pratt algorithm, Trie

A bottom-up dynamic programming style that fills a table iteratively, starting from the smallest subproblems and using earlier entries to compute later ones. It avoids recursion and its overhead. It avoids recursion and usually makes the order of computation explicit.

Example. To compute fib(n), fill table[0] = 0, table[1] = 1, then table[i] = table[i-1] + table[i-2] up to n.

Related: Memoization, Dynamic programming, Array

A function describing how the number of basic steps an algorithm performs grows as the input size grows. It is usually written with Big-O and lets you predict whether a solution will still work when the data gets 1,000 times larger.

Example. A linear scan over 1 lakh orders is O(n), about 100,000 steps. A nested loop over the same data is O(n^2), about 10 billion steps and far too slow.

Related: Space complexity, Big-O notation, Worst-case analysis

A hybrid stable sorting algorithm that finds naturally ordered runs in the data, extends short ones with insertion sort and merges runs. It is O(n log n) worst case and close to O(n) on nearly sorted data, and it is the sort used by Python's sorted and list.sort.

Example. Sorting a log file that is already mostly in time order is very fast because Timsort detects the long ordered runs and merges few of them.

Related: Merge sort, Insertion sort, Stable sort

Finding the k largest or smallest items from a collection without fully sorting it. A heap of size k does this in O(n log k) time, which is far cheaper than sorting when k is small.

Example. To list the 10 highest-selling products from 5 lakh, keep a min-heap of 10 items and replace its smallest whenever a bigger sale appears.

Related: Heap, Quickselect, Priority queue

An ordering of the vertices of a directed acyclic graph so that every edge points from an earlier vertex to a later one. It exists only if there is no cycle and is used to schedule dependent tasks.

Example. With courses Maths before ML, and Python before ML, one valid order is Maths, Python, ML.

Related: Directed acyclic graph, Depth-first search, Cycle detection

The problem of finding the shortest tour that visits each city exactly once and returns to the start. It is NP-hard, so exact solutions take exponential time and practical work uses heuristics or approximations.

Example. Visiting 20 cities has about 20!/2 possible tours, which is far too many to check one by one.

Related: NP-complete, Heuristic

A hierarchical structure of nodes connected by edges, with one root at the top, where each other node has exactly one parent and zero or more children. It naturally represents nested data and enables fast searching when kept ordered.

Example. A folder structure on a laptop is a tree: the root drive contains folders, which contain files and further folders.

Related: Binary tree, Graph, Binary search tree

A systematic way of visiting every node of a tree exactly once. Common orders are preorder (node, left, right), inorder (left, node, right), postorder (left, right, node) and level order (row by row). Inorder on a search tree yields keys in sorted order.

Example. Inorder traversal of a binary search tree holding 30, 10, 50 and 20 prints 10, 20, 30, 50.

Related: Binary tree, Depth-first search, Breadth-first search

A tree in which each edge represents a character and each path from the root spells a prefix, with nodes marking where words end. It supports lookups and prefix searches in time proportional to the word length, independent of how many words are stored.

Example. Storing 'car', 'card' and 'care' shares the path c-a-r, so typing 'car' in a search box quickly lists all three completions.

Related: Tree, Hash table, String matching

A technique that moves two indices through a sequence, often from both ends or at different speeds, to solve a problem in one pass instead of nested loops. It turns many O(n^2) checks into O(n).

Example. To find two numbers summing to 10 in the sorted list [1, 3, 4, 6, 9], move a left pointer up when the sum is too small and a right pointer down when too large.

Related: Sliding window, Binary search, In-place algorithm

A structure that tracks a partition of items into groups and supports two operations: find which group an item belongs to, and union two groups. With path compression and union by rank, each operation takes almost constant time.

Example. Grouping friends into circles: after union(Ravi, Meena) and union(Meena, Sana), find gives the same group for Ravi and Sana.

Related: Kruskal's algorithm, Connected components, Graph

A graph in which each edge has a number attached, such as cost, distance or time. Algorithms on weighted graphs typically find paths or trees with the smallest total weight.

Example. In a road network, the edge Pune-Mumbai may carry weight 150 (kilometres), and the shortest route minimises the sum of weights.

Related: Dijkstra's algorithm, Minimum spanning tree, Graph

Measuring an algorithm's cost on the most unfavourable input of a given size. It gives a guarantee that the running time will never be worse than the bound, which matters for systems with strict response deadlines.

Example. Quicksort with a poor pivot choice on an already sorted array takes O(n^2), even though its typical time is O(n log n).

Related: Big-O notation, Quicksort, Amortized analysis