Free Handbook · Every example compiled & verified

Problem Solving

A repeatable way to crack coding problems in Java: read it, break it down, test small cases, then apply one of eight patterns that cover most interviews.

0 / 142 lessons🔥 0 day streak

ShareX LinkedIn

Module 14 · what you'll be able to do

Turn a problem statement into inputs, outputs, constraints and edge cases before writing any code
Test a solution with a tiny hand-rolled harness of small cases instead of guessing
Estimate the Big-O a problem needs from its input limits, in plain English
Recognise and apply eight patterns: two pointers, sliding window, hash map, stack, backtracking, sorting, BFS/DFS and DP-lite

Read the problem before touching the keyboard

Most failed coding rounds fail in the first two minutes: the candidate starts typing a solution to a problem they have not fully read. Slow down and write these five things down (in a comment, on the whiteboard, or out loud) before any code.

1
Restate it
One sentence, in your own words. "Given a list of prices, return the biggest profit from one buy followed by one sell."
2
Inputs and outputs, with types
int[] prices in, int out. Can the array be empty? What is returned then?
3
Constraints
How big is n? Can values be negative? Duplicates? Sorted? These decide the algorithm (see the Big-O lesson below).
4
Two examples by hand
One normal, one tricky. Work them out on paper. If you cannot do it by hand, you cannot code it.
5
Edge cases
Empty input, one element, all equal, already sorted, huge values that overflow int.

javaMain.java

public class Main {
    // Restated: best profit from one buy then one later sell; 0 if prices only fall.
    // Input: int[] prices (may be empty). Output: int >= 0.
    static int maxProfit(int[] prices) {
        int lowest = Integer.MAX_VALUE, best = 0;
        for (int price : prices) {
            lowest = Math.min(lowest, price);          // cheapest buy so far
            best = Math.max(best, price - lowest);     // sell today?
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxProfit(new int[] {7, 1, 5, 3, 6, 4}));   // normal: buy 1, sell 6
        System.out.println(maxProfit(new int[] {7, 6, 4, 3, 1}));      // only falls
        System.out.println(maxProfit(new int[] {}));                   // empty
        System.out.println(maxProfit(new int[] {5}));                  // one day
    }
}

Outputcompiled & run with real Java

The comments at the top are the reading step. The four calls in main are the examples and edge cases from that step, not an afterthought.

Break it down and test with small cases

Break the problem into pieces you can test separately: a helper that checks one thing, a loop that applies it. Then test with the smallest inputs that could break it. In an interview, and in your own practice, a tiny check helper is faster than a test framework and shows the interviewer you verify your own code.

javaMain.java

public class Main {
    static boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            char a = s.charAt(i), b = s.charAt(j);
            if (!Character.isLetterOrDigit(a)) { i++; continue; }
            if (!Character.isLetterOrDigit(b)) { j--; continue; }
            if (Character.toLowerCase(a) != Character.toLowerCase(b)) return false;
            i++; j--;
        }
        return true;
    }

    static int passed = 0, failed = 0;
    static void check(String input, boolean expected) {
        boolean got = isPalindrome(input);
        if (got == expected) passed++;
        else { failed++; System.out.println("FAIL \"" + input + "\": expected " + expected + ", got " + got); }
    }

    public static void main(String[] args) {
        check("", true);                          // empty
        check("a", true);                         // one char
        check("ab", false);                       // smallest false case
        check("Aba", true);                       // case
        check("A man, a plan, a canal: Panama", true);
        check("race a car", false);
        check(".,", true);                        // only punctuation
        System.out.println(passed + " passed, " + failed + " failed");
    }
}

Outputcompiled & run with real Java

7 passed, 0 failed

Your turn

Break the method on purpose (drop the toLowerCase calls) and watch exactly which case reports FAIL. That is how a good small-case list pinpoints bugs.

The order to test in

Empty, one element, two elements, the example from the problem, then one case that targets each branch of your code. Small inputs make a wrong answer obvious by eye.

Big-O in plain English

Big-O answers one question: if the input gets ten times bigger, how much slower does this get? O(n) gets ten times slower. O(n²) gets a hundred times slower. O(log n) barely notices. A Java program does very roughly 10⁸ simple operations per second, which turns the constraints in a problem statement into a direct hint about which algorithm is expected.

