Free Handbook · Every example compiled & verified

Problem Solving

A repeatable method for coding problems and the eight patterns behind most of them, each worked end to end in idiomatic Kotlin.

0 / 136 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 code
Test a solution against small hand-made cases and a brute-force twin
Explain Big-O in plain English and predict whether a solution is fast enough
Recognise and apply two pointers, sliding window, hash map, stack, backtracking, sorting, BFS/DFS and DP-lite

Read the problem before you type

Most failed coding rounds fail in the first two minutes: the candidate starts typing before they know what is being asked. The fix is a fixed routine you run every time, out loud in an interview and in a comment block at home.

1
Restate it
Say the problem back in one sentence of your own. "Given a list of prices, return the biggest profit from one buy followed by one later sell."
2
Pin down input and output
Types, sizes and ranges. List<Int> or IntArray? Can it be empty? Negative numbers? Return Int, Int? or throw? In Kotlin, deciding whether "no answer" is null is part of the design.
3
Write three examples by hand
A normal case, an edge case (empty, one element, all equal) and a tricky case (the answer is at the very end, duplicates). Work each out on paper — these become your tests.
4
Brute force first
Say the obvious solution and its cost, even if it is O(n²). It proves you understand the problem and gives you something to check the fast version against.
5
Name the pattern, then optimise
Sorted input? Two pointers or binary search. "Longest/shortest contiguous…"? Sliding window. "Have I seen this before?" Hash map. Nested structure or "most recent"? Stack. "All combinations"? Backtracking. Grid or network? BFS/DFS. "How many ways / best value" with overlapping sub-problems? DP.
6
Test with the small cases
Run your three examples, then trace one by hand. Only then talk about further optimisation.

In real jobs

The same routine is how a senior engineer handles a vague ticket: restate it, ask about the edge cases ("what if the upload is empty?"), agree on inputs and outputs, ship the simple version, then optimise with measurements.

Test with small cases and a brute-force twin

A brute-force solution is slow but obviously correct. Keep it next to your fast solution and check both against hand-worked expected answers — if they ever disagree, one of them has a bug and you have a small input that shows it. Kotlin's Pair and destructuring make a tidy table of cases.

kotlinMain.kt

fun maxProfitBrute(prices: List<Int>): Int {          // O(n²), obviously right
    var best = 0
    for (i in prices.indices)
        for (j in i + 1 until prices.size) best = maxOf(best, prices[j] - prices[i])
    return best
}

fun maxProfit(prices: List<Int>): Int {               // O(n), one pass
    var minSoFar = Int.MAX_VALUE
    var best = 0
    for (p in prices) {
        minSoFar = minOf(minSoFar, p)
        best = maxOf(best, p - minSoFar)
    }
    return best
}

fun main() {
    val cases = listOf(
        listOf(7, 1, 5, 3, 6, 4) to 5,
        listOf(7, 6, 4, 3, 1) to 0,
        listOf(5) to 0,
        emptyList<Int>() to 0,
        listOf(2, 2, 2) to 0,
    )
    for ((prices, expected) in cases) {
        val fast = maxProfit(prices)
        val slow = maxProfitBrute(prices)
        val status = if (fast == expected && slow == expected) "ok" else "FAIL"
        println("$prices -> $fast ($status)")
    }
}

Outputcompiled & run with real Kotlin

[7, 1, 5, 3, 6, 4] -> 5 (ok)
[7, 6, 4, 3, 1] -> 0 (ok)
[5] -> 0 (ok)
[] -> 0 (ok)
[2, 2, 2] -> 0 (ok)

Your turn

Add a random tester: generate 1,000 lists with kotlin.random.Random(42) (seeded, so it is repeatable), and print the first list where maxProfit and maxProfitBrute disagree.

Big-O in plain English

Big-O answers one question: if the input gets 10 times bigger, how much more work is there? O(1): none. O(log n): one more step or so. O(n): 10 times more. O(n log n): a bit more than 10 times. O(n²): 100 times more. Constants and small terms are dropped because the growth dominates once n is large.

