Two Integer Sum

Problem:

• https://neetcode.io/problems/two-integer-sum
• https://leetcode.com/problems/two-sum/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]

Solution

Here are two ways in solving this problem.

1. Sort, then use two-pointers.
2. Use hashmap to lookup complementary number

Using Two-pointers

First, sort the array while keeping track of original indices. Create two pointers,

Let left be the starting index (0)

Let right be the ending index (len(nums) - 1)

While left < right, compute sum = nums[left] + nums[right]. if sum == target, we found our solution, lookup and return the pair original indices. if sum < target, move left forward to increase the sum. if sum > target, move right backward to decrease the sum.

class Solution:
    @staticmethod
    def twoSum(nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # Keep track of original indices by enumerating
        indexed_nums = list(enumerate(nums))  # [(index, value), ...]
        indexed_nums.sort(key=lambda x: x[1])  # sort by value

        left, right = 0, len(indexed_nums) - 1

        while left < right:
            sum = indexed_nums[left][1] + indexed_nums[right][1]

            if sum == target:
                # Return original indices
                return [indexed_nums[left][0], indexed_nums[right][0]]
            elif sum < target:
                left += 1
            else:
                right -= 1

        return []  # if no solution found (though problem states one exists)


# Example usage
print(Solution.twoSum([3, 2, 4], 6))  # [1, 2]

Using Hashmap

Traverse the array and store each number with its index in a hashmap. For each number, compute complement = target - num, if complete exists in the hashmap, return the pair indices.

Start with a hashmap, if the number doesn't exist in the hash, add the number to keep track. If the complementary number exists in the hashmap, then we know that number makes sum(arr[left], arr[right] == target, return the indices.

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)