Data Structures and Algorithms, Part 8: Programming Patterns for Solving Problems

Run it: four classic two-pointer jobs

The first line prints the first pair the pointers meet. Try changing the target and predict which pair comes out.

fun pairSumSorted(a: IntArray, target: Int): Pair<Int, Int>? {
    var l = 0
    var r = a.size - 1
    while (l < r) {
        val sum = a[l] + a[r]
        if (sum == target) return l to r
        if (sum < target) l++ else r--
    }
    return null
}

fun reverseInPlace(a: IntArray) {
    var l = 0
    var r = a.size - 1
    while (l < r) {
        val t = a[l]; a[l] = a[r]; a[r] = t
        l++; r--
    }
}

// Returns the new length; the first that-many items are the unique values.
fun removeDuplicates(a: IntArray): Int {
    if (a.isEmpty()) return 0
    var w = 1                       // next slot to write
    for (r in 1 until a.size) {
        if (a[r] != a[w - 1]) { a[w] = a[r]; w++ }
    }
    return w
}

fun maxWater(h: IntArray): Int {
    var l = 0
    var r = h.size - 1
    var best = 0
    while (l < r) {
        best = maxOf(best, minOf(h[l], h[r]) * (r - l))
        if (h[l] < h[r]) l++ else r--      // move the shorter wall
    }
    return best
}

fun main() {
    println(pairSumSorted(intArrayOf(1, 2, 4, 7, 8, 11), 9))     // (0, 4): 1 + 8
    println(pairSumSorted(intArrayOf(1, 2, 3), 100))             // null

    val a = intArrayOf(1, 2, 3, 4, 5)
    reverseInPlace(a)
    println(a.toList())

    val b = intArrayOf(1, 1, 2, 2, 2, 3)
    val k = removeDuplicates(b)
    println("unique count $k -> ${b.copyOf(k).toList()}")

    println(maxWater(intArrayOf(1, 8, 6, 2, 5, 4, 8, 3, 7)))    // 49
}

Run it: middle, cycle and happy number

Run it and check the cycle detector before and after the loop is closed.

class Node(val value: Int, var next: Node? = null)

fun build(vararg values: Int): Node? {
    var head: Node? = null
    for (v in values.reversed()) head = Node(v, head)
    return head
}

fun middle(head: Node?): Node? {
    var slow = head
    var fast = head
    while (fast != null && fast.next != null) {
        slow = slow!!.next
        fast = fast.next!!.next
    }
    return slow
}

fun hasCycle(head: Node?): Boolean {
    var slow = head
    var fast = head
    while (fast != null && fast.next != null) {
        slow = slow!!.next
        fast = fast.next!!.next
        if (slow === fast) return true      // === means "the very same node"
    }
    return false
}

fun digitSquares(n: Int): Int {
    var x = n
    var sum = 0
    while (x > 0) { val d = x % 10; sum += d * d; x /= 10 }
    return sum
}

fun isHappy(n: Int): Boolean {
    var slow = n
    var fast = digitSquares(n)
    while (fast != 1 && slow != fast) {
        slow = digitSquares(slow)
        fast = digitSquares(digitSquares(fast))
    }
    return fast == 1
}

fun main() {
    println("middle of 1..5 = ${middle(build(1, 2, 3, 4, 5))?.value}")
    println("middle of 1..4 = ${middle(build(1, 2, 3, 4))?.value}   (second middle)")

    val a = Node(1); val b = Node(2); val c = Node(3); val d = Node(4)
    a.next = b; b.next = c; c.next = d
    println("cycle before: ${hasCycle(a)}")
    d.next = b                                  // close a loop back to node 2
    println("cycle after:  ${hasCycle(a)}")

    println("happy numbers up to 30: ${(1..30).filter { isHappy(it) }}")
}

Run it: fixed and variable windows

Three windows in one file. Add a println inside the loops to watch left and right move.

// Fixed: largest sum of any k consecutive numbers.
fun maxSumOfK(a: IntArray, k: Int): Int? {
    if (k <= 0 || a.size < k) return null
    var window = 0
    for (i in 0 until k) window += a[i]
    var best = window
    for (i in k until a.size) {
        window += a[i] - a[i - k]          // add the new, drop the old
        best = maxOf(best, window)
    }
    return best
}

// Variable: longest substring with no repeated letter.
fun longestUnique(s: String): Int {
    val lastSeen = HashMap<Char, Int>()
    var left = 0
    var best = 0
    for ((right, c) in s.withIndex()) {
        val prev = lastSeen[c]
        if (prev != null && prev >= left) left = prev + 1   // jump past the repeat
        lastSeen[c] = right
        best = maxOf(best, right - left + 1)
    }
    return best
}