kotlinMain.kt

fun main() {
    for (n in listOf(10, 100, 1000)) {
        var linear = 0
        for (i in 0 until n) linear++

        var quadratic = 0
        for (i in 0 until n) for (j in 0 until n) quadratic++

        var logarithmic = 0
        var k = n
        while (k > 1) { k /= 2; logarithmic++ }

        println("n=$n  log=$logarithmic  linear=$linear  quadratic=$quadratic")
    }
}

Outputcompiled & run with real Kotlin

n=10  log=3  linear=10  quadratic=100
n=100  log=6  linear=100  quadratic=10000
n=1000  log=9  linear=1000  quadratic=1000000

A JVM does very roughly 10⁸ simple operations per second. Read the constraints in a problem statement to work out which row you are in before choosing an approach.
Input size n	Fastest acceptable	Typical Kotlin shape
up to ~20	O(2ⁿ), O(n!)	backtracking over subsets / permutations
up to ~5,000	O(n²)	two nested `for` loops
up to ~1,000,000	O(n log n)	`sortedBy` then one pass; `PriorityQueue`
up to ~100,000,000	O(n)	one pass with a `HashMap` or two pointers
anything	O(log n) / O(1)	binary search, math, a lookup

Hidden costs in Kotlin one-liners

x in list is O(n), not O(1) — convert to a Set first if you check membership in a loop. list.sorted() inside a loop is O(n log n) every iteration. Each filter/map on a List allocates a whole new list; chaining five is still O(n) but five times the memory.

Pattern 1: two pointers

Put one index at each end of a sorted array (or a string) and move them toward each other based on what you see. Each step throws away one candidate, so the whole scan is O(n) instead of checking every pair in O(n²).

kotlinMain.kt

fun pairWithSum(sorted: IntArray, target: Int): Pair<Int, Int>? {
    var left = 0
    var right = sorted.lastIndex
    while (left < right) {
        val sum = sorted[left] + sorted[right]
        when {
            sum == target -> return sorted[left] to sorted[right]
            sum < target -> left++     // need bigger: move the small end up
            else -> right--            // need smaller: move the big end down
        }
    }
    return null
}

fun isPalindrome(s: String): Boolean {
    val clean = s.filter { it.isLetterOrDigit() }.lowercase()
    var i = 0
    var j = clean.lastIndex
    while (i < j) {
        if (clean[i] != clean[j]) return false
        i++
        j--
    }
    return true
}

fun main() {
    val nums = intArrayOf(1, 3, 4, 6, 8, 11)
    println(pairWithSum(nums, 10))
    println(pairWithSum(nums, 2))
    println(isPalindrome("A man, a plan, a canal: Panama"))
    println(isPalindrome("Kotlin"))
}

Outputcompiled & run with real Kotlin

(4, 6)
null
true
false

VisualizepairWithSum([1, 3, 4, 6, 8, 11], 10)Step 1 / 6

1var left = 0
2var right = sorted.lastIndex
3while (left < right) {
4    val sum = sorted[left] + sorted[right]
5    when {
6        sum == target -> return sorted[left] to sorted[right]
7        sum < target -> left++
8        else -> right--
9    }
10}

Line 2

Pointers at both ends.

Variables now

`left`	`0 (1)`
`right`	`5 (11)`

All 6 steps as a table

Step	Line	What happened	Variables now
1	2	Pointers at both ends.	`left = 0 (1)` `right = 5 (11)`
2	8	1 + 11 = 12 is too big — 11 cannot pair with anything larger than 1, drop it.	`sum = 12` `right = 4 (8)`
3	7	1 + 8 = 9 is too small — drop 1.	`sum = 9` `left = 1 (3)`
4	8	3 + 8 = 11 is too big — drop 8.	`sum = 11` `right = 3 (6)`
5	7	3 + 6 = 9 is too small — drop 3.	`sum = 9` `left = 2 (4)`
6	6	4 + 6 = 10 — found it in five steps.	`sum = 10`

