Data Structures & Algo

Big O describes how time or memory grows as the input grows, ignoring constants: it answers "if n doubles, what happens to the cost?". Indexing a List is O(1), searching it is O(n), and a Map or Set lookup is O(1) on average. The ladder: O(1) index or hash lookup, O(log n) binary search, O(n) one pass, O(n log n) a good sort, O(n²) nested loops over the same data, O(2ⁿ) trying every subset **List**: list[i] and add are O(1) (add is amortized: the backing array occasionally grows by copying), while insert(0, x), removeAt(0) and contains are O(n) **Map / Set**: [], containsKey, add and remove are O(1) on average and O(n) in the worst case, when many keys share a hash code Space counts too: a copy with toList() or a memo table costs O(n) extra memory; state both time and space when you present a solution Constants still matter: for 20 items a linear scan of a List can beat building a Set; Big O is about how the cost grows, not about small inputs

A stack is last-in-first-out, a queue is first-in-first-out. In Dart a plain List makes a fine stack (add and removeLast), and ListQueue from dart:collection is the queue: O(1) at both ends. Stack: push with add, pop with removeLast, peek with last; the call stack, undo history and the navigation stack all work this way Queue: addLast to enqueue, removeFirst to dequeue; a List with removeAt(0) shifts every remaining element, so each dequeue is O(n) Typical stack tasks: balanced brackets, evaluating an expression, "next greater element", a min-stack that returns the minimum in O(1) Typical queue tasks: BFS, level-order tree traversal, processing jobs in arrival order Empty collection: first, last and ListQueue.removeFirst throw StateError when it is empty, and List.removeLast throws RangeError; check isEmpty first

Instead of comparing every element with every other one, remember what you have already seen in a hash-based Set or Map. Each lookup is O(1) on average, so a single pass is enough. Duplicates: Set.add returns false when the value is already there, so the first false is your answer Anagrams and word frequency: count occurrences into a Map<String, int> with update(key, (n) => n + 1, ifAbsent: () => 1) and compare the counts; sorting both strings also works but costs O(n log n) Two-sum: for each x, look up target - x in a map of value → index before inserting x, so an element never pairs with itself The price: O(n) extra memory; on an already sorted list two pointers solve two-sum with O(1) memory

Only when you already hold the node you insert next to or remove: a linked list relinks it in O(1), while a List shifts everything after the index. Reaching element i costs O(n), so for almost everything else List wins. **List is a growable array**: O(1) by index, amortized O(1) add, contiguous memory the CPU cache likes; a linked list allocates an object per element and chases pointers "Fast insert" is a half-truth: finding the insertion point is still O(n); only the relinking is O(1) **Need both ends? Use ListQueue: O(1) add and remove at head and tail, which is what most people want a linked list for dart:collection has one**: LinkedList<E extends LinkedListEntry<E>> is intrusive: each entry knows its list, and entry.unlink() is O(1), handy for a list you reorder often What interviewers check: reversing in place, finding the middle and detecting a cycle with a slow and a fast pointer (Floyd), merging two sorted lists; they test pointer handling, not whether you would ship one

Keep the default LinkedHashMap unless you need something it lacks: HashMap when order is irrelevant and memory is tight, SplayTreeMap when keys must stay sorted or you need range queries, a sorted List with binary search for data built once and read often. **LinkedHashMap / LinkedHashSet** (what {} creates): O(1) average lookup and iteration in insertion order, which keeps output and tests predictable **HashMap / HashSet: the same O(1) average, no order guarantee, slightly less memory per entry SplayTreeMap / SplayTreeSet**: keys always sorted, O(log n) amortized; firstKeyAfter and lastKeyBefore answer "the next event after 10:00" without a scan, and recently used keys get cheaper **Sorted List + lowerBound: O(log n) lookup with the smallest memory footprint, but every insert is O(n) The hash contract**: a key must override == and hashCode together and must not change while it sits in the map, or lookups silently miss; a poor hashCode degrades every operation towards O(n)

