Start learning free

LESSON 239 OF 348 · HASH TABLE

Two Sum in Kotlin: O(n) with a HashMap

Practice O(n) Read the full explanation

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input will have at most one solution, and you may not use the same index twice.

In case no solution exists, return [-1, -1]

Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9

Note:

Your algorithm should run in O(n) time and use O(n) space.


Hints:

This the type of problem where we optimize the brute force approach to get the optimal one. The brute force approach took O(n^2) time because we had two nested for loops, one for i and another one j. In order to get O(n), we have to reduce this to only one for loop, so we should fix only one index, let it be j, the index of the second number. We will try out each possible j, and for each of them we should check if there is an index i < j such that nums[i] + nums[j] == target: 
for each j : 0 -> n - 1:
	// We know nums[j]. Find some index i < j such that nums[i] + nums[j] == target.
How can we find that index in O(1)?

nums[i] + nums[j] == target <=> nums[i] == target - nums[j]. So for each j, we should look for an element equal to target - nums[j] from the left of j. Is there a data structure that allows us to look for an element in a collection in constant time? How can we use it here?

That data structure is the Hash Map. We can have a Hash Map where we insert all the elements nums[j] we iterate on during the for loop. In this way, for each j, we can look in the Hash Map to see if there is some element of value target - nums[j] and if so, we found a solution: 
for each j : 0 -> n - 1:
	- Look for target - nums[j] in the Hash Map. If there exists, we found the solution.
	- Otherwise, insert nums[j] into the Hash Map and continue with the for loop.
I know the code above is not perfect. Hash Maps work with pairs (key => value), we cannot just insert a nums[j] into a Hash Map. What should we actually insert in this hash map? What are the keys and what are the values?

The problem with the code above is that we just check if there is an element equal to target - nums[j]. If so, we have a solution, but that's not enough. The problem asks us to return the indices of those elements and we only know of them: j. Can we adapt the solution such that if for some j there is an element equal to target - nums[j], we can also get its index?

The pairs in the Hash Map should be nums[j] => j so that for each element we insert, we can also get its index: 
for each j : 0 -> n - 1:
	if target - nums[j] in indexOfValue:
		return [indexOfValue[target - nums[j]], j]
	indexOfValue[nums[j]] = j
return [-1, -1]

STEP 1 OF 5
    Ctrl + Enter to check

    KOTLIN · HASH TABLE

    Two Sum in Kotlin, explained

    Problem overview

    The function twoSum receives an IntArray called nums and an Int called target. It returns the indices of two different positions whose values add up to target, or [-1, -1] if no such pair exists. There is at most one solution, and the same index can't be used twice, although equal values at different indices are fine.

    For nums = [2, 7, 11, 15] and target = 9, the values at indices 0 and 1 are 2 and 7, so the answer is [0, 1]. The statement asks for O(n) time and O(n) space.

    Approach: remember what you have seen

    Trying every pair of indices with two nested loops is O(n²). To get to O(n), only one loop is allowed, so each element must find its partner without a search.

    Fix the second element of the pair at index i. Its partner must equal target - nums[i] and must sit at an earlier index. If you've remembered every earlier value together with its index, finding the partner is one lookup. A hash map does that in constant time on average, with the value as the key and its index as the stored value, so the lookup returns the index that the answer needs.

    The loop therefore does two things for each i: first look for target - nums[i] among the earlier elements, and return if it's there; otherwise record nums[i] and move on. Checking before storing also guarantees that an element is never paired with itself.

    On nums = [3, 2, 4] and target = 6: at i = 0 the needed value is 3, the map is empty, so store 3 -> 0. At i = 1 the needed value is 4, still absent, so store 2 -> 1. At i = 2 the value 4 needs 2, which is in the map at index 1. The answer is [2, 1], with the current index first.

    Step by step

    1. Create the map. indexOfValue is a HashMap<Int, Int> declared with val. It maps each value seen so far to its index.
    2. Loop over the indices. for (i in nums.indices) treats each nums[i] as the possible second element of the pair.
    3. Look for the partner. If indexOfValue.containsKey(target - nums[i]), the partner appeared earlier. Return an IntArray with i first and the stored index second. The lookup indexOfValue[target - nums[i]] gives an Int?, so the code adds !!, which is safe because containsKey just confirmed the key is present.
    4. Store the current element. indexOfValue[nums[i]] = i adds the key, or overwrites it if the value was seen before. It happens after the check, so an element can't match itself.
    5. Return [-1, -1] when the loop ends without finding a pair.

    The solution in Kotlin

    class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val indexOfValue = HashMap<Int, Int>()
        for (i in nums.indices) {
            if (indexOfValue.containsKey(target - nums[i])) {
                return intArrayOf(i, indexOfValue[target - nums[i]]!!)
            }
            indexOfValue[nums[i]] = i
        }
        return intArrayOf(-1, -1)
    }
}

    Kotlin details worth knowing:

    • nums.indices is the range 0..nums.size - 1. For an empty array it is empty, so the loop body never runs.
    • Map lookups are nullable. indexOfValue[key] has type Int? because a missing key gives null. intArrayOf wants plain Ints, so the nullable value must be converted. !! says "I know this isn't null" and throws a NullPointerException if you're wrong. Here containsKey makes it safe. The alternative val j = indexOfValue[target - nums[i]] followed by if (j != null) does the lookup once instead of twice, and Kotlin then treats j as a plain Int inside the if.
    • map[key] = value is the shorthand for put. It adds a new key or replaces the value of an existing one.
    • intArrayOf(a, b) creates an IntArray with the given elements. The function's return type is IntArray, not List<Int>.
    • Overflow. target - nums[i] is an Int subtraction, and Int wraps silently at 32 bits. For example Int.MAX_VALUE - (-5) gives -2147483644. With inputs near the limits, the wrapped number could match a stored value by accident; use Long if the inputs can be that large.

    Complexity

    Time: O(n). The loop visits each element once, and each iteration does a constant number of hash-map operations, each O(1) on average.

    Space: O(n). In the worst case, when no pair matches, the map stores one entry per distinct value in the array.

    This trades memory for speed. Sorting plus two pointers needs no map but costs O(n log n) time, and the brute force needs no extra space but takes O(n²).

    Edge cases and common mistakes

    • Index order. The result is the current index first, then the earlier one. For [2, 7, 11, 15] and target 9, the code returns [1, 0], not [0, 1]. Both name the same two elements.
    • Using one element twice. For [3, 4] and target 6, the answer is [-1, -1]. Storing 3 before checking would pair it with itself.
    • Equal values. For [3, 3] and target 6 the answer is [1, 0]. The first 3 is stored at index 0, then the second 3 finds it.
    • Duplicates overwriting. If a value occurs twice, the map keeps the later index. That is fine here, since a pair is returned the moment it exists.
    • No pair. [1, 2, 3] with target 100 returns [-1, -1].
    • Empty array. It returns [-1, -1].
    • Forgetting !!. Passing the lookup straight to intArrayOf doesn't compile, because the value is an Int?.

    Testing

    • nums = [3, 2, 4], target = 6 gives [2, 1].
    • nums = [3, 3], target = 6 gives [1, 0].
    • nums = [3, 4], target = 6 gives [-1, -1].
    • nums = [1, 2, 3], target = 100 gives [-1, -1].
    • nums = [], target = 9 gives [-1, -1].
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free