Pattern 2: sliding window

For "best contiguous run" problems, keep a window [start, i] and update its summary as it slides instead of recomputing it. A fixed-size window adds the new element and subtracts the one that fell off. A variable-size window grows on the right and shrinks from the left whenever a rule is broken.

kotlinMain.kt

fun maxWindowSum(nums: IntArray, k: Int): Int {
    var window = nums.take(k).sum()
    var best = window
    for (i in k until nums.size) {
        window += nums[i] - nums[i - k]   // add the new, drop the oldest
        best = maxOf(best, window)
    }
    return best
}

fun longestUniqueRun(s: String): Int {
    val lastSeen = HashMap<Char, Int>()
    var start = 0
    var best = 0
    for ((i, c) in s.withIndex()) {
        val prev = lastSeen[c]
        if (prev != null && prev >= start) start = prev + 1   // shrink past the repeat
        lastSeen[c] = i
        best = maxOf(best, i - start + 1)
    }
    return best
}

fun main() {
    println(maxWindowSum(intArrayOf(2, 1, 5, 1, 3, 2), 3))
    println(longestUniqueRun("abcabcbb"))
    println(longestUniqueRun("pwwkew"))
    println(longestUniqueRun(""))
}

Outputcompiled & run with real Kotlin

Your turn

Write minWindowAtLeast(nums, target): the length of the shortest contiguous run whose sum is at least target (all numbers positive), or 0 if none. Grow the right edge, and shrink from the left while the sum still qualifies.

Pattern 3: hash map lookups

Whenever a brute force asks "have I seen the value I need before?" with an inner loop, a hash map answers it in O(1). Two Sum is the canonical example: instead of checking every pair, store each number's index and look up its complement.

kotlinMain.kt

fun twoSum(nums: IntArray, target: Int): Pair<Int, Int>? {
    val indexOf = HashMap<Int, Int>()
    for ((i, n) in nums.withIndex()) {
        val j = indexOf[target - n]
        if (j != null) return j to i
        indexOf[n] = i
    }
    return null
}

fun firstUnique(s: String): Char? {
    val counts = s.groupingBy { it }.eachCount()
    return s.firstOrNull { counts[it] == 1 }
}

fun main() {
    println(twoSum(intArrayOf(2, 7, 11, 15), 9))
    println(twoSum(intArrayOf(3, 2, 4), 6))
    println(twoSum(intArrayOf(1, 2), 7))
    println(firstUnique("swiss"))
    println(firstUnique("aabb"))
}

Outputcompiled & run with real Kotlin

(0, 1)
(1, 2)
null
w
null

Looking up before inserting matters: for [3, 2, 4] and target 6, inserting first would pair the 3 with itself.

Pattern 4: stacks

Reach for a stack when the most recent unresolved item is the one that matters: matching brackets, evaluating expressions, undo, and "next greater element" problems. A monotonic stack keeps indices whose answer is still unknown; each new element resolves every smaller one on top.

kotlinMain.kt

fun daysUntilWarmer(temps: IntArray): IntArray {
    val answer = IntArray(temps.size)
    val waiting = ArrayDeque<Int>()               // indices still waiting for a warmer day
    for (i in temps.indices) {
        while (waiting.isNotEmpty() && temps[i] > temps[waiting.last()]) {
            val j = waiting.removeLast()
            answer[j] = i - j
        }
        waiting.addLast(i)
    }
    return answer
}

fun evalRpn(tokens: List<String>): Int {
    val stack = ArrayDeque<Int>()
    for (t in tokens) {
        if (t in setOf("+", "-", "*", "/")) {
            val b = stack.removeLast()
            val a = stack.removeLast()
            stack.addLast(when (t) { "+" -> a + b; "-" -> a - b; "*" -> a * b; else -> a / b })
        } else {
            stack.addLast(t.toInt())
        }
    }
    return stack.single()
}