Rules of thumb, not laws. They are good enough to rule out the wrong approach before you write it.
If n is up to…	You can afford	Typical approach
10 to 20	O(2ⁿ) or O(n!)	Backtracking: try every subset or ordering
~500	O(n³)	Three nested loops, small DP tables
~5,000	O(n²)	Two nested loops, 2-D DP
~10⁶	O(n log n)	Sort first, heap, binary search inside a loop
~10⁸	O(n)	One pass: two pointers, sliding window, hash map
Anything larger	O(log n) or O(1)	Binary search on the answer, a formula

javaMain.java

import java.util.HashSet;
import java.util.Set;

public class Main {
    static long ops;

    static boolean hasDuplicateNested(int[] a) {            // O(n^2)
        for (int i = 0; i < a.length; i++)
            for (int j = i + 1; j < a.length; j++) { ops++; if (a[i] == a[j]) return true; }
        return false;
    }

    static boolean hasDuplicateSet(int[] a) {               // O(n)
        Set<Integer> seen = new HashSet<>();
        for (int x : a) { ops++; if (!seen.add(x)) return true; }
        return false;
    }

    public static void main(String[] args) {
        for (int n : new int[] {1_000, 10_000}) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = i;           // no duplicates: worst case
            ops = 0; hasDuplicateNested(a); long nested = ops;
            ops = 0; hasDuplicateSet(a);    long set = ops;
            System.out.println("n=" + n + "  nested=" + nested + "  set=" + set);
        }
    }
}

Outputcompiled & run with real Java

n=1000  nested=499500  set=1000
n=10000  nested=49995000  set=10000

Ten times the input: the nested version does a hundred times the work, the set version ten times. At n = 10⁶ the nested version would need half a trillion comparisons.

Pattern 1: two pointers

Signal: a sorted array (or a string) and a question about pairs, or "in place". Put one index at each end and move them towards each other based on a comparison. Each step discards a whole row of candidate pairs, so an O(n²) "try every pair" becomes O(n).

javaMain.java

import java.util.Arrays;

public class Main {
    // sorted input: indices of two numbers that add up to target
    static int[] pairSum(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i < j) {
            int sum = a[i] + a[j];
            if (sum == target) return new int[] {i, j};
            if (sum < target) i++;        // need bigger: move the left pointer up
            else j--;                     // need smaller: move the right pointer down
        }
        return new int[0];
    }

    public static void main(String[] args) {
        int[] a = {1, 3, 4, 6, 8, 11};
        System.out.println(Arrays.toString(pairSum(a, 10)));
        System.out.println(Arrays.toString(pairSum(a, 2)));
    }
}

Outputcompiled & run with real Java

[2, 3]
[]

VisualizepairSum({1, 3, 4, 6, 8, 11}, 10)Step 1 / 11

1int i = 0, j = a.length - 1;
2while (i < j) {
3    int sum = a[i] + a[j];
4    if (sum == target) return new int[] {i, j};
5    if (sum < target) i++;
6    else j--;
7}

Line 1

Pointers at both ends.

Variables now

`i`	`0`
`j`	`5`

All 11 steps as a table

Step	Line	What happened	Variables now
1	1	Pointers at both ends.	`i = 0` `j = 5`
2	3	1 + 11 = 12, too big.	`sum = 12`
3	6	Nothing pairs with 11 now, so drop it.	`j = 4`
4	3	1 + 8 = 9, too small.	`sum = 9`
5	5	Nothing pairs with 1, so drop it.	`i = 1`
6	3	3 + 8 = 11, too big.	`sum = 11`
7	6	Drop 8.	`j = 3`
8	3	3 + 6 = 9, too small.	`sum = 9`
9	5	Drop 3.	`i = 2`
10	3	4 + 6 = 10.	`sum = 10`
11	4	Found: indices 2 and 3.

Pattern 2: sliding window

Signal: "longest / shortest / best contiguous subarray or substring such that…". Grow a window by moving its right edge; when the window breaks the rule, shrink it from the left. Each index enters and leaves the window at most once, so it is O(n).

javaMain.java

import java.util.HashMap;
import java.util.Map;

