Let’s take the classic Two Sum problem and move it from slow and clunky to clean and quick.

Problem

The original problem description from leetcode .

We are given:

• an integer array nums
• an integer target

Our task is to find two different elements in nums whose sum equals target, then return their indices as an array.

Extra rules:

1. We cannot reuse the same element twice.
2. LeetCode guarantees exactly one valid pair, so no tie-breakers needed.

Here is an illustration. In given inputs, when elements 2 and 7 are summed up, they give 9 which is our target value. So as a result we must return [0,1] – array of indexes of those two elements.

Example of problem statement

Brute-Force Solution

The most obvious approach is brute-force:

1. Loop through every element.
2. Inside that loop, add it to every other element.
3. If the sum equals target, return those two indices.

Illustration of brute-force solution

Time Complexity: O(N²) in worst case.

Space Complexity: O(1) because independent of array size we just need few variables.

Hash-Map-Based Solution

We can do better.

Take any element in the array. Instead of adding it to every other element, notice that the complement we need is target – element.

If we can find that complement in the array, we have solved the problem skipping all nested loops!

However, looking for the complement in the array still takes O(N) time per element. So we need to use data structure which would give us constant time element lookup. Of course, this is hash map!

So the solution could be following

1. Build the map in one pass — key = array value, value = its index.
   • We need index here because as a result we will need provide indexes of the two element, so we need to store that index as hash map value.
2. Scan the array again. For each element, compute complement = target − element and check the map.

Illustration of HashMap based Solution

We need O(N) operations to build the map and another O(N) to iterate through the array, compute each complement, and look it up in the map.

Therefore, the overall time complexity is O(N) + O(N) = O(N), and the space complexity is O(N).

One-pass solution

Instead of loading the entire array into the map first, we can build the map lazily, iterating through the array only once.

The time complexity is still O(N), but the constant factor is lower.

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
       val elementsMap = HashMap<Int,Int>()
       for (i in 0..nums.size -1 ) {
            val complement = target - nums[i]
            val complementIndex = elementsMap[complement]
            complementIndex?.let {
                return intArrayOf(i, complementIndex)
            }
            elementsMap[nums[i]] = i
       }
       throw IllegalArgumentException("No solution is possible")
    }
}

Takeaway

This is an easy problem, but it shows an important concept: we can solve a problem much more efficiently simply by choosing the right data structure.