Two Sum

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Find two indices that sum to the target
• Cannot use the same number twice

What is Being Asked?

(One sentence on the actual task.)

• Find two numbers that sum to a target amount

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Cannot do $O(n^2$)

Approach Taken

(Step-by-step logic or pseudocode before coding.)

• Keep a Hash Map to store value:index pair
• Iterate through each number
  • If $target-num$ exists within the Hash Map then you found the answer
  • Else, add current index to Hash Map

Why This Works

(Explain the core reason the solution is correct.)

• Given nums = [2,7,11,15], target = 9
• We can return [0, 1] or [1,0]
• When we are looking at 7 we just need 2, which is already in our Hash Map

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Hash Map
• Array

Time & Space Complexity

• Time: O(N) → Reason: Iterating through the array once
• Space: O(N) → Reason: Storing each value once

Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # nums = [3,3,3], target = 9
        # store index for each number in `nums`
        # iterate through each num and try to find the complementing pair to make the target

        # brute force:
        # nested loop - O(n^2)
        # for i in range(len(nums)): # 0, 1 
        #     for j in range(i + 1, len(nums)): # 1, 2 | 2
        #         if nums[i] + nums[j] == target: # no, no
        #             return [i, j] 
        
        # optimized
        hashmap = {} # 3: 
        for i, num in enumerate(nums):
            if target - num in hashmap:
                return [i, hashmap[target - num]]
            else:
                hashmap[num] = i

Common Mistakes / Things I Got Stuck On

• Tried to store indices in an array
• Tried to not include a duplicate
• Key is to rely on the fact that 2,7 or 7,2 are both valid