To break down a complex programming problem, work in this order: pin down exactly what is asked using small examples, write the simplest solution even if it is slow, split the work into named pieces that each do one thing, solve and test each piece on its own, then combine and improve. The point is that at every moment you are working on something small enough to hold in your head. This post shows the method on two problems with code you can run.<\/p>\n
The task: given a 9×9 board where “.” means empty, decide whether the filled-in digits break the rules. No row, column or 3×3 box may contain the same digit twice. (It does not have to be solvable, only not already invalid.)<\/p>\n
Doing a row by hand shows the core check: collect the digits, ignore the dots, and see whether any digit appears twice. A column and a box need the same check, only the cells come from different places. So the problem splits into two independent parts:<\/p>\n
def valid_sudoku(board):\n def no_repeats(cells):\n digits = [c for c in cells if c != \".\"]\n return len(digits) == len(set(digits))\n\n def rows():\n return board\n\n def cols():\n return [[board[r][c] for r in range(9)] for c in range(9)]\n\n def boxes():\n for br in range(0, 9, 3):\n for bc in range(0, 9, 3):\n yield [board[r][c] for r in range(br, br + 3) for c in range(bc, bc + 3)]\n\n return all(no_repeats(g) for g in (*rows(), *cols(), *boxes()))\n<\/code><\/pre>\nEach helper is a few lines and can be tested alone. Try no_repeats(list(\"53..7....\"))<\/code> (true) and no_repeats(list(\"55.......\"))<\/code> (false) before you trust the rest. Then test the whole thing:<\/p>\ngood = [list(r) for r in [\n \"53..7....\", \"6..195...\", \".98....6.\",\n \"8...6...3\", \"4..8.3..1\", \"7...2...6\",\n \".6....28.\", \"...419..5\", \"....8..79\"]]\nprint(valid_sudoku(good)) # True\n\nbad = [r[:] for r in good]\nbad[0][0] = \"8\" # now 8 appears twice in column 0\nprint(valid_sudoku(bad)) # False\n<\/code><\/pre>\nA single-pass version with three sets of seen digits per row, column and box is faster in practice, but this version is simpler to get right, and it is the one you can explain in a minute. Start with the clear version, and optimize only if asked.<\/p>\n
Example 2: longest palindromic substring<\/h2>\n
The task: given a string, return its longest substring that reads the same forwards and backwards. By hand on \"babad\"<\/code>: the candidates are \"bab\"<\/code> and \"aba\"<\/code>, both length 3. Notice what you did: you looked at substrings and checked each. That is the brute-force decomposition:<\/p>\n\n- Generate every substring.<\/li>\n
- Check whether it is a palindrome.<\/li>\n
- Keep the longest.<\/li>\n<\/ol>\n
def longest_pal_brute(s):\n best = \"\"\n for i in range(len(s)):\n for j in range(i + 1, len(s) + 1):\n sub = s[i:j]\n if sub == sub[::-1] and len(sub) > len(best):\n best = sub\n return best\n<\/code><\/pre>\nThis is correct and takes O(n\u00b3) time: O(n\u00b2) substrings, each checked in O(n). Now use the structure of the problem to improve one piece. Every palindrome has a center, and it grows outward while the characters on both sides match. So instead of generating substrings and testing them, try each possible center and expand. A palindrome has either a single-character center (odd length) or a between-two-characters center (even length), so there are 2n – 1 centers:<\/p>\n
def longest_pal(s):\n def expand(l, r):\n while l >= 0 and r < len(s) and s[l] == s[r]:\n l -= 1\n r += 1\n return s[l + 1:r]\n\n best = \"\"\n for i in range(len(s)):\n for cand in (expand(i, i), expand(i, i + 1)): # odd, then even\n if len(cand) > len(best):\n best = cand\n return best\n\nfor s in [\"babad\", \"cbbd\", \"a\", \"forgeeksskeegfor\"]:\n print(s, longest_pal_brute(s), longest_pal(s))\n# babad bab bab\n# cbbd bb bb\n# a a a\n# forgeeksskeegfor geeksskeeg geeksskeeg\n<\/code><\/pre>\nThe time is now O(n\u00b2), since each of the 2n – 1 centers expands at most n steps, and space is O(n) for the returned substring. The brute-force version earned its keep here: Comparing both on 300 random strings of a’s and b’s gave results of equal length every time. The strings can differ (both \"aba\"<\/code> and \"bab\"<\/code> could tie), which is why the comparison is on length. There is also an O(n) algorithm (Manacher’s), but it is rarely expected in interviews.<\/p>\nPatterns that help you split a problem<\/h2>\n\n- Stages (pipeline).<\/strong> Parse, then transform, then format. Each stage takes the previous stage’s output.<\/li>\n
- Parts of the data.<\/strong> Rows, columns and boxes (Sudoku); left half and right half (merge sort); each node’s subtree (trees).<\/li>\n
- Solve a smaller case and extend.<\/strong> If you can solve it for n – 1 items, how do you handle the n-th? That is recursion and dynamic programming.<\/li>\n
- Solve an easier version first.<\/strong> Drop a constraint (no duplicates, sorted input, fixed size), solve that, then add it back.<\/li>\n
- Work backwards from the output.<\/strong> What would the last step have to look like?<\/li>\n
- Look for a known pattern.<\/strong> Two pointers, sliding window, hash map, BFS, and so on. Matching a piece to a pattern you know replaces thinking with recall. Our step-by-step approach to coding challenges<\/a> and breaking problems into manageable parts<\/a> cover more of these.<\/li>\n<\/ul>\n
Common mistakes<\/h2>\n\n- Coding before you can do an example by hand.<\/strong> If you cannot do it on paper, the code will not do it either.<\/li>\n
- Pieces that are not independent.<\/strong> If every helper reads and changes the same global variables, you cannot test them separately. Pass values in and return values out.<\/li>\n
- Splitting too early into too many pieces.<\/strong> Three to five parts is usually right at the top level. Split the hard part further when you get to it.<\/li>\n
- Skipping the brute force.<\/strong> You lose both a fallback and a test oracle for your clever version.<\/li>\n
- Never testing the edge cases.<\/strong> Empty input, one element, all elements equal, the largest allowed size.<\/li>\n<\/ul>\n
Using the method in an interview<\/h2>\n
Say the decomposition out loud: “I’ll split this into checking one group, and producing all the groups.” Interviewers are looking for exactly that structure, and it gives them a place to correct you early if you misread the problem. State the brute-force complexity before improving it, name what is wasteful, and then improve one piece at a time. See algorithmic thinking<\/a> for the broader habit.<\/p>\nPractice this way<\/h2>\n
Pick a problem you have already solved and redo it, writing the pieces and their inputs and outputs before any code. Then pick one you could not solve and do the by-hand examples first. Good problems to try next are Valid Parentheses, Merge Intervals and Word Search. AlgoCademy’s step-by-step lessons are built around this idea; the Palindrome Check<\/a> and Sudoku<\/a> exercises are good places to apply it.<\/p>\n","protected":false},"excerpt":{"rendered":"A practical method to break a hard coding problem into small steps: examples first, brute force, helper functions, testing each piece. Worked Python examples.<\/p>\n","protected":false},"author":1,"featured_media":4612,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23],"tags":[],"class_list":["post-4613","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-problem-solving"],"_links":{"self":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/4613"}],"collection":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/comments?post=4613"}],"version-history":[{"count":1,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/4613\/revisions"}],"predecessor-version":[{"id":8735,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/4613\/revisions\/8735"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media\/4612"}],"wp:attachment":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media?parent=4613"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/categories?post=4613"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/tags?post=4613"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}