Skip to content

1. Two SumΒΆ

Problem Link

You can think of the problem as, given a number \(num\) find the index of \(target-num\).

This can be done by storing the index of each \(num\) in a data structure like Hashmap which can be queried to fetch index of a value in a constant time.

Pseudocode
  • Iterate over the \(nums\) array. For each \(num\),
  • check if the \(target-num\) is present in our map.
    • If yes, we can directly return the current index and saved index from here
    • Else, store the index of current num in our map and continue.
Runtime Complexity

Time: \(O(n)\), since we're only iterating the nums array once and querying hashmap is an \(O(1)\) operation.

Space: \(O(n)\), due to the map used for storing num -> index mapping

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        s = dict()
        for i, num in enumerate(nums):
            if num in s:
                return [i, s[num]]
            s[target - num] = i
        return [-1, -1]

func twoSum(nums []int, target int) []int {
    idxMap := make(map[int]int)
    for idx, num := range nums {
        if val, ok := idxMap[num]; ok {
            return []int{val, idx}
        }
        idxMap[target-num] = idx
    }
    return []int{}
}