// Variable: shortest subarray whose sum is at least target (all numbers positive).
fun smallestSubarray(target: Int, a: IntArray): Int {
    var left = 0
    var sum = 0
    var best = Int.MAX_VALUE
    for (right in a.indices) {
        sum += a[right]
        while (sum >= target) {                // valid: record, then shrink
            best = minOf(best, right - left + 1)
            sum -= a[left]
            left++
        }
    }
    return if (best == Int.MAX_VALUE) 0 else best
}

fun main() {
    println(maxSumOfK(intArrayOf(2, 1, 5, 1, 3, 2), 3))   // 9
    println(maxSumOfK(intArrayOf(1, 2), 5))               // null
    println(longestUnique("abcabcbb"))                    // 3
    println(longestUnique("pwwkew"))                      // 3
    println(smallestSubarray(7, intArrayOf(2, 3, 1, 2, 4, 3)))   // 2  (4 + 3)
    println(smallestSubarray(100, intArrayOf(1, 2, 3)))          // 0  (none)
}

Run it: range queries and subarray sum equals k

The map version also works with negative numbers, which a sliding window cannot handle.

class RangeSum(a: IntArray) {
    private val prefix = IntArray(a.size + 1)
    init { for (i in a.indices) prefix[i + 1] = prefix[i] + a[i] }

    // sum of a[from..to], both included
    fun sum(from: Int, to: Int): Int = prefix[to + 1] - prefix[from]
}

fun countSubarraysWithSum(a: IntArray, k: Int): Int {
    val seen = HashMap<Int, Int>()      // running total -> how many times
    seen[0] = 1
    var running = 0
    var count = 0
    for (x in a) {
        running += x
        count += seen[running - k] ?: 0
        seen[running] = (seen[running] ?: 0) + 1
    }
    return count
}

fun main() {
    val rs = RangeSum(intArrayOf(3, 1, 4, 1, 5))
    println(rs.sum(1, 3))      // 6
    println(rs.sum(0, 4))      // 14
    println(rs.sum(2, 2))      // 4

    println(countSubarraysWithSum(intArrayOf(1, 1, 1), 2))        // 2
    println(countSubarraysWithSum(intArrayOf(1, -1, 0), 0))       // 3, negatives are fine
    println(countSubarraysWithSum(intArrayOf(), 5))               // 0
}

Run it: rectangle sums on a grid

class GridSum(g: Array<IntArray>) {
    private val rows = g.size
    private val cols = if (rows == 0) 0 else g[0].size
    private val p = Array(rows + 1) { IntArray(cols + 1) }

    init {
        for (r in 0 until rows) for (c in 0 until cols) {
            p[r + 1][c + 1] = g[r][c] + p[r][c + 1] + p[r + 1][c] - p[r][c]
        }
    }

    fun rect(r1: Int, c1: Int, r2: Int, c2: Int): Int =
        p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1]
}

fun main() {
    val grid = arrayOf(
        intArrayOf(1, 2, 3),
        intArrayOf(4, 5, 6),
        intArrayOf(7, 8, 9),
    )
    val gs = GridSum(grid)
    println(gs.rect(0, 0, 2, 2))   // 45, the whole grid
    println(gs.rect(1, 1, 2, 2))   // 5 + 6 + 8 + 9 = 28
    println(gs.rect(0, 1, 1, 1))   // 2 + 5 = 7
}

Run it: longest consecutive run with a set

The inner while looks scary, but it only runs from the start of a run, never from the middle.

fun longestConsecutive(a: IntArray): Int {
    val set = a.toHashSet()
    var best = 0
    for (x in set) {
        if (x - 1 !in set) {                // x starts a run
            var y = x
            while (y + 1 in set) y++
            best = maxOf(best, y - x + 1)
        }
    }
    return best
}

fun main() {
    println(longestConsecutive(intArrayOf(100, 4, 200, 1, 3, 2)))    // 4
    println(longestConsecutive(intArrayOf(5, 5, 5)))                 // 1
    println(longestConsecutive(intArrayOf()))                        // 0
}

Run it: smallest speed and smallest capacity

Notice that the search code is almost identical in both. Only the yes/no check changes.

// Koko: smallest eating speed k so all piles finish within h hours.
fun hoursNeeded(piles: IntArray, k: Int): Long {
    var hours = 0L
    for (p in piles) hours += (p + k - 1) / k      // round up
    return hours
}

fun minEatingSpeed(piles: IntArray, h: Int): Int {
    if (piles.isEmpty()) return 0
    var lo = 1
    var hi = piles.max()                  // eating the biggest pile in an hour always works
    while (lo < hi) {
        val mid = lo + (hi - lo) / 2
        if (hoursNeeded(piles, mid) <= h) hi = mid else lo = mid + 1
    }
    return lo
}

