How to solve any DSA problem
A repeatable method for unfamiliar problems: understand it, let the constraints choose the complexity, start from brute force, spot the pattern, optimise, test with edge cases and a stress test, and explain your reasoning.
The method
Understand. Restate the problem in your own words. Work through the examples by hand. Ask what the input and output are exactly, and what happens in edge cases (empty input, one element, duplicates, negative numbers). Read the constraints. The input size tells you the complexity you need (see the widget). n ≤ 20 invites 2ⁿ; n ≤ 10⁵ demands O(n log n). Brute force first. Write down the obvious solution and its complexity, even if it is too slow. It proves you understand the problem, and it becomes your test oracle later. Find the bottleneck and the pattern. What does the brute force repeat? Which clue in the wording points to a known technique? Optimise. Precompute (prefix sums, sorting), trade memory for time (hash maps, memoisation), or change the approach (greedy, DP, graph search). Code it cleanly. Good names, small functions, no cleverness you cannot explain. Test. The examples, then edge cases, then a stress test against the brute force. Analyse. State the final time and space complexity, and why it is correct.
Clues in the wording
| If the problem says… | Think of |
|---|---|
A worked example
int[] loads = { 14, 3, 9, 21, 6, 11 };int limit = 20;Console.WriteLine(BruteForce(loads, limit));Console.WriteLine(SortedPointers(loads, limit));Console.WriteLine(HashLookup(loads, limit)); static (int, int)? BruteForce(int[] a, int target) // O(n^2): every pair{ for (int i = 0; i < a.Length; i++) for (int j = i + 1; j < a.Length; j++) if (a[i] + a[j] == target) return (a[i], a[j]); return null;} static (int, int)? SortedPointers(int[] a, int target) // O(n log n): sort, then close in from both ends{ var s = a.Order().ToArray(); for (int l = 0, r = s.Length - 1; l < r; ) { int sum = s[l] + s[r]; if (sum == target) return (s[l], s[r]); if (sum < target) l++; else r--; } return null;} static (int, int)? HashLookup(int[] a, int target) // O(n): remember what we have seen{ var seen = new HashSet<int>(); foreach (int x in a) { if (seen.Contains(target - x)) return (target - x, x); seen.Add(x); } return null;}(14, 6) (6, 14) (14, 6)
Test like you mean it
Edge cases: empty input, a single element, all elements equal, already sorted, reverse sorted, negative numbers and zero, the largest allowed values (overflow!), no valid answer. Off-by-one: check the first and last positions, inclusive versus exclusive ranges, loops that should run zero times. Stress test: generate thousands of small random inputs, run the slow-but-obvious solution and the fast one, and stop at the first difference. It finds bugs that no hand-written example does.
var rng = new Random(42);for (int test = 1; test <= 1000; test++){ int[] a = Enumerable.Range(0, rng.Next(1, 12)).Select(_ => rng.Next(-20, 21)).ToArray(); int slow = SlowMaxSubarray(a), fast = Kadane(a); if (slow != fast) { Console.WriteLine($"Mismatch on [{string.Join(", ", a)}]: {slow} vs {fast}"); return; }}Console.WriteLine("All 1000 random tests agree"); static int SlowMaxSubarray(int[] a) // obviously correct, O(n^2){ int best = int.MinValue; for (int i = 0; i < a.Length; i++) { int sum = 0; for (int j = i; j < a.Length; j++) { sum += a[j]; best = Math.Max(best, sum); } } return best;} static int Kadane(int[] a) // the fast one we want to trust, O(n){ int best = a[0], here = a[0]; for (int i = 1; i < a.Length; i++) { here = Math.Max(a[i], here + a[i]); best = Math.Max(best, here); } return best;}All 1000 random tests agree
When you are stuck
Solve a smaller or simpler version: n = 1, 2, 3; one dimension instead of two; no constraint X. Draw it: the array with pointers, the graph, the recursion tree, the DP table. Ask what you would precompute if you could: sorted order, prefix sums, positions in a hash map. Reverse it: work backwards from the goal, or ask for the complement (“count the bad ones and subtract”). Binary search on the answer: if “can it be done with X?” is easy to check and gets easier as X grows, search for the smallest X. Model it as a graph: states are nodes, moves are edges, and the answer is a shortest path.
Where to go from here
{ 4, 2, 7, 1, 5 }. For each target in { 5, 13, 20 }, find the first day (0-based) on which the running total reaches the target, or −1 if it never does: 1 2 -1. There may be 100,000 days and 100,000 targets, so each answer must be fast. Name the techniques you combine.
Show a hint
Show the solution
int[] output = { 4, 2, 7, 1, 5 };int[] targets = { 5, 13, 20 }; var prefix = new int[output.Length]; // prefix sums: increasing, because outputs are positivefor (int i = 0; i < output.Length; i++) prefix[i] = output[i] + (i > 0 ? prefix[i - 1] : 0);Console.WriteLine(string.Join(" ", targets.Select(t => FirstDay(prefix, t)))); static int FirstDay(int[] prefix, int target) // lower-bound binary search{ int lo = 0, hi = prefix.Length; // hi = "not found" while (lo < hi) { int mid = (lo + hi) / 2; if (prefix[mid] >= target) hi = mid; else lo = mid + 1; } return lo == prefix.Length ? -1 : lo;}1 2 -1
Remember
Follow a method: understand, read the constraints, brute force, find the pattern, optimise, code, test, analyse. Input limits reveal the intended complexity; the wording reveals the technique. A brute-force solution is your test oracle: stress-test the fast solution against it on small random inputs. When stuck: simplify, draw, precompute, reverse, binary search on the answer, or model it as a graph.