Problem Statement in English

You’re given a list of numbers nums, and a target value, target. Your task is to return a list of the first 2 indices from nums whose values sum up to target.

Approach

To solve this problem, we can make a pass over nums, and index all its records - every unique entry, and the position of that entry in nums.

From there, to find the first 2 indices satisfying this condition, you can iterate over the nums array again, and check whether the other summand required to meet target exists in the index we made (a map essentially), if it does, then return this index, and the index of the summand from the index we made previously.

Solution in Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        store = {}

        for i in range(len(nums)):
            store[nums[i]]=i

        for i in range(len(nums)):
            needed = target - nums[i]
            if needed in store and store[needed]!=i:
                return [i, store[needed]]

Complexity

  • Time: $O(n)$
    Since we need to iterate over the array to generate the index.

  • Space: $O(n)$
    Since we create an index that contains atmost as many elements as the target array.

And we are done.