DSA Practice — Learn by Solving

Keep a running total that starts at 0 (remember the "running total" idea from Start Here?).

Loop over the list, and on each item add it to the total.

total = 0; for x in nums: total += x; then total is the answer. O(n). (LeetCode 1480, Running Sum, is a close cousin.)

Imagine reading the numbers one by one — you'd keep track of the biggest you've seen so far.

Start by assuming the first element is the biggest, then update it whenever you find something larger.

best = nums[0]; loop and if x > best: best = x. O(n).

"Even" means divisible by 2 — and % gives the remainder.

Keep a counter; for each number, if x % 2 == 0, add 1.

count = 0; for x in nums: if x % 2 == 0: count += 1. O(n).

range(1, n + 1) gives you 1, 2, ... n (the stop value is excluded, so use n + 1).

Keep a running total and add each i to it inside the loop.

total = 0; for i in range(1, n + 1): total += i. O(n). (Shortcut formula: n * (n + 1) // 2.)

You want n x 1, n x 2, ... n x 10 — the same action ten times with a changing multiplier.

Loop i from 1 to 10 and print n * i each time.

for i in range(1, 11): print(n, "x", i, "=", n * i). O(1) (fixed 10 lines).

If you walk the original from the last element to the first, adding each to a new list, what do you get?

Loop the indices backwards with range(len(nums) - 1, -1, -1), or just append and reverse — or use slicing nums[::-1].

out = []; loop backwards appending; (or the Python one-liner nums[::-1]). O(n).

a is the largest only if it beats both of the others. and checks two things at once.

if a >= b and a >= c: ... elif b >= c: ... else: ....

The if/elif/else chain above (or simply max(a, b, c) once you understand it). O(1).

Use % to test divisibility. Which case is the most specific and must be checked first?

Check "divisible by both 3 and 5" first, then by 3, then by 5, then else the number.

Loop 1..n with an if/elif/elif/else; test i % 3 == 0 and i % 5 == 0 first. O(n).

This is ranges, not exact values, so an if/elif chain fits better than match here.

Check from the highest band down: >= 90 → A, >= 75 → B, >= 50 → C, else Fail. Order matters.

if/elif/elif/else from highest threshold to lowest. O(1).

A palindrome reads the same forwards and backwards. Put one pointer at the start, one at the end.

Move them inward, skipping anything that isn't a letter/number, and compare the two characters (lower-cased). Mismatch → not a palindrome.

Two pointers from both ends; skip non-alphanumeric; compare s[left].lower() with s[right].lower(); move inward. O(n) time, O(1) space.

It's sorted — that's a huge clue. If the current pair sums too high, which pointer should move?

Sum too big → move the right pointer left (smaller). Too small → move left pointer right (bigger).

Two pointers at both ends. If a[l] + a[r] == target you're done; if too big r -= 1, if too small l += 1. O(n), no extra space.

Area is width x min(height of the two lines). Start as wide as possible (both ends).

The width only shrinks as you move in, so move the shorter line inward — it's the one limiting the area, and it's your only chance to find a taller one.

Two pointers at both ends, track max area, always move the pointer at the shorter line. O(n).

You must buy before you sell. Track the cheapest price you've seen so far as you scan left to right.

At each day, the best profit ending today is today's price minus the cheapest-so-far. Keep the maximum.

One pass: keep min_price and best; update best = max(best, price - min_price). O(n).

Grow a window on the right. What do you do when the new character is already inside the window?

Shrink from the left until the duplicate is gone (a set tracks what's in the window). Track the longest length seen.

Sliding window + a set/last-seen dict; move left past the previous copy on a repeat. O(n).

Grow the window until the sum reaches the target — then try to shrink from the left.

While the window sum is at least target, record the length and shrink from the left to look for a smaller one.

Expand right adding to a running sum; while sum >= target, update the min length and subtract arr[left++]. O(n).

You could sort and check neighbours — but a set checks "seen before?" instantly.

Walk the array adding to a set; if a value is already in the set, you found a duplicate.

seen = set(); for each x, if x in seen return True else add it. O(n).

For each number x, you're really looking for one specific value: target - x.

Keep a dict of value → index of numbers you've passed. Check for the complement before adding the current one.

One pass: if target - x is in the dict, return both indices; else store x. O(n) time/space. (This is the same problem worked fully in Start Here.)

Two words are anagrams if they have the same letters. How could you give anagrams the same key?

Sort each word's letters (or count them) — anagrams produce the same sorted string. Use that as a dict key.

dict from sorted-word → list of words; append each word under its sorted key; return the values. O(n·k log k).

When you see an opening bracket, you'll need to remember it. Which one must close first — the most recent one. That's a stack.

Push opening brackets. On a closing bracket, the top of the stack must be its matching opener — pop and check.

Push opens; for each close, pop and verify it matches; at the end the stack must be empty. O(n).

A normal stack can't find its min fast. What if each entry also remembered the min at that point?

Push pairs (value, current-min) — or keep a second stack of mins alongside.

Alongside the main stack, push the running minimum with each value; getMin reads the top of the min stack. All O(1).

Brute force checks every later day (O(n²)). A stack can remember days still waiting for a warmer one.

Keep a stack of indices with decreasing temperatures. When today is warmer than the top, you've found that day's answer — pop it.

Monotonic decreasing stack of indices; pop while current temp is higher, setting their distance. O(n).

Compare the target to the middle element — that tells you which half to keep.

Target bigger than mid → search the right half (lo = mid + 1); smaller → left half (hi = mid - 1).

Standard binary search with lo <= hi and mid = (lo + hi)//2. O(log n).

The array isn't what's sorted — the answer (a speed from 1 to max pile) is. And feasibility is monotonic: if speed s works, every faster speed works too.

Binary search the speed. For a candidate speed, compute the hours needed and check if it's within h.

Binary search on speed in [1, max(piles)]; feasible(s) = sum of ceil(pile/s) ≤ h. This is "binary search on the answer" — see Problem Solving. O(n log max).

You need to flip each node's next to point backwards. Keep track of the node before the current one.

Walk the list with prev and curr; at each step save curr.next, point curr.next = prev, then move both forward.

Iterative three-pointer reverse (prev, curr, nxt); return prev. O(n) time, O(1) space.

A set of visited nodes works (O(n) space). Can you do it with no extra space?

Two pointers, one moving 1 step and one moving 2. If there's a loop, the fast one laps the slow one and they meet.

Floyd's fast/slow pointers; if they ever meet, there's a cycle. O(n) time, O(1) space.

Like merging two sorted piles of cards — always take the smaller current head.

Use a dummy head node; repeatedly attach the smaller of the two current nodes and advance that list.

Dummy node + tail pointer; compare heads, attach smaller, advance; attach the leftover. O(n + m).

The depth of a tree is 1 plus the depth of its taller subtree. That's a recursive definition.

depth(node) = 1 + max(depth(left), depth(right)), with depth(None) = 0.

Recursive DFS returning 1 + max(left, right); base case empty node → 0. O(n).

At every node, what simple thing do you do to its two children?

Swap the left and right child, then invert each subtree recursively.

Recursion: swap children, recurse on both. O(n).

"Level by level" is the signature of BFS — and BFS uses a queue.

Process the queue one whole level at a time: record how many nodes are in the current level, pop exactly that many, and enqueue their children.

BFS with a deque; loop while it's non-empty, taking len(queue) nodes per level. O(n).

Each unvisited piece of land starts a new island. How do you "use up" the whole island so you don't count it twice?

When you find land, flood-fill it (DFS/BFS to all connected land) and mark it visited, then keep scanning.

Scan the grid; on each unvisited 1, increment the count and DFS/BFS to sink the whole island. O(rows·cols).

Courses + prerequisites form a directed graph. When is it impossible to finish everything?

If there's a cycle, you can never start. So: detect a cycle (or do a topological sort).

Topological sort (Kahn's: repeatedly remove zero-in-degree nodes) or DFS cycle detection. O(V + E). See Problem Solving.

Sorting works (O(n log n)). But to keep just the top K, what size heap do you need?

Keep a min-heap of size K. Push each number; if the heap grows past K, pop the smallest. The top is the Kth largest.

Min-heap of size K → answer is heap[0]. O(n log k). (heapq in Python.)

The median sits between the lower half and the upper half. What if you kept those two halves separately?

A max-heap for the lower half and a min-heap for the upper half, kept balanced in size. The median is the top(s).

Two heaps balanced to differ by ≤1; median is the top of the larger, or the average of both tops. Insert O(log n), median O(1).

For each element you have two choices: include it, or don't. That's a branching tree of decisions.

Recurse with an index; at each step, recurse with the current element and without it (remember to undo when you backtrack).

Backtracking: at index i, add nums[i], recurse, then remove it and recurse. O(2ⁿ).

Build the permutation one position at a time, picking an unused number for each spot.

Track which numbers are used; choose an unused one, recurse, then un-choose it.

Backtracking with a used set / path; when the path length equals n, record it. O(n·n!).

To reach step n, your last move came from step n-1 (a 1-step) or n-2 (a 2-step).

So ways(n) = ways(n-1) + ways(n-2) — it's Fibonacci. Build it up from the bottom.

dp[i] = dp[i-1] + dp[i-2], base dp[0]=dp[1]=1. O(n), and O(1) with two variables.

At each house you choose: rob it (and skip the previous) or skip it. What's best up to here?

best(i) = max(best(i-1), best(i-2) + money[i]) — skip this house, or take it plus best two back.

1-D DP with that recurrence; keep two rolling values. O(n), O(1) space.

To make amount a, try each coin c: then you still need a - c, which is a smaller version of the same problem.

dp[a] = 1 + min(dp[a - c]) over all coins c that fit; dp[0] = 0.

Bottom-up DP over amounts 0..target; for each, try every coin. O(amount · coins).

Scan left to right keeping a running sum. When would carrying the running sum forward hurt you?

If the running sum goes negative, drop it (start fresh from the next element) — it can only drag the next subarray down. Track the best seen.

Kadane's algorithm: cur = max(x, cur + x), best = max(best, cur). O(n).

Track the farthest index you can currently reach as you scan.

If you ever stand on an index beyond your farthest reach, you're stuck. Otherwise update the reach with i + nums[i].

Greedy: keep farthest; if i > farthest return False; else farthest = max(farthest, i + nums[i]). O(n).

Re-adding the range every query is O(n) each. What could you precompute once so each query is O(1)?

Build a prefix-sum array where prefix[k] is the sum of the first k elements. Then the range sum is a subtraction.

Precompute prefix; sumRange(i, j) = prefix[j+1] - prefix[i]. Build O(n), query O(1).

A subarray sum is a difference of two prefix sums. So you want two prefix sums that differ by k.

As you scan, keep a running prefix sum and a dict counting how many times each prefix sum has appeared. For the current sum, how many earlier prefixes equal sum - k?

Running prefix sum + a dict of prefix-sum counts; add count[sum - k] each step. O(n) — combines prefix sums with hashing.

Overlaps are easiest to see when intervals are in order — what should you sort by first?

Sort by start. Walk through; if the current interval's start is ≤ the last merged interval's end, they overlap — extend the end. Otherwise start a new one.

Sort by start; iterate merging when cur.start <= last.end (extend last.end), else append. O(n log n).

This is a greedy scheduling problem. If two overlap, which one should you keep to leave the most room for the rest?

Sort by end time; greedily keep the interval that finishes earliest, and remove any later one that overlaps it.

Sort by end; track the last kept end; count an interval as "removed" when its start is before that end. O(n log n). (A greedy classic — see Problem Solving.)

A hash map counting occurrences works (O(n) space). But there's an O(1)-space trick hiding in how pairs behave.

XOR-ing a number with itself gives 0. So XOR the whole array — every pair cancels and only the lonely number is left.

result = 0; XOR every element into it; return result. O(n) time, O(1) space.

You could check each bit with a shift and a mask (n & 1, then n >>= 1). There's also a neat trick that only loops once per set bit.

n & (n - 1) clears the lowest set bit. Keep doing it and counting until n becomes 0.

Loop n &= n - 1 and count iterations — runs once per set bit. O(number of set bits).

Each node should have a link for each possible next character, plus a flag marking "a word ends here."

To insert, walk/create a node per character. To search, walk and check the end-flag; for startsWith, just check the path exists.

Nodes with a children map + is_end flag; all operations walk the characters. O(word length) each.

Normal letters walk one path. What should a . do — it can match any child.

On a ., recurse into every child node and succeed if any branch matches the rest of the word.

Trie + DFS search; on . try all children recursively. O(word length) typical, more with many wildcards.

Rotating is hard to do directly in place. Is there a combination of two simpler operations that equals a rotation?

Transpose the matrix (swap m[i][j] with m[j][i]), then reverse each row. That equals a 90° clockwise rotation.

Transpose in place, then reverse every row. O(n²) time, O(1) extra space.

Treat each land cell as a node connected to its 4 neighbours. Counting islands = counting connected components.

Scan the grid; on each unvisited land cell, DFS/BFS to its connected neighbours and mark them visited, then continue.

Nested loops + flood-fill (DFS/BFS) from each unvisited 1. O(rows·cols). Grid problems and graph problems are often the same thing.

Start by assuming every node is its own group. Each edge then joins two groups.

Use union-find: for each edge, union its two endpoints. Each successful union reduces the group count by one.

Union-find with path compression; start count at n, decrement on each merge of two different roots. ~O(edges).

Add edges one by one. A cycle appears the moment you connect two nodes that are already connected.

For each edge, if find(a) == find(b) they're already in the same group — that edge is the redundant one. Otherwise union them.

Union-find; the first edge whose endpoints share a root is the answer. ~O(edges).

To reach a cell, your last move came from the cell above or the cell to the left.

So paths(r, c) = paths(r-1, c) + paths(r, c-1), with the top row and left column all equal to 1 (only one way along an edge).

Fill a 2-D table with that recurrence (or one row, rolling). O(rows·cols).

Compare the two strings character by character. When the current characters match, what does that add to the answer?

If a[i] == b[j], it's 1 + LCS(i-1, j-1). If not, it's the better of dropping one character from either string: max(LCS(i-1, j), LCS(i, j-1)).

2-D table dp[i][j] over the two strings with that recurrence; base cases are 0. O(n·m). A classic worth knowing cold — see Problem Solving.