public class Main {
    // length of the longest substring with no repeated character
    static int longestUnique(String s) {
        Map<Character, Integer> lastSeen = new HashMap<>();
        int best = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            Integer prev = lastSeen.get(c);
            if (prev != null && prev >= left) left = prev + 1;   // jump past the repeat
            lastSeen.put(c, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    // fixed-size window: biggest sum of any k consecutive numbers
    static int maxSumK(int[] a, int k) {
        int sum = 0;
        for (int i = 0; i < k; i++) sum += a[i];
        int best = sum;
        for (int i = k; i < a.length; i++) {
            sum += a[i] - a[i - k];          // slide: add the new, drop the old
            best = Math.max(best, sum);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(longestUnique("abcabcbb") + " " + longestUnique("bbbb") + " " + longestUnique("pwwkew"));
        System.out.println(maxSumK(new int[] {2, 1, 5, 1, 3, 2}, 3));
    }
}

Outputcompiled & run with real Java

3 1 3
9

Your turn

Write minLengthAtLeast(int[] a, int target): the shortest contiguous run of positive numbers whose sum is at least target. Grow right, then shrink left while the sum still qualifies.

Pattern 3: hash map lookups

Signal: "have I seen X before?", "count occurrences", "find the complement". Trade memory for time: store what you have seen in a HashMap or HashSet, and each lookup is O(1) instead of another loop. This is the single most common interview pattern.

javaMain.java

import java.util.*;

public class Main {
    // unsorted input: indices of two numbers adding to target (the classic "Two Sum")
    static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> indexOf = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer j = indexOf.get(target - nums[i]);
            if (j != null) return new int[] {j, i};
            indexOf.put(nums[i], i);
        }
        return new int[0];
    }

    // group words that are anagrams of each other
    static Collection<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> groups = new TreeMap<>();
        for (String w : words) {
            char[] key = w.toCharArray();
            Arrays.sort(key);
            groups.computeIfAbsent(new String(key), k -> new ArrayList<>()).add(w);
        }
        return groups.values();
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(twoSum(new int[] {3, 8, 2, 11, 7}, 9)));
        System.out.println(groupAnagrams(new String[] {"eat", "tea", "tan", "ate", "nat", "bat"}));
    }
}

Outputcompiled & run with real Java

[2, 4]
[[bat], [eat, tea, ate], [tan, nat]]

The sorted letters are the key: "eat", "tea" and "ate" all sort to "aet". A TreeMap keeps the group order deterministic for printing.

Pattern 4: stack

Signal: matching pairs (brackets, tags), "the next greater / smaller element", undo, or evaluating expressions. A monotonic stack keeps indices whose values are still waiting for an answer; when a bigger value arrives, it resolves everything smaller on top of the stack. Every index is pushed and popped once: O(n).

javaMain.java

import java.util.*;

public class Main {
    // for each day, how many days until a warmer temperature (0 if never)
    static int[] daysUntilWarmer(int[] temps) {
        int[] answer = new int[temps.length];
        Deque<Integer> waiting = new ArrayDeque<>();          // indices, temps decreasing
        for (int i = 0; i < temps.length; i++) {
            while (!waiting.isEmpty() && temps[i] > temps[waiting.peek()]) {
                int day = waiting.pop();
                answer[day] = i - day;
            }
            waiting.push(i);
        }
        return answer;
    }

    // evaluate reverse Polish notation: "3 4 + 2 *" = (3 + 4) * 2
    static int rpn(String expr) {
        Deque<Integer> st = new ArrayDeque<>();
        for (String tok : expr.split(" ")) {
            switch (tok) {
                case "+" -> st.push(st.pop() + st.pop());
                case "*" -> st.push(st.pop() * st.pop());
                case "-" -> { int b = st.pop(), a = st.pop(); st.push(a - b); }
                default -> st.push(Integer.parseInt(tok));
            }
        }
        return st.pop();
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(daysUntilWarmer(new int[] {73, 74, 75, 71, 69, 72, 76, 73})));
        System.out.println(rpn("3 4 + 2 *") + " " + rpn("10 3 -"));
    }
}

Outputcompiled & run with real Java

[1, 1, 4, 2, 1, 1, 0, 0]
14 7

For subtraction the order matters: the first pop is the right-hand operand. Pop into named variables whenever the operator is not commutative.

Pattern 5: recursion and backtracking

Signal: "all combinations", "all permutations", "every way to…", and small n (roughly 20 or fewer). Build a candidate one choice at a time; recurse; then undo the choice (backtrack) and try the next one. The shape is always: choose, explore, un-choose.