Know insertion sort (O(n²), fast on tiny input), merge sort (O(n log n), stable, O(n) extra memory) and quicksort (O(n log n) on average, O(n²) worst, in place). Dart's List.sort uses insertion sort for short lists and dual-pivot quicksort otherwise, so it is not stable. Bubble sort: O(n²) and slower than insertion sort in practice; know it only to explain why you would not use it Heap sort: O(n log n) even in the worst case and in place, but not stable and unfriendly to the CPU cache; the heap itself is the useful part, for top-K and priority queues Stable means equal elements keep their input order; you need it when you sort by one key on top of an earlier sort by another. mergeSort and insertionSort from package:collection are stable. The n log n floor: no comparison sort beats O(n log n); counting or radix sort reach O(n + k) when keys are small integers, like ages or star ratings In an app: call sort with a comparator instead of writing your own, and sort once where the data arrives, not inside build

Compare scores first, falling through to the name only on a tie, and flip the direction by swapping operands: b.score.compareTo(a.score). List.sort works in place and is not guaranteed stable, so put the tie-breaker in the comparator. The contract: negative if a goes first, zero on a tie, positive if b does; it must be consistent and transitive, or sort quietly returns a scrambled order instead of throwing **Use compareTo, not subtraction**: a.rating - b.rating on doubles returns a double, which is not a valid comparator result No stability guarantee: equal elements may swap, so sorting by name and then by score loses the name order; add the tie-breaker explicitly or use mergeSort from package:collection It sorts in place: on a const list it throws Unsupported operation; copy with List.of(source)..sort(...) or use sorted() from package:collection to get a new list

A random comparator is not a shuffle. Use list.shuffle(): it is Fisher-Yates, runs in O(n), and gives every ordering the same chance. Why the comparator fails: sort needs a consistent, transitive comparator; a random one contradicts itself, so the result is decided by the sort's pivots rather than by chance. The bias is measurable, and you pay O(n log n) for it. What Fisher-Yates does: walk from the end, pick j = rng.nextInt(i + 1), swap i and j. The classic bug is nextInt(a.length) instead of nextInt(i + 1), which is biased again. Making it testable: pass Random(42) for a deterministic test, Random.secure() when the order is worth money Two Flutter traps: shuffle mutates, so copy first with List.of(source)..shuffle(); and shuffling inside build reorders the deck on every rebuild

When a[mid] < target, mid is already ruled out, yet lo = mid keeps it. Once only one candidate is left (hi - lo == 1), mid == lo, nothing shrinks and the loop spins forever; write lo = mid + 1. The invariant: the answer always lies between lo and hi inclusive, where hi == a.length means "no such element"; every branch must shrink that range, and hi = mid is safe because floor division keeps mid < hi Why it finds the first duplicate: it searches for a boundary, not for equality: the first position whose value is not less than target, called the lower bound Cost: O(log n) comparisons, about 20 for a million timestamps Use the library: lowerBound(list, value, compare: ...) from package:collection is exactly this function; binarySearch returns an arbitrary index inside a run of duplicates, or -1 End of a run: there is no upperBound; call lowerBound again with the next key, for example day + 1 Common mistake: searching by a different key than the list is sorted by; it never throws, it just returns nonsense

Both replace a nested loop with one pass where each index only moves forward: two pointers walk a sorted list from both ends towards each other, and a sliding window keeps a contiguous range, extending its right edge and pulling the left edge behind it. Two pointers: on a sorted list, if the pair sums to too much move the right pointer left, if too little move the left pointer right; the same shape reverses in place, removes duplicates and merges two sorted lists Sliding window: for the best or the count over a contiguous run: extend to the right, and while the window is invalid shrink it from the left, keeping a running sum or a character count as you go Why it is O(n): each pointer crosses the list at most once, so the total work is at most 2n steps even though there is a loop inside a loop How to spot them: the task says "contiguous subarray" or "substring", or the input is sorted Common mistake: two pointers on unsorted data; sort first or switch to a hash map

