On the first Leetcode question we need to achieve a target number by summing numbers from known list. We can solve this problem in two ways: brute force, which tries all combinations, or by using a dictionary for a more efficient lookup.

Brute force - the easiest solution- but where’s the efficiency?

I have a confession: most of the time, I prefer brute force code. It’s simpler and has a Soviet-era feel to it. When I’m writing brute force solutions I know it’s gonna work for ever!

A simple brute force approach involves checking every pair of elements to see if their sum matches the target. We can achieve this using nested loops. The outer loop iterates through the list from the beginning to the second-to-last element. For each element from the outer loop, the inner loop iterates through the remaining elements (from the element after the outer loop’s current element to the end). This approach, however, has a time complexity of O(n^2) - Which is pretty bad in terms of efficiency

1
2
3
4
5
6
7
8

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        b = len(nums)
        for i in range(b - 1):
            for j in range(i + 1, b):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

Single-pass dictionary

A better efficient approach is to use a dictionary. This approach iterates through the array only once. For each element, we check if the target value minus the current element exists within the hash table. If it does, we’ve found a matching pair! If not, the current element is simply added to the hash table.

1
2
3
4
5
6
7
8

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        used = {}
        for i, num in enumerate(nums):
            if target - num in used:
                return([used[target-num],i])
            elif num not in used:
                used[num] = i

I hope these solutions finds you well. You can give me some feedback on Dolev@Ravid.Email.

Good Luck!

Photo by Hitesh Choudhary on Unsplash