Two Sum

• Difficulty: Easy
• Topics: Array, Hash Table
• Link: https://leetcode.com/problems/two-sum/

Problem 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]

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

**Follow-up:**Can you come up with an algorithm that is less than O(n2) time complexity?

Solution

1. Problem Deconstruction

Rewriting the Problem

1. Technical Version:

   • Given an array nums of integers and a target integer target, find the indices (i, j) such that nums[i] + nums[j] = target with i ≠ j. The solution is guaranteed to exist uniquely.

2. Beginner Version:

   • You have a list of numbers and a target sum. Find two different numbers in the list that add up to the target, and return their positions.

3. Mathematical Version:

   • Let $S = \{ (i, j) \mid i, j \in [0, n-1], i \neq j, \text{ and } \text{nums}[i] + \text{nums}[j] = \text{target} \}$.
   • The problem requires outputting the unique element of $S$.

Constraint Analysis

1. Array Length (2 ≤ nums.length ≤ 1e4):

   • Limits brute-force feasibility. $O(n^2)$ is computationally expensive for $n=1e4$ (100M operations).
   • Edge Case: Smallest array (n=2) must directly return [0,1].

2. Value Range (-1e9 ≤ nums[i], target ≤ 1e9):

   • No overflow issues in Python, but hash-based solutions must handle negative keys.
   • Edge Case: Large values could stress hash collisions or caching.

3. Unique Solution Guarantee:

   • Simplifies logic; no need to handle multiple pairs or no solution.
   • Edge Case: Duplicate values (e.g., nums = [3,3], target=6) must not return the same index twice.

---

2. Intuition Scaffolding

Analogies

1. Real-World Metaphor:

   • “Like finding two items in a shopping cart whose prices sum to a gift card’s value.”

2. Gaming Analogy:

   • “In a RPG, combining two potions to create a specific effect—each potion can’t be reused.”

3. Math Analogy:

   • “Solving $x + y = k$ where $x, y$ are elements of a multiset.”

Common Pitfalls

1. Reusing Elements:
   • Checking nums[i] + nums[i] = target violates i ≠ j.
2. Overlooking Duplicates:
   • Assuming all elements are unique (e.g., [3,3]).
3. Premature Optimization:
   • Sorting first (disrupts indices) without tracking original positions.
4. Brute-Force Inefficiency:
   • Nested loops fail for large n.
5. Hashmap Misuse:
   • Not handling complements correctly (e.g., storing values before checking).

---

3. Approach Encyclopedia

Brute Force (Naive)

• Pseudocode:

  for i in range(len(nums)):  
      for j in range(i + 1, len(nums)):  
          if nums[i] + nums[j] == target:  
              return [i, j]  
  

• Complexity:
  • Time: $O(n^2)$ from $\sum_{i=1}^{n-1} (n-i) = \frac{n(n-1)}{2}$ operations.
  • Space: $O(1)$.
• Visualization:

  nums = [2,7,11,15], target=9  
  i=0: j=1 → 2+7=9 → return [0,1]  
  

Hashmap (Optimal)

• Pseudocode:

  hashmap = {}  
  for i, num in enumerate(nums):  
      complement = target - num  
      if complement in hashmap:  
          return [hashmap[complement], i]  
      hashmap[num] = i  
  

• Complexity:
  • Time: $O(n)$ (single pass, hash lookups are $O(1)$ average-case).
  • Space: $O(n)$ (store up to $n$ elements).
• Visualization:

  nums = [3,2,4], target=6  
  Step 1: hashmap={3:0}  
  Step 2: hashmap={3:0, 2:1}  
  Step 3: complement=6-4=2 → found in hashmap → return [1,2]  
  

---

4. Code Deep Dive

Optimal Solution (Hashmap)

def twoSum(nums, target):  
    hashmap = {}  # Stores value → index mappings  
    for i, num in enumerate(nums):  
        complement = target - num  
        if complement in hashmap:  # O(1) lookup  
            return [hashmap[complement], i]  
        hashmap[num] = i  # Insert after check to avoid reuse  

Edge Case Handling

• Example 3 (nums = [3,3], target=6):
  • First 3 stored in hashmap. Second 3 finds complement 3 already present, returns [0,1].
• Large Inputs:
  • Hashmap handles $n=1e4$ efficiently (modern systems execute $1e4$ operations in ~1ms).

---

5. Complexity War Room

Hardware-Aware Analysis

• Memory: At $n=1e4$, hashmap uses ~40KB (assuming 4B per int key/value), fitting in CPU cache.

Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force	$O(n^2)$	$O(1)$	High	❌ Fails large $n$
Hashmap	$O(n)$	$O(n)$	Medium	✅ Optimal

---

6. Pro Mode Extras

Variants

• Three Sum: Find all triplets summing to zero (LC 15).
• k Sum: Generalize to $k$ elements (backtracking/DP).

Interview Cheat Sheet

• Key Points:
  1. Always clarify uniqueness and input constraints.
  2. Mention hashmap trade-offs (space for time).
  3. Practice edge cases: duplicates, negative numbers, minimal input.