Build one prefix-sum array (prefix[i + 1] = prefix[i] + values[i]) and any range total becomes a single subtraction, prefix[r] - prefix[l]. That is O(n) once and O(1) per query. The leading zero slot: one extra 0 at the front removes the special case for l == 0 One fixed window needs less: for a rolling total over the same window on every day, a running sum (add the day that entered, subtract the one that left) is simpler; prefix sums win for arbitrary ranges, such as a date range the user picks Build it where the data changes: in the notifier or view model when the data arrives, never in build; recomputing on every frame is the actual bug Only for invertible operations: sum, count, xor. Min and max have no inverse, so a rolling minimum needs a monotonic deque instead. Money in doubles: subtracting two large prefixes loses precision; keep amounts as int cents

A Dart String is a sequence of UTF-16 code units, so reversing it unit by unit tears apart every character that needs more than one. The correct version is s.characters.toList().reversed.join() from package:characters. Code units: s.split('').reversed.join() swaps the halves of a surrogate pair and you get replacement boxes; the same counting is why one emoji reports length == 2 Runes: String.fromCharCodes(s.runes.toList().reversed) fixes surrogate pairs, but a flag, a family emoji or a letter with a combining accent still breaks, because each is several code points glued together Characters: package:characters walks what the user sees, the grapheme clusters, and it already ships with Flutter The same trap nearby: substring can cut a character in half; truncate with s.characters.take(100), and compare graphemes in a palindrome check

Every call takes a stack frame, so depth that grows with the input (a long linked list, a deep folder tree) ends in a StackOverflowError. Naive fib(n) has a different problem: it recomputes the same values, O(2ⁿ); caching each result makes it O(n). Base case first: a missing or unreachable base case is the usual cause of an overflow on small input No tail-call optimisation: Dart does not turn tail calls into loops, so even a tail-recursive function grows the stack Safe depth: bounded and small, such as a balanced tree (depth about log n); the exact limit varies with the platform and the frame size, so do not design around a number Memoization does not fix depth: memoized fib(100000) still recurses 100,000 frames deep on the first call; the bottom-up loop needs no stack and O(1) memory Converting: DFS becomes a loop over an explicit List stack, BFS a loop over a ListQueue The number overflows too: fib(93) no longer fits in a 64-bit int, and on the web integers lose precision above 2⁵³; use BigInt for large n

[r, c] builds a new List on every call, and a List is compared by identity, so memo[key] never finds an earlier entry. The memo never hits: the search stays exponential, and the map gains one dead entry per call. Why: List does not override == and hashCode, so [1, 2] == [1, 2] is false; a Map key matches only the very same list object The fix: key by a record, (r, c): records get value-based == and hashCode for free, so a cell finds its cached count. The 14×14 grid drops from over ten seconds to about a millisecond, and the memo holds at most rows × columns entries. Worse than no memo: every call still allocates a list and adds a map entry nobody reads, so memory grows with the exponential number of calls, not with the grid Other keys that work: r * cols + c as an int (the cheapest), a 2D List<List<int?>> table, or a String such as '$r,$c'; a class used as a key needs its own == and hashCode Catching it: check memo.length after a run: it must never exceed the number of states; a test on a 20×20 grid with a timeout catches the blow-up

Almost every tree question is solved by one of two traversals: DFS goes as deep as it can before backing up, BFS visits the tree level by level using a queue. DFS in three orders: pre-order (node, left, right) to copy or serialise a tree; in-order (left, node, right) yields a BST's values sorted; post-order (left, right, node) when children must be handled first, like height or a bottom-up sum BFS: put the root into a ListQueue, take a node, add its children; use it for level-by-level output, the nearest match or the shortest path in edges How to write them: DFS is shortest as recursion, but use an explicit stack when the tree can be deep; BFS is always a loop, and reading queue.length at the start of a level splits the output by level Validating a BST: check each node against a min/max range passed down, or check that an in-order walk is strictly increasing; comparing a node only with its direct children is the classic wrong answer Common mistake: forgetting the null check on a child, or recursing down a degenerate, list-shaped tree until StackOverflowError