// Ship packages in order within the given number of days.
fun daysNeeded(weights: IntArray, capacity: Int): Int {
    var days = 1
    var load = 0
    for (w in weights) {
        if (load + w > capacity) { days++; load = 0 }
        load += w
    }
    return days
}

fun minCapacity(weights: IntArray, days: Int): Int {
    if (weights.isEmpty()) return 0
    var lo = weights.max()                // must at least carry the heaviest package
    var hi = weights.sum()                // one day carries everything
    while (lo < hi) {
        val mid = lo + (hi - lo) / 2
        if (daysNeeded(weights, mid) <= days) hi = mid else lo = mid + 1
    }
    return lo
}

fun main() {
    println(minEatingSpeed(intArrayOf(3, 6, 7, 11), 8))                  // 4
    println(minCapacity(intArrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), 5))   // 15
    println(minCapacity(intArrayOf(3, 2, 2, 4, 1, 4), 3))                // 6
}

Run it: next greater, warmer days and the largest rectangle

The stack holds indexes, not values, so we can both read the value and compute distances.

fun nextGreater(a: IntArray): IntArray {
    val result = IntArray(a.size) { -1 }          // -1 means "none"
    val stack = ArrayDeque<Int>()                 // indexes, values decreasing
    for (i in a.indices) {
        while (stack.isNotEmpty() && a[stack.last()] < a[i]) {
            result[stack.removeLast()] = a[i]
        }
        stack.addLast(i)
    }
    return result
}

fun dailyTemperatures(t: IntArray): IntArray {
    val wait = IntArray(t.size)                   // 0 means "never warmer"
    val stack = ArrayDeque<Int>()
    for (i in t.indices) {
        while (stack.isNotEmpty() && t[stack.last()] < t[i]) {
            val j = stack.removeLast()
            wait[j] = i - j
        }
        stack.addLast(i)
    }
    return wait
}

fun largestRectangle(h: IntArray): Int {
    val stack = ArrayDeque<Int>()                 // indexes, heights increasing
    var best = 0
    for (i in 0..h.size) {
        val cur = if (i == h.size) 0 else h[i]    // a final height 0 pops everything
        while (stack.isNotEmpty() && h[stack.last()] >= cur) {
            val height = h[stack.removeLast()]
            val left = if (stack.isEmpty()) -1 else stack.last()
            best = maxOf(best, height * (i - left - 1))
        }
        stack.addLast(i)
    }
    return best
}

fun main() {
    println(nextGreater(intArrayOf(2, 1, 5, 3, 6, 4)).toList())                      // [5, 5, 6, 6, -1, -1]
    println(dailyTemperatures(intArrayOf(73, 74, 75, 71, 69, 72, 76, 73)).toList())  // [1, 1, 4, 2, 1, 1, 0, 0]
    println(largestRectangle(intArrayOf(2, 1, 5, 6, 2, 3)))                          // 10
}

Run it: merge, insert and count rooms

Touching intervals such as (1, 4) and (4, 5) are treated as overlapping when merging, but as sharing a room when counting. Decide which you need and test it.

fun mergeIntervals(iv: List<Pair<Int, Int>>): List<Pair<Int, Int>> {
    if (iv.isEmpty()) return emptyList()
    val sorted = iv.sortedBy { it.first }
    val out = mutableListOf(sorted[0])
    for (i in 1 until sorted.size) {
        val last = out.last()
        val cur = sorted[i]
        if (cur.first <= last.second) {
            out[out.size - 1] = last.first to maxOf(last.second, cur.second)   // overlap: extend
        } else {
            out.add(cur)                                                        // gap: new interval
        }
    }
    return out
}

// iv is sorted and non-overlapping already.
fun insertInterval(iv: List<Pair<Int, Int>>, add: Pair<Int, Int>): List<Pair<Int, Int>> {
    val out = mutableListOf<Pair<Int, Int>>()
    var cur = add
    var i = 0
    while (i < iv.size && iv[i].second < cur.first) { out.add(iv[i]); i++ }      // entirely before
    while (i < iv.size && iv[i].first <= cur.second) {                            // overlapping
        cur = minOf(cur.first, iv[i].first) to maxOf(cur.second, iv[i].second)
        i++
    }
    out.add(cur)
    while (i < iv.size) { out.add(iv[i]); i++ }                                   // entirely after
    return out
}

fun minMeetingRooms(iv: List<Pair<Int, Int>>): Int {
    val starts = iv.map { it.first }.sorted()
    val ends = iv.map { it.second }.sorted()
    var i = 0
    var j = 0
    var busy = 0
    var most = 0
    while (i < starts.size) {
        if (starts[i] < ends[j]) { busy++; i++; most = maxOf(most, busy) }   // someone arrives
        else { busy--; j++ }                                                 // someone leaves
    }
    return most
}

