Problem Description

Difficulty: Easy

Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.

Assume that every input has exactly one pair of indices i and j that satisfy the condition.

Return the answer with the smaller index first.

Example:

Input: 
nums = [3,4,5,6], target = 7
Output: [0,1]
# Explanation: nums[0] + nums[1] == 7, so we return [0, 1].

Additional examples are provided in the tests below.

Initial Solution

from typing import List, Callable

class InitialSolution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, i_num in enumerate(nums):
            for j, j_num in enumerate(nums[1:]): 
                if i_num + j_num == target and i != j+1: # must 'and' to ensure i != j 
                    return [i,j+1]
        return [] # not really needed as we are told a solution exists

Note: I first tried to ensure i != j by starting the for j loop at [1:] instead of 0. This failed the following case, which led me to add the and operator in the equality check, at which point it was apparent the slicing was unnecessary. Careful reading of the question indicates that the indices are not allowed to be equal, but there is no restriction on the numbers being equal.

nums = [2,5,5,11]
target = 10
output = [1,2]

Let’s clean up the function:

class BruteForceSolution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, i_num in enumerate(nums):
            for j, j_num in enumerate(nums): 
                if i_num + j_num == target and i != j:
                    return [i,j]
        return []

# Examples for testing purposes.
#nums, target = [3,4,5,6], 7 # output [0,1]
#nums, target = [4,5,6], 10 # output [0,2]
#nums, target = [3,3], 6 # output [0,1] 
#nums, target = [3,2,4], 6 # output [1,2]
nums, target = [2,5,5,11], 10 # output [1,2] # tricky

#solution = InitialSolution()
solution = BruteForceSolution()
solution.twoSum(nums, target)

Initial Results

BruteForceSolution passes NeetCode submission.

Time Complexity: O(n)*O(n) = O(n²)

Tests

def test(fn: Callable[[List[int], int], List[int]]) -> None:
    nums, target = [3, 4, 5, 6], 7
    output = [0, 1]
    assert output == fn(nums, target)
    
    nums, target = [4, 5, 6], 10
    output = [0, 2]
    assert output == fn(nums, target)
    
    nums, target = [3, 3], 6
    output = [0, 1]
    assert output == fn(nums, target)
    
    nums, target = [3, 2, 4], 6
    output = [1, 2]
    assert output == fn(nums, target)
    
    nums, target = [2, 5, 5, 11], 10
    output = [1, 2]
    assert output == fn(nums, target)
    print('Tests Passed')

solution = BruteForceSolution()
test(solution.twoSum)

NeetCode Solution

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

        for i, n in enumerate(nums):
            diff = target - n
            if diff in prevMap:
                return [prevMap[diff], i]
            prevMap[n] = i

solution = Solution()
test(solution.twoSum)

Conclusion

The above code represents a more optimal solution. It uses a hashmap (dictionary) called prevMap that stores previously encountered numbers as keys with their corresponding indices as values. Here prevMap acts as a lookup table to quickly check if the complement of the current number (i.e., the number needed to reach the target) has been seen before. This method has a time complexity of O(n) because it processes each element of the list once only. A little extra memory is needed, since we have to create the lookup table.

Time complexity: O(n)
Space complexity: O(n)