Two Sum

TypeArray, Hash Table
Difficulty
Easy
Last Reviewed12/28/2024

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: The sum of nums[0] + nums[1] = 2 + 7 = 9, which is the target.

Example 2

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

Output: [1,2]

Explanation: The sum of nums[1] + nums[2] = 2 + 4 = 6, which is the target.

Example 3

Input: nums = [3,3], target = 6

Output: [0,1]

Explanation: The sum of nums[0] + nums[1] = 3 + 3 = 6, which is the target.

Solution Overview

Initial Approach

We can use a dictionary to store the indices of elements as we iterate through the list. For each element, we check if the target minus the element is already in the dictionary. If it is, we return the indices of the two elements.

Step by Step Solution

  1. Create an empty dictionary to store the indices of elements.
  2. Iterate through the list of numbers, and for each element:
  3. - Calculate the difference between the target and the current element.
  4. - Check if the difference exists in the dictionary.
  5. - If it does, return the indices of the current element and the element at the difference index.
  6. - If it doesn't, add the current element's index to the dictionary.

Solution Code

1def twoSum(nums, target):
2    # Create a dictionary to store the indices of elements
3    indices = {}
4    
5    # Iterate through the list
6    for i, num in enumerate(nums):
7        # Calculate the complement
8        complement = target - num
9        
10        # Check if the complement is in the dictionary
11        if complement in indices:
12            # Return the indices of the two numbers
13            return [indices[complement], i]
14        
15        # Add the current number and its index to the dictionary
16        indices[num] = i

Solution Walkthrough

[2, 7, 11, 15], target = 9

Step 1

1indices = {}

Initialize an empty dictionary to store the indices of elements

State: indices = {}

Step 2

1for i, num in enumerate(nums):

Iterate through the list of numbers along with their indices

State: indices = {}, i = 0, num = 2

Step 3

1complement = target - num

Calculate the complement by subtracting the current number from the target

State: indices = {}, i = 0, num = 2, complement = 7

Step 4

1if complement in indices:

Check if the complement is already in the dictionary

State: indices = {}, i = 0, num = 2, complement = 7

Step 5

1indices[num] = i

Add the current number and its index to the dictionary

State: indices = {2: 0}, i = 0, num = 2, complement = 7

Step 6

1i = 1, num = 7

Move to the next number in the list

State: indices = {2: 0}, i = 1, num = 7, complement = 2

Step 7

1complement = target - num

Calculate the new complement

State: indices = {2: 0}, i = 1, num = 7, complement = 2

Step 8

1if complement in indices:

Check if the new complement is in the dictionary

State: indices = {2: 0}, i = 1, num = 7, complement = 2

Complexity Analysis

Time Complexity: O(n)

The solution iterates through the list of numbers once to find the target sum.

Space Complexity: O(n)

We use a dictionary to store the indices of elements as we iterate through the list, which has a space complexity of O(n) where n is the number of elements in the list.

Breakdown:

    Algorithmic Patterns

    Two Pointers

    How it's used: Finding pairs efficiently in sorted arrays or lists

    Where in code: Main algorithm

    Example: Finding two elements that sum up to a target

    Common Mistakes

    Mistake 1

    What: Not handling duplicate elements correctly

    Why: Ignoring duplicates can lead to incorrect results

    How to avoid: Use a hashmap to store the indices of elements to handle duplicates

    Mistake 2

    What: Using brute force approach without considering alternatives

    Why: Brute force may not be efficient for large inputs

    How to avoid: Explore hashmaps or sorting-based solutions for better performance

    Mistake 3

    What: Not verifying the input constraints

    Why: Input constraints can impact the algorithm's correctness

    How to avoid: Always check if the input meets the specified constraints

    Interview Tips

    • Understand the problem requirements clearly before starting
    • Consider different approaches and their trade-offs
    • Optimize for time or space complexity based on constraints