fun main() {
    println(mergeIntervals(listOf(1 to 3, 2 to 6, 8 to 10, 15 to 18)))   // [(1, 6), (8, 10), (15, 18)]
    println(insertInterval(listOf(1 to 3, 6 to 9), 2 to 5))              // [(1, 5), (6, 9)]
    println(minMeetingRooms(listOf(0 to 30, 5 to 10, 15 to 20)))         // 2
    println(minMeetingRooms(listOf(1 to 2, 2 to 3)))                     // 1, touching ends reuse the room
}

Run it: k largest and k most frequent

In Kotlin you can also write a.sortedDescending().take(k). It is shorter, and fine for small data. The heap version is what scales.

import java.util.PriorityQueue

fun kLargest(a: IntArray, k: Int): List<Int> {
    val heap = PriorityQueue<Int>()          // min-heap
    for (x in a) {
        heap.add(x)
        if (heap.size > k) heap.poll()       // drop the smallest
    }
    return heap.sortedDescending()
}

fun kMostFrequent(words: List<String>, k: Int): List<String> {
    val counts = HashMap<String, Int>()
    for (w in words) counts[w] = (counts[w] ?: 0) + 1

    val heap = PriorityQueue<Pair<String, Int>>(compareBy { it.second })
    for ((word, n) in counts) {
        heap.add(word to n)
        if (heap.size > k) heap.poll()       // drop the least frequent
    }
    return heap.sortedByDescending { it.second }.map { it.first }
}

fun main() {
    println(kLargest(intArrayOf(5, 1, 9, 3, 7, 8), 3))     // [9, 8, 7]
    println(kLargest(intArrayOf(4, 4), 5))                 // [4, 4], fewer than k items is fine
    val words = listOf("a", "b", "a", "c", "a", "b", "d")
    println(kMostFrequent(words, 2))                       // [a, b]
}

Run it: sort colors and find the missing number

Both functions change the array they are given. That is what “in place” means.

fun swap(a: IntArray, i: Int, j: Int) { val t = a[i]; a[i] = a[j]; a[j] = t }

fun sortColors(a: IntArray) {
    var lo = 0
    var mid = 0
    var hi = a.size - 1
    while (mid <= hi) {
        when (a[mid]) {
            0 -> { swap(a, lo, mid); lo++; mid++ }
            1 -> mid++
            else -> { swap(a, mid, hi); hi-- }
        }
    }
}

// a holds the numbers 0..n with exactly one missing (n = a.size).
fun missingNumber(a: IntArray): Int {
    val n = a.size
    var i = 0
    while (i < n) {
        val v = a[i]
        if (v < n && a[v] != v) swap(a, i, v) else i++    // send v to its home, index v
    }
    for (j in 0 until n) if (a[j] != j) return j
    return n
}

fun main() {
    val colors = intArrayOf(2, 0, 2, 1, 1, 0)
    sortColors(colors)
    println(colors.toList())                                  // [0, 0, 1, 1, 2, 2]

    println(missingNumber(intArrayOf(3, 0, 1)))               // 2
    println(missingNumber(intArrayOf(9, 6, 4, 2, 3, 5, 7, 0, 1)))   // 8
    println(missingNumber(intArrayOf(0, 1)))                  // 2
}

Run it: single number, power of two, count bits

The last loop enumerates all 8 subsets of 3 items by counting from 0 to 7. Each bit says “in” or “out” for one item.

fun singleNumber(a: IntArray): Int {
    var x = 0
    for (v in a) x = x xor v
    return x
}

fun isPowerOfTwo(n: Int): Boolean = n > 0 && (n and (n - 1)) == 0

fun countBits(n: Int): Int {
    var x = n
    var count = 0
    while (x != 0) {
        x = x and (x - 1)        // remove the lowest 1-bit
        count++
    }
    return count
}

fun main() {
    println(singleNumber(intArrayOf(4, 1, 2, 1, 2)))     // 4
    println(listOf(0, 1, 2, 3, 16, 18, -8).map { isPowerOfTwo(it) })
    println(listOf(0, 7, 1024, 255).map { countBits(it) })   // [0, 3, 1, 8]

    // Bitmask: list every subset of three items.
    val items = listOf("x", "y", "z")
    for (mask in 0 until (1 shl items.size)) {
        val subset = items.filterIndexed { i, _ -> (mask shr i) and 1 == 1 }
        println("mask ${Integer.toBinaryString(mask).padStart(3, '0')} -> $subset")
    }
}