Solving Array and String Problems with Hash-Based Lookups

Welcome back. In the last lesson, we designed Kotlin APIs that preserve useful type information. Now we’ll use a collection for a different purpose: remembering what an array scan has already seen.

This lesson focuses on a common coding-interview task, Two Sum. You’ll move from a straightforward solution to a hash-based one, implement it in Kotlin, explain why it returns two distinct indices, and state its time and space costs. Allow about 40 minutes, including a short video, reading, and time to run the code.

Turn a pair search into a lookup

Here is the interview contract: given an unsorted IntArray and a target, return the indices of two different elements whose values sum to the target. Assume exactly one valid pair exists. For example, nums = [2, 1, 5, 3] with target = 4 should return indices [1, 3], because the values at those positions are 1 and 3.

The direct approach tries each element with every later element. It needs no substantial extra storage, but for an array of $n$ elements it may inspect a quadratic number of pairs: $O(n^2)$ time.

We can ask a narrower question. When the current value is 3 and the target is 4, the only value worth looking for is 1. In general, the needed complement is the target minus the current value. If we can look up that complement without scanning the array again, we can avoid the inner loop.

Watch NeetCode’s “Two Sum - Leetcode 1 - HashMap - Python” for the visual reasoning. The implementation near the end of the video is in Python; we’ll write Kotlin below. Notice that the worked example switches targets during the explanation, so follow the complement calculation for the target currently on screen.

A HashSet<Int> could tell us whether a complement exists. But this contract asks for indices, not just whether a pair exists. We therefore need a HashMap<Int, Int> that associates a previously seen value with an index where it appeared. This is the choice of collection dictated by the output requirement.

Implement the one-pass scan in Kotlin

Before processing index i, let the map contain only values from indices earlier than i. Look up the current value’s complement in that map. If it is present, its stored index and i form the answer. Otherwise, store the current value and continue.

fun twoSum(nums: IntArray, target: Int): IntArray {
    val seenIndexByValue = HashMap<Int, Int>()

    for (index in nums.indices) {
        val value = nums[index]
        val complement = target - value
        val previousIndex = seenIndexByValue[complement]

        if (previousIndex != null) {
            return intArrayOf(previousIndex, index)
        }

        seenIndexByValue[value] = index
    }

    error("Expected a pair whose sum is the target")
}

The final error makes the stated contract explicit: reaching it means the promised pair was absent. If an application needed to handle “no pair” as an ordinary result, we would choose a different return contract rather than silently return an empty array.

Trace the example with target 4. At index 0, value 2 needs another 2; the map is empty, so we store 2 at index 0. At index 1, value 1 needs 3; it is absent, so we store 1 at index 1. Value 5 finds no complement either. Finally, value 3 needs 1, which is already mapped to index 1, so the function returns [1, 3].

The order of lookup and insertion is essential. If we inserted the current value first, a single 3 could appear to pair with itself for target 6. Looking only among previous indices makes using the same element twice impossible. It still permits equal values at different indices: [3, 3] with target 6 returns [0, 1].

For a brief hands-on pass, run the function with these calls and compare the printed indices with the array positions:

fun main() {
    println(twoSum(intArrayOf(2, 1, 5, 3), 4).contentToString()) // [1, 3]
    println(twoSum(intArrayOf(3, 3), 6).contentToString())       // [0, 1]
    println(twoSum(intArrayOf(0, 4), 4).contentToString())       // [0, 1]
}

The last case checks a small but important Kotlin detail. A stored index of 0 is a valid, non-null map result; previousIndex != null does not mistake it for “not found.”

Explain correctness, not just the code

The useful invariant is: before each lookup at index i, every entry in seenIndexByValue refers to an index less than i. The map may retain only the most recent index for a repeated value, which is enough—any earlier occurrence of the needed value forms a valid pair with the current element.

Suppose the promised pair occurs at indices p and q, with p < q. By the time the scan reaches q, the value at p has been seen. Unless the function has already returned a valid pair, that value—or a later occurrence of the same value at an index still less than q—is in the map. The lookup at q therefore finds a valid earlier index. This argument explains both why one pass suffices and why overwriting an index for a duplicate does not lose the ability to find an answer.

State assumptions when presenting the solution. The code above assumes computing target - value fits in an Int. If interview constraints permit overflow, compute complements in Long and use Long map keys. That changes neither the lookup idea nor its asymptotic costs.

State the costs precisely

LeetCode’s Two Sum editorial is useful here because it places the brute-force baseline beside hash-table approaches. Read the indicated parts rather than treating “one pass” as a complete complexity argument.

Our loop examines at most $n$ elements. With expected constant-time hash-map lookup and insertion, its expected time is $O(n)$. The map holds at most $n$ value–index entries, so its additional space is $O(n)$, excluding the input and the fixed-size returned pair. The nested-loop alternative uses $O(n^2)$ time and $O(1)$ additional space.

“Expected” matters. Hash keys can collide, making a lookup slower than constant time. The image below shows separate chaining, one conceptual way a hash table handles collisions; it is not a diagram of this Kotlin function or a promise about a particular HashMap implementation.

In an interview, a concise statement is: “I use a map from previously seen values to their indices. Each current value checks its complement before insertion, so the indices are distinct. The algorithm takes $O(n)$ expected time and $O(n)$ extra space; hash lookup is not an unconditional worst-case constant-time guarantee.” That communicates the design decision as well as the headline complexity.

Key takeaways

A hash lookup helps when each array element prompts a question about something already encountered. For Two Sum, the question is whether the complement appeared earlier; a map stores its index because the answer requires positions. The lookup-before-insert invariant protects against reusing one element, and the speed improvement trades $O(n)$ additional space for $O(n)$ expected time.

Next, we’ll tackle a different array-and-string pattern: sliding windows, where the important state describes a contiguous range rather than all previously seen values.