fun main() {
    println(daysUntilWarmer(intArrayOf(73, 74, 75, 71, 69, 72, 76, 73)).toList())
    println(evalRpn("2 1 + 3 *".split(" ")))
    println(evalRpn("4 13 5 / +".split(" ")))
}

Outputcompiled & run with real Kotlin

[1, 1, 4, 2, 1, 1, 0, 0]
9
6

Every index is pushed once and popped at most once, so daysUntilWarmer is O(n) even though it has a loop inside a loop.

Pattern 5: recursion and backtracking

Backtracking builds a candidate one choice at a time, recurses, then undoes the choice and tries the next. It explores every subset, permutation or path — exponential by nature, so it fits small inputs (see the table in the Big-O lesson). The shape is always: record or check the current state, loop over choices, choose, recurse, un-choose.

kotlinMain.kt

fun subsets(items: List<Int>): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    val current = mutableListOf<Int>()
    fun build(start: Int) {
        result.add(current.toList())            // snapshot, not the live list
        for (i in start until items.size) {
            current.add(items[i])               // choose
            build(i + 1)                        // explore
            current.removeAt(current.lastIndex) // un-choose
        }
    }
    build(0)
    return result
}

fun permutations(s: String): List<String> =
    if (s.length <= 1) listOf(s)
    else s.indices.flatMap { i -> permutations(s.removeRange(i, i + 1)).map { s[i] + it } }

fun main() {
    println(subsets(listOf(1, 2, 3)))
    println(permutations("abc"))
}

Outputcompiled & run with real Kotlin

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

Forgetting toList() is the classic bug: every entry in result would be the same list object, emptied by the time you print it.

Pattern 6: sort first

Many problems become a single pass once the data is sorted: overlapping intervals end up next to each other, duplicates sit side by side, anagrams share a sorted form. Paying O(n log n) for sortedBy is often the whole trick.

kotlinMain.kt

fun merge(intervals: List<IntRange>): List<IntRange> {
    val out = mutableListOf<IntRange>()
    for (r in intervals.sortedBy { it.first }) {
        val last = out.lastOrNull()
        if (last != null && r.first <= last.last) {
            out[out.lastIndex] = last.first..maxOf(last.last, r.last)   // overlap: extend
        } else {
            out.add(r)
        }
    }
    return out
}

fun isAnagram(a: String, b: String) = a.toCharArray().sorted() == b.toCharArray().sorted()

fun main() {
    println(merge(listOf(8..10, 1..3, 2..6, 15..18, 17..20)))
    println(isAnagram("listen", "silent"))
    println(isAnagram("rat", "car"))
}

Outputcompiled & run with real Kotlin

[1..6, 8..10, 15..20]
true
false

Your turn

Given meeting times as IntRanges, return the minimum number of rooms needed. Hint: sort by start and keep a PriorityQueue of end times.

Pattern 7: BFS and DFS on grids

A grid is a graph in disguise: each cell is a node, and its up/down/left/right neighbours are the edges. Use BFS with an ArrayDeque for "fewest steps", because it explores in rings of equal distance. Use DFS (recursion is fine for small grids) for "how many connected regions".

kotlinMain.kt

val moves = listOf(1 to 0, -1 to 0, 0 to 1, 0 to -1)

fun shortestSteps(grid: List<String>): Int {
    val rows = grid.size
    val cols = grid[0].length
    val dist = Array(rows) { IntArray(cols) { -1 } }
    dist[0][0] = 0                               // S is top-left
    val queue = ArrayDeque(listOf(0 to 0))
    while (queue.isNotEmpty()) {
        val (r, c) = queue.removeFirst()
        if (grid[r][c] == 'E') return dist[r][c]
        for ((dr, dc) in moves) {
            val nr = r + dr
            val nc = c + dc
            if (nr in 0 until rows && nc in 0 until cols && grid[nr][nc] != '#' && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1
                queue.addLast(nr to nc)
            }
        }
    }
    return -1
}

