Blind 75 -& LeetCode Problem 1: Two Sum

 

Problem Statement:

LeetCode Problem: "Two Sum"

Given an array of integers nums and an integer target, return the 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.

Function Signature:

vector<int> twoSum(vector<int>& nums, int target);

def twoSum(nums: List[int], target: int) -> List[int]:

Optimal Approach:

The optimal solution for this problem involves using a hash map (dictionary in Python) to store the numbers we've seen so far and their corresponding indices. This allows us to check if the complement (i.e., target - current number) of the current number exists in the hash map.

Key Idea:

• Iterate through the list while maintaining a hash map to store numbers and their indices.
• For each number, check if its complement (target - number) is already in the hash map.
• If the complement is found, return the indices of the current number and its complement.
• If the complement is not found, add the current number and its index to the hash map.

This approach allows us to solve the problem in O(n) time, where n is the number of elements in the list.

LeetCode-Compatible Code Implementations:

C++ Solution:

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> num_map; // Map to store the numbers and their indices
        
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i]; // Find the complement
            
            // If the complement is already in the map, return its index and current index
            if (num_map.find(complement) != num_map.end()) {
                return {num_map[complement], i};
            }
            
            // Otherwise, store the current number and its index
            num_map[nums[i]] = i;
        }
        
        return {}; // Return an empty vector if no solution is found (shouldn't happen with given assumptions)
    }
};

Python Solution:

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_map = {}  # Dictionary to store numbers and their indices
        
        for i, num in enumerate(nums):
            complement = target - num  # Calculate complement
            
            # Check if complement is already in the dictionary
            if complement in num_map:
                return [num_map[complement], i]
            
            # Store the current number and its index
            num_map[num] = i
        
        return []  # Return an empty list if no solution is found (not needed per problem statement)

Step-by-Step Explanation of Code:

1. Initialize a hash map (num_map):

   • This map stores the number as the key and its index as the value. It helps quickly check if the complement of the current number exists.

2. Iterate over the input array:

   • For each number, calculate the complement (target - num).
   • Check if the complement exists in the hash map.
     • If it does, return the index of the complement and the current index.
     • If it doesn't, add the current number and its index to the hash map.

3. Return the indices:

   • As soon as we find a pair, return the two indices.
   • The problem guarantees that there is exactly one solution, so no need to handle cases with no solution.

Dry Run / Execution Steps:

Let's perform a dry run on the input nums = [2, 7, 11, 15], target = 9.

• Step 1: Initialize num_map = {}.
• Step 2: Iterate through nums:
  • Index 0: num = 2, complement = 9 - 2 = 7.
    • 7 is not in num_map. Add num_map[2] = 0.
  • Index 1: num = 7, complement = 9 - 7 = 2.
    • 2 is in num_map at index 0. Return [0, 1].

The output is [0, 1].

Alternative Approaches & Why Not?

1. Brute Force:

   • Approach: Check every pair of numbers in the array to see if they sum up to the target.
   • Time Complexity: O(n^2), where n is the number of elements in the array.
   • Space Complexity: O(1).
   • Why Not: This approach is inefficient and too slow for large inputs.

2. Sorting + Two Pointers:

   • Approach: Sort the array, then use two pointers to find the sum.
   • Time Complexity: O(n log n) due to sorting.
   • Space Complexity: O(n) for storing indices after sorting.
   • Why Not: Sorting changes the original indices, which violates the problem constraints. Also, it's not as efficient as the hash map approach.

3. Dynamic Programming:

   • Approach: Use dynamic programming to store solutions of subproblems.
   • Time Complexity: O(n^2), similar to brute force.
   • Space Complexity: O(n).
   • Why Not: This is overkill and unnecessary for this problem.

Best Solution & Why It’s Best:

The hash map approach is the best solution because:

• Time Complexity: O(n) — we only need one pass through the array.
• Space Complexity: O(n) — we use a hash map to store elements.
• It is the most efficient solution for this problem.

Approach	Time Complexity	Space Complexity
Brute Force	O(n^2)	O(1)
Sorting + Two Pointers	O(n log n)	O(n)
Hash Map (Best)	O(n)	O(n)

Complexity Analysis:

• Hash Map:
  • Time Complexity: O(n) — We iterate over the array once, and each lookup and insertion operation in the hash map is O(1).
  • Space Complexity: O(n) — We store at most n numbers in the hash map.

Conclusion:

The best approach for the "Two Sum" problem is using a hash map (dictionary in Python) because it provides a linear time solution and avoids unnecessary complexity.

Similar Problems for Practice:

1. Two Sum II – Input Array Is Sorted
2. 3Sum
3. Two Sum IV - Input is a BST

By solving these problems, you can practice optimizing solutions using hash maps and other techniques.