Start learning free

LESSON 262 OF 414 · HASH TABLE

Two Sum in Scala: O(n) with a Mutable 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

    SCALA · HASH TABLE

    Two Sum in Scala, explained

    Problem overview

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

    For nums = Array(2, 7, 11, 15) and target = 9, the values at indices 0 and 1 are 2 and 7, and 2 + 7 = 9. The expected answer is indices 0 and 1.

    The lesson asks for O(n) time and O(n) extra space, which rules out checking every pair of indices.

    Approach: remember what you have already seen

    The brute-force solution uses two nested loops over the indices, which costs O(n²). To reach O(n) you need a single pass, so fix one index, call it i, and treat nums(i) as the second element of the pair. Its partner must equal target - nums(i), and if the pair exists, the partner sits to the left of i and has already been visited.

    So the loop only has to answer one question for each element: "Have I already seen the value target - nums(i), and at which index?" A hash map answers that in constant time on average. Its keys are the values seen so far, and each key maps to the index where that value appeared. If the partner is in the map, you have both indices. If not, you record the current element and move on.

    Take nums = Array(3, 9, -2, 5) with target = 3:

    • At index 0 the value is 3, and the partner would be 0. The map is empty, so store 3 mapped to 0.
    • At index 1 the value is 9, and the partner would be -6. It is not in the map, so store 9 mapped to 1.
    • At index 2 the value is -2, and the partner would be 5. Not there yet, so store -2 mapped to 2.
    • At index 3 the value is 5, and the partner is -2. The map holds -2 at index 2, so the answer is the array Array(3, 2).

    Step by step

    1. Create the map. indexOfValue is a scala.collection.mutable.HashMap[Int, Int] declared with val. The variable never points to another map; only the map's contents change.
    2. Loop over the indices with for (i <- nums.indices). Each nums(i) is a candidate second element of the pair.
    3. Check for the partner with indexOfValue.contains(target - nums(i)). If it is there, return Array(i, indexOfValue(target - nums(i))). Calling the map like a function with a key reads the stored index.
    4. Store the current element after the check, with indexOfValue(nums(i)) = i. Doing this after the check means an element is never paired with itself.
    5. Return Array(-1, -1) after the loop. The loop only ends without returning when no pair adds up to target.

    The solution in Scala

    class Solution {
    def twoSum(nums: Array[Int], target: Int): Array[Int] = {
        val indexOfValue = scala.collection.mutable.HashMap[Int, Int]()
        for (i <- nums.indices) {
            if (indexOfValue.contains(target - nums(i))) {
                return Array(i, indexOfValue(target - nums(i)))
            }
            indexOfValue(nums(i)) = i
        }
        return Array(-1, -1)
    }
}

    The Scala details worth a closer look:

    • Mutable versus immutable. The default Map in Scala is immutable, so it can't be updated in place. The lesson uses the class from scala.collection.mutable, spelled out with its full package name.
    • Apply and update. indexOfValue(key) calls the map's apply method and indexOfValue(key) = value calls update. That is why reading and writing look like array indexing. Parentheses are used for arrays too: nums(i), not nums[i].
    • Missing keys throw. indexOfValue(5) on a map without the key 5 throws a NoSuchElementException with the message "key not found: 5". The contains check is what makes the read safe. indexOfValue.get(5) would return None instead.
    • The order of the result. The array is Array(i, earlierIndex), so the current index comes first. For Array(2, 7, 11, 15) and target 9, the code returns Array(1, 0), the same two indices as [0, 1] in a different order.
    • return inside for. A for loop over a collection is turned into a call with a closure, so this return leaves the whole method from inside that closure. Scala 3.5 accepts it but warns that such non-local returns are no longer supported and suggests scala.util.boundary. A while loop avoids the issue.

    Complexity

    Time: O(n). The loop visits each index once. Each iteration does one contains, at most one lookup and one insertion, and each of those takes constant time on average for a hash map.

    Space: O(n). In the worst case, no pair exists and the map ends up holding one entry per distinct value.

    Edge cases and common mistakes

    • Equal values. Array(3, 3) with target 6 gives indices 1 and 0. When the loop reaches index 1, the map already holds 3 mapped to 0.
    • Pairing an element with itself. Array(3, 4) with target 6 gives Array(-1, -1). If the code stored nums(i) before the check, index 0 would find its own 3.
    • Duplicate values overwrite. The map keeps only the latest index of a value. That is safe here because a pair found with the earlier copy would already have been returned.
    • Empty array. The loop body never runs and the method returns Array(-1, -1).
    • Reading before checking. Calling indexOfValue(target - nums(i)) without contains throws on the first element that has no partner yet.
    • Overflow. Int is 32 bits and wraps silently. In target - nums(i) the subtraction can leave the range of Int for extreme inputs and wrap to a wrong value, so use Long if the inputs can be that large.

    Testing

    • Array(2, 7, 11, 15), target 9 gives the indices 1 and 0.
    • Array(3, 3), target 6 gives the indices 1 and 0.
    • Array(3, 4), target 6 gives Array(-1, -1).
    • Array(1, 2, 3), target 100 gives Array(-1, -1).
    • Array(), target 5 gives Array(-1, -1).
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free