Two linear operations sit inside the loop: queue.removeAt(0) shifts every remaining element, and visited.contains scans a List. Use a ListQueue with removeFirst() and a Set<int> for visited, and the search is back to O(V + E). **removeAt(0)**: a List is an array, so removing the head moves every remaining element down; with a wide frontier that adds up to O(V²) **List.contains**: a linear scan for every edge, O(V · E) in total; a Set lookup is O(1) on average **if (visited.add(next))**: Set.add returns whether the value was new, so the check and the insert become one call Mark on enqueue, not on dequeue: this code already does it right; marking on dequeue lets the same node enter the queue many times Spotting it in review: removeAt(0), insert(0, ...) or contains on a List inside a loop is a hidden inner loop

One visited set cannot tell "fully explored" from "still on the current path", so any task reached twice (config in the diamond auth → config, db → config) is reported as a cycle. Only an edge back to a node on the current DFS path is a cycle. Why: in a directed graph two paths may meet at the same node without forming a loop; the single-set check is copied from undirected graphs, where reaching a visited node other than the parent does mean a cycle The fix: a second set, onPath: add the task before visiting its dependencies and remove it after. A dependency in onPath is a back edge, a real cycle; one that is only in visited was explored earlier and is skipped. This is the white–grey–black colouring from textbooks. Cost: still O(V + E): every task is explored once, the fix adds one O(1) lookup per edge Alternative: Kahn's algorithm: repeatedly take tasks with no remaining incoming edges; whatever is left over is on a cycle or depends on one, and you get the start-up order as a by-product Catching it: test a diamond, not only a chain and a loop: a chain and a two-task loop both pass with the buggy version

BFS finds the shortest path when every edge costs the same, Dijkstra once edges have non-negative weights, and topological sort orders a graph of dependencies. BFS shortest path: a queue plus a distance per node; the first time you reach a node is by the fewest edges. O(V + E). Dijkstra: the same idea with a priority queue keyed by the distance so far. O((V + E) log V). Negative weights break it, and then you need Bellman-Ford. No decrease-key in Dart: HeapPriorityQueue from package:collection cannot lower a priority in place, so push a duplicate entry and skip stale ones when they come out Topological sort: an order in which every edge u→v puts u before v; it exists only without cycles. Kahn's algorithm repeatedly takes nodes with no remaining incoming edges; if some are left over, there is a cycle. Where it shows up in apps: ordering startup tasks or module initialisation by their dependencies, routing between stops, "degrees of separation" in a social graph Representation: an adjacency map Map<Node, List<Edge>> is O(V + E) memory; an adjacency matrix is O(V²) and only pays off for dense graphs

It is dynamic programming when two things hold at once: the answer is built from answers to smaller versions of the same problem, and a naive recursion would solve the same smaller problem over and over. If only the first holds, it is divide and conquer, like merge sort, not DP. The repetition is what memoization pays off. Start with the brute force: write the plain recursion and get it right on a tiny input first Name the state: the smallest set of values that determines an answer: an index, the capacity left, the last item taken Add a memo keyed by that state: same code, exponential becomes polynomial; that is top-down DP. Cost = number of states × work per state. Then, if needed, a table: bottom-up has the same complexity, no recursion depth (top-down for an amount of 100,000 is 100,000 frames), and often only the last row or two must be kept Say it in words first: "dp[i] is the fewest coins that make amount i" is what interviewers want to hear before any code

