Two Integer Sum

Problem:

• https://neetcode.io/problems/two-integer-sum
• https://leetcode.com/problems/valid-anagram/description/

Given an array of integers nums and an integer target, return indices of the 
two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not 
use the same element twice. 

You can return the answer in any order.

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]

Description

The TwoSum problem is an interesting problem. Even though the problem is marked as Easy , it has a non-obvious solution. This problem should have been a Medium problem.

In short, the problem is to find a case so that x + y = target is true. We know that in each iteration, there are 2 known variables, x and target where x is each number in the list, nums[i] and target is given from the parameter.

So, if we know x and target, to find y, the equation becomes y = target - x.

However, it is never guaranteed that x + y = target is true, but at some iteration, a solution could be found. So, for that to happen, we need to keep track of the complement number, y = target - x so that at some point, the equation x + y = target is true (i.e. we found the solution).

To implement the solution, we are given a hint that the solution would have exactly one solution . That means, we can use a set or dictionary to keep track of the complement number, y. However, the problem specifically requires us to return the index of the complement number; using a dictionary makes more sense since we can easily map the number -> number_position in our dictionary.

Solving the problem requires us to iterate through the list, evaluate the complement number, y using y = target - x, and check if y exists in the dictionary, if so, we know we found two numbers such that it adds up to the target (i.e. the solution). However, if y does not exist in our dictionary, store the result in our dictionary so that y -> y_position . Repeat until y = target - x exists in the dictionary. This implies that the solution x + y = target is found.

Logic

• Iterate through each number,
  • Check if the solution y = target - x exits in the dictionary
  • If the solution y = target - x exists in the dictionary, return the position of the solution and current iteration index. (this means x + y = target is found)
  • Otherwise, keep track of the y = target - x by mapping y -> y_position until at some iteration, a solution x + y = target is found.
    
    

Solution

class Solution():
    @staticmethod
    def twoSum(nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

        # Dictionary to store the index of the numbers we have seen
        num_to_index = {}
        
        # Iterate over the list
        for i, num in enumerate(nums):
            # Calculate the complement of the current number
            complement = target - num
            
            # Check if the complement exists in the dictionary
            if complement in num_to_index:
                # If it exists, return the indices of the complement and 
                # the current number
                return [num_to_index[complement], i]
            
            # Otherwise, add the current number and 
            # its index to the dictionary
            num_to_index[num] = i

        # If there is no solution, return an empty list 
        # (though the problem states there is exactly one solution)
        return []

solution = Solution.twoSum([3, 2, 4], 6)