javaMain.java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static void subsets(int[] nums, int start, List<Integer> current, List<List<Integer>> out) {
        out.add(new ArrayList<>(current));            // copy: current keeps changing
        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);                      // choose
            subsets(nums, i + 1, current, out);        // explore
            current.remove(current.size() - 1);        // un-choose
        }
    }

    static void permutations(String prefix, String rest, List<String> out) {
        if (rest.isEmpty()) { out.add(prefix); return; }
        for (int i = 0; i < rest.length(); i++) {
            permutations(prefix + rest.charAt(i), rest.substring(0, i) + rest.substring(i + 1), out);
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> subs = new ArrayList<>();
        subsets(new int[] {1, 2, 3}, 0, new ArrayList<>(), subs);
        System.out.println(subs);
        List<String> perms = new ArrayList<>();
        permutations("", "abc", perms);
        System.out.println(perms);
    }
}

Outputcompiled & run with real Java

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
[abc, acb, bac, bca, cab, cba]

Forgetting new ArrayList<>(current) is the classic bug: every entry in out would be the same list object, emptied by the end.

Your turn

Add a target: print only the subsets of {2, 3, 5, 7} that sum to 10. Prune by returning early once the running sum passes 10.

Pattern 6: sort first

Signal: intervals, "closest", "meeting rooms", duplicates, or anything where order would make the answer obvious. Sorting costs O(n log n) once and often turns the rest into a single O(n) pass.

javaMain.java

import java.util.*;

public class Main {
    static List<int[]> merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(iv -> iv[0]));
        List<int[]> out = new ArrayList<>();
        for (int[] iv : intervals) {
            if (!out.isEmpty() && iv[0] <= out.get(out.size() - 1)[1]) {
                int[] last = out.get(out.size() - 1);
                last[1] = Math.max(last[1], iv[1]);    // overlap: extend
            } else {
                out.add(iv);                            // gap: start a new one
            }
        }
        return out;
    }

    public static void main(String[] args) {
        int[][] meetings = {{8, 10}, {1, 3}, {2, 6}, {15, 18}, {17, 20}};
        StringBuilder sb = new StringBuilder();
        for (int[] iv : merge(meetings)) sb.append(Arrays.toString(iv)).append(' ');
        System.out.println(sb.toString().trim());
    }
}

Outputcompiled & run with real Java

[1, 6] [8, 10] [15, 20]

Unsorted, you would compare every interval with every other one. Sorted by start, an interval can only overlap the one just before it.

Pattern 7: BFS and DFS on a grid

Signal: a grid, a maze, a network, "connected", "reachable", "fewest steps". Treat each cell as a node with up to four neighbours. DFS answers "how many separate regions?"; BFS answers "shortest number of moves?".

javaMain.java

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    static int countIslands(char[][] g) {
        int count = 0;
        for (int r = 0; r < g.length; r++)
            for (int c = 0; c < g[0].length; c++)
                if (g[r][c] == '#') { count++; sink(g, r, c); }
        return count;
    }

    static void sink(char[][] g, int r, int c) {                 // DFS
        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '#') return;
        g[r][c] = '.';
        for (int[] d : DIRS) sink(g, r + d[0], c + d[1]);
    }

    static int shortestPath(String[] maze) {                     // BFS from top-left to bottom-right
        int rows = maze.length, cols = maze[0].length();
        int[][] dist = new int[rows][cols];
        for (int[] row : dist) java.util.Arrays.fill(row, -1);
        Deque<int[]> q = new ArrayDeque<>();
        dist[0][0] = 0;
        q.offer(new int[] {0, 0});
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] d : DIRS) {
                int r = cur[0] + d[0], c = cur[1] + d[1];
                if (r >= 0 && c >= 0 && r < rows && c < cols && maze[r].charAt(c) == '.' && dist[r][c] == -1) {
                    dist[r][c] = dist[cur[0]][cur[1]] + 1;
                    q.offer(new int[] {r, c});
                }
            }
        }
        return dist[rows - 1][cols - 1];
    }

    public static void main(String[] args) {
        char[][] map = {
            "##..#".toCharArray(),
            "#...#".toCharArray(),
            "..#..".toCharArray(),
            "....#".toCharArray()};
        System.out.println("islands: " + countIslands(map));
        System.out.println("steps: " + shortestPath(new String[] {"..#.", ".#..", "....", "#.#."}));
    }
}

Outputcompiled & run with real Java

islands: 4
steps: 6

"Sinking" visited land to . is the visited set, stored in the grid itself. On a very large grid, recursive DFS can overflow the stack; switch to an explicit ArrayDeque stack then.

Pattern 8: DP-lite

Signal: "how many ways", "minimum cost", "maximum value", where the answer for position i depends on the answers just before it. Write the recurrence in words first ("best up to house i = max of skipping it, or robbing it plus best up to i-2"), then fill an array or keep two variables.