results.add(path) stores the same list object every time. Backtracking keeps mutating that one path and undoes each choice, so once the recursion unwinds it is empty; the leaf must save a snapshot, results.add(List.of(path)). The shape is choose (path.add), explore (recurse), un-choose (path.removeLast()); that last line is what makes it backtracking rather than a search that never comes back. **Prune with break**: sort the candidates and stop the loop once nums[i] > remaining; with positive numbers every later branch fails too. This version keeps exploring with a negative remaining. Skip duplicates at the same depth: if (i > start && nums[i] == nums[i - 1]) continue; Combinations vs permutations: a start index forbids reusing earlier elements; recurse with i instead of i + 1 to allow reuse, and track a used list when order matters The cost: subsets are O(2ⁿ · n), permutations O(n! · n); the extra n is the copy at each leaf, so cap the result count or yield lazily with sync* Memoization does not rescue enumeration: DP can count the solutions in polynomial time, but listing them is as large as the output

Keep a min-heap of exactly K elements: push each incoming score and pop the smallest whenever the heap grows past K. What remains at the end is the top 100, for O(n log K) time and O(K) memory. Sorting all ten million is O(n log n) and needs every event in memory at once, which a stream does not give you. K largest needs a MIN-heap: its root is the weakest survivor, so one comparison with heap.first rejects most incoming values before any insert. K smallest needs a max-heap; mixing them up is the classic slip. In Dart: dart:collection has no heap; use HeapPriorityQueue from package:collection with your comparator How the heap works: an array where the children of index i sit at 2i + 1 and 2i + 2; add sifts the new value up, removeFirst moves the last element to the root and sifts it down, both O(log K) Draining costs K log K: popping everything yields ascending order, so reverse it for a leaderboard When the heap stops paying: if everything fits in memory and the order inside the top K does not matter, quickselect is O(n) on average; if K approaches n, just sort Edge cases: fewer than K inputs, k == 0, and ties at the cut line; add a second key if the result must be deterministic

A hash map plus a doubly-linked list gives O(1) get and put; in Dart the default Map is a LinkedHashMap that keeps insertion order, so remove-and-reinsert on every hit and evicting keys.first does the same in a few lines. **get: remove the key and put it back with the same value, which moves it to the most-recent end; return null on a miss put**: remove any existing entry first. A plain map[k] = v replaces the value but keeps the old position, and that one line quietly turns an LRU into a FIFO. Evict: while length > capacity, remove(keys.first); keys.first is one iterator step, not a scan Capacity 0: the while loop would evict the entry you just added; decide whether that means "cache nothing" or reject the value Not shared across isolates: each isolate has its own heap, so every isolate gets its own cache

Union-Find, a disjoint-set forest: every record points at a parent, find walks up to the root, and two records are the same person exactly when their roots match. Path compression: on the way out of find, re-point every node you passed straight at the root, so the next query is one hop Union by size: hang the smaller tree under the bigger root; without it a chain of merges degenerates into a list and find slows to O(n). With both tricks a query costs effectively O(1) (inverse Ackermann). Why not a graph traversal: BFS is O(V + E) per query, and you ask a million times; merging sets by copying members is O(n) per union Cycle detection for free: union returning false means the two were already connected, so that edge closes a cycle What it cannot do: it never splits, so an "unmerge" button needs a log to rebuild from; and it answers "same group?" and nothing else, no path and no member list In Dart: parents in a Map with ids registered lazily; write find as a loop, because there is no tail-call optimisation and a long chain overflows the stack

Build a trie (prefix tree) once instead of scanning on every keystroke: the query walks m nodes and reads off the completions, so the cost per keystroke stops depending on how many cities there are. How it works: each node holds a Map<String, TrieNode> of children; a lookup walks the m nodes of the prefix. Storing the best few completions in each node at index time skips the DFS below it, so a query is O(m) plus the size of the answer. The version you may ship instead: sort the names once, then lowerBound(names, query) and take the run while startsWith(query) holds: O(log n + k), a plain List<String>, far less memory than a trie Normalise both sides at index time: lowercase and fold diacritics, or "Zurich" will never find "Zürich" Debounce about 150 ms and drop stale results: otherwise you render the answer to a prefix the user has already replaced **Build the index in Isolate.run**: indexing 80,000 rows is pure CPU work and has no business on the UI isolate, let alone in build Prefixes only: matching in the middle of a word needs an n-gram index, typo tolerance a bounded edit distance walked over the trie