fun countIslands(grid: List<String>): Int {
    val seen = Array(grid.size) { BooleanArray(grid[0].length) }
    fun sink(r: Int, c: Int) {
        if (r !in grid.indices || c !in grid[0].indices) return
        if (grid[r][c] != '1' || seen[r][c]) return
        seen[r][c] = true
        for ((dr, dc) in moves) sink(r + dr, c + dc)
    }
    var count = 0
    for (r in grid.indices) for (c in grid[0].indices) {
        if (grid[r][c] == '1' && !seen[r][c]) { count++; sink(r, c) }
    }
    return count
}

fun main() {
    println(shortestSteps(listOf("S..#", ".#..", "...#", "#.E.")))
    println(shortestSteps(listOf("S#", "#E")))
    println(countIslands(listOf("11000", "11000", "00100", "00011")))
}

Outputcompiled & run with real Kotlin

5
-1
3

Mark when you enqueue, not when you dequeue

Setting dist[nr][nc] the moment a cell is added to the queue stops the same cell being queued several times by different neighbours. Marking on dequeue still gives the right answer but can make the queue many times larger.

Pattern 8: DP-lite

When the question is "how many ways" or "the best total", and the answer for step i depends only on the last one or two answers, you do not need a table — two variables rolling forward are enough. Write the recurrence in words first: "ways to reach step i = ways to reach i-1 + ways to reach i-2".

kotlinMain.kt

// ways to climb n stairs taking 1 or 2 steps at a time
fun climbStairs(n: Int): Long {
    var oneBack = 1L   // ways to reach step i - 1
    var twoBack = 1L   // ways to reach step i - 2
    repeat(n - 1) {
        val next = oneBack + twoBack
        twoBack = oneBack
        oneBack = next
    }
    return oneBack
}

// best total from houses where you may not take two neighbours
fun rob(houses: IntArray): Int {
    var skip = 0   // best so far if the previous house was NOT taken
    var take = 0   // best so far if the previous house WAS taken
    for (h in houses) {
        val newTake = skip + h
        skip = maxOf(skip, take)
        take = newTake
    }
    return maxOf(skip, take)
}

fun main() {
    println((1..5).map { climbStairs(it) })
    println(climbStairs(45))
    println(rob(intArrayOf(2, 7, 9, 3, 1)))
    println(rob(intArrayOf(1, 2, 3, 1)))
}

Outputcompiled & run with real Kotlin

[1, 2, 3, 5, 8]
1836311903
12
4

Your turn

Change climbStairs so each move can be 1, 2 or 3 steps. You will need a third rolling variable; n = 4 should give 7.

Brute force: The obvious, usually slow solution; your correctness baseline.
Edge case: An input at the boundary — empty, one element, all equal, maximum size — where bugs hide.
Two pointers: Two indices moving through a sorted array or string, each step ruling out candidates; O(n).
Sliding window: A contiguous range whose summary is updated incrementally as it moves.
Monotonic stack: A stack kept in increasing or decreasing order so each element resolves the ones it beats.
Backtracking: Choose, recurse, un-choose — exhaustive search over combinations.
Recurrence: A rule expressing an answer in terms of smaller answers; the heart of any DP.

Quick check

You must find the longest substring with no repeated characters in a 100,000-character string. Which approach fits?

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

Frequently asked questions

Should I practise coding problems in Kotlin or Java?

Kotlin, if that is the job you want. It is accepted by all major coding platforms and most interviewers, and idioms like groupingBy, withIndex, destructuring and ArrayDeque make solutions shorter and easier to explain. Know the JDK types it relies on (PriorityQueue, TreeMap) because they are the same in both languages.

How many patterns do I need to know for interviews?

The eight in this module cover most junior and mid-level coding rounds. Add binary search on the answer, union-find, topological sort and interval scheduling as you move toward senior or big-tech interviews.

What if I cannot see the optimal solution in an interview?

Say the brute force and its Big-O, code it cleanly, and test it. A correct O(n²) solution explained well scores better than an unfinished O(n) one. Then look for repeated work — that is usually where a hash map, sort or window fits.

Finish the Kotlin 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.