javaMain.java

public class Main {
    // ways to climb n stairs taking 1 or 2 steps at a time
    static long climb(int n) {
        long a = 1, b = 1;                    // ways(0), ways(1)
        for (int i = 2; i <= n; i++) { long c = a + b; a = b; b = c; }
        return b;
    }

    // max money robbing houses in a row without robbing two neighbours
    static int rob(int[] houses) {
        int skip = 0, take = 0;               // best so far without / with the previous house
        for (int money : houses) {
            int newTake = skip + money;
            skip = Math.max(skip, take);
            take = newTake;
        }
        return Math.max(skip, take);
    }

    // largest sum of a contiguous subarray (Kadane)
    static int maxSubarray(int[] a) {
        int best = a[0], endingHere = a[0];
        for (int i = 1; i < a.length; i++) {
            endingHere = Math.max(a[i], endingHere + a[i]);
            best = Math.max(best, endingHere);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println("climb(5) = " + climb(5) + ", climb(50) = " + climb(50));
        System.out.println("rob = " + rob(new int[] {2, 7, 9, 3, 1}));
        System.out.println("max subarray = " + maxSubarray(new int[] {-2, 1, -3, 4, -1, 2, 1, -5, 4}));
    }
}

Outputcompiled & run with real Java

climb(5) = 8, climb(50) = 20365011074
rob = 12
max subarray = 6

climb(50) does not fit in an int; that is why it returns long. Check the constraints for overflow as part of reading the problem.

Choosing the pattern

The problem says…	Try first
sorted array, pair / triplet with a sum	Two pointers
longest / shortest contiguous substring or subarray	Sliding window
seen before, count, duplicate, complement	HashMap / HashSet
brackets, next greater, undo, expression	Stack (ArrayDeque)
all combinations / permutations, n ≤ 20	Backtracking
intervals, closest, meeting rooms	Sort first
grid, maze, network, connected, fewest steps	BFS (shortest) / DFS (regions)
how many ways, min cost, max value, depends on previous	DP
top k, k-th largest, merge k sorted	PriorityQueue (Module 13)
sorted data and "smallest X such that…"	Binary search (Module 13)

Talk while you solve

In a real interview, say the brute force first ("try every pair, O(n²)"), then name the pattern that improves it and why. An interviewer can give credit for a correct plan even if the code runs out of time; silence gives them nothing to grade.

Brute force: The simplest correct solution, usually trying every possibility. State it first, then improve it.
Two pointers: Two indices moving through an array (often from both ends) to avoid a nested loop.
Sliding window: A contiguous range [left, right] that grows on the right and shrinks on the left, processing each element at most twice.
Monotonic stack: A stack whose values stay in increasing or decreasing order; used for next-greater / next-smaller problems.
Backtracking: Recursive search that makes a choice, explores, and then undoes the choice before trying the next.
Recurrence: A formula for an answer in terms of answers to smaller inputs; the heart of every DP solution.
Edge case: An input at the boundary of what is allowed: empty, one element, maximum size, negative, overflow.

Quick check

Constraints say n ≤ 100,000. Which approach is most likely expected?

Quick check

"Find the length of the longest substring with at most two distinct characters." Which pattern fits?

← Module 13Data Structures & Algorithms Module 15 →Interview Questions

Frequently asked questions

How do I get better at solving coding problems in Java?

Practise by pattern, not at random: do three to five problems per pattern (two pointers, sliding window, hash map, stack, backtracking, sorting, BFS/DFS, DP) until you recognise the signal in the problem statement. Always write the brute force first, test with small cases, and state the Big-O out loud.

Which Java collections do I need for coding interviews?

ArrayList, HashMap, HashSet, ArrayDeque (as both stack and queue), PriorityQueue and TreeMap cover nearly every problem. Know Arrays.sort, Collections.sort, Comparator.comparing and Arrays.fill as well.

How do I know which Big-O a problem needs?

Read the input limits. Up to about 20 allows exponential backtracking, a few thousand allows O(n²), around a million needs O(n log n), and larger needs O(n) or binary search. A Java program does roughly 10^8 simple operations per second.

Finish the Java handbook, then get hired

Sit the exam for your certificate, run your resume through the ATS checker, and see the jobs that ask for exactly this.

Check my resume

Found this course useful? Share it.

ShareX LinkedIn

Comments

Join the conversation. Sign in to leave a comment — we'd love to hear your thoughts.