LeetCode #1 solution: Two Sum

Problem: 1 two sum

Leetcode #1 solution – Two Sum: 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.

Examples:

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

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

Input: [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?

---

LeetCode #1 Solution: two sum

The Two Sum problem is the first challenge on LeetCode, known as LeetCode #1. It’s a fundamental algorithmic problem that tests your understanding of arrays and hash maps, serving as a building block for more complex problems.

Problem Statement:

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

Constraints:

• Each input will have exactly one solution.
• You may not use the same element twice.
• You can return the answer in any order.

Understanding the Problem

• Input: An array of integers (nums) and an integer (target).
• Output: Indices of the two numbers in nums that add up to target.
• Objective: Find a pair of numbers whose sum equals the target and return their indices.

To grasp this problem thoroughly, consider that you’re given a list of numbers, and you need to find the positions of two distinct numbers that add up to a specific value. It’s important to note that the array can contain negative numbers and zeros, and the indices returned should correspond to the positions in the original array. Also, since there’s guaranteed to be exactly one solution, we don’t need to handle scenarios where no pair sums up to the target.

Approach Discussion

To tackle LeetCode #1 – Two Sum, we’ll explore various strategies, analyzing their time and space complexities. Understanding multiple approaches enhances our problem-solving skills and prepares us for similar challenges..

1. Brute Force Approach

Idea: Iterate through each pair of numbers in the array and check if they add up to the target. This involves using two nested loops to consider all possible combinations.

Time Complexity: O(n²)
Space Complexity: O(1)

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

Explanation: The brute force method is straightforward but inefficient for large datasets. By examining every possible pair, we ensure that we don’t miss any potential solutions. However, the time complexity grows quadratically with the number of elements, making it impractical for large arrays.

2. Two-Pass Hash Map

Idea: Use a hash map to store each number’s index. In the first pass, populate the hash map with all numbers and their indices. In the second pass, check if the complement (i.e., target - num) of each number exists in the hash map.

Time Complexity: O(n)
Space Complexity: O(n)

def two_sum_two_pass(nums, target):
    num_to_index = {}
    # First pass: fill the hash map
    for i, num in enumerate(nums):
        num_to_index[num] = i
    # Second pass: find the complement
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_to_index and num_to_index[complement] != i:
            return [i, num_to_index[complement]]

Explanation: By using a hash map, we reduce the time complexity to linear time. The first pass collects all the data needed for quick lookups. In the second pass, we check for each number if its complement exists in the hash map. We also ensure that we’re not using the same element twice by checking that the indices are not the same.

3. One-Pass Hash Map (Optimal Solution)

Idea: Combine the two passes into one. While iterating through the array, we check if the complement of the current number exists in the hash map. If it does, we return the indices immediately. If not, we add the current number and its index to the hash map.

Time Complexity: O(n)
Space Complexity: O(n)

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

Explanation: This approach is the most efficient because it reduces the problem to a single pass through the array. By checking for the complement and updating the hash map simultaneously, we ensure optimal time performance without additional passes.

Ideal Data Structure and Algorithm

The hash map (Python dictionary) is the ideal data structure for this problem.

Reasons:

• Constant-Time Operations: Hash maps provide O(1) time complexity for insertion and lookup operations, which is essential for optimizing performance.
• Efficient Complement Check: Storing numbers and their indices allows quick determination of whether the complement of a number exists in the array.
• Memory Trade-Off: While we use extra space proportional to the size of the input array (O(n) space complexity), this is acceptable for the significant gain in time efficiency.

By leveraging a hash map, we effectively trade off additional space for faster computation, which is often a worthwhile compromise in algorithm design.

Introduction to the Optimal Solution

In the optimal solution, we aim to find the two numbers that sum up to the target in a single traversal of the array. This approach is efficient and elegant, utilizing the strengths of a hash map to keep track of the numbers we’ve seen so far.

Here’s how it works:

• As we iterate through the array, we calculate the complement of the current number.
• We immediately check if this complement is present in our hash map.
  • If it is, we’ve found the two numbers that add up to the target.
  • If it’s not, we add the current number and its index to the hash map for future reference.

This method ensures that we find the solution as early as possible, without unnecessary computations or iterations.

Let’s break down the optimal LeetCode #1 solution step by step.

def two_sum(nums, target):
    # Step 1: Initialize the hash map
    num_to_index = {}
    
    # Step 2: Iterate over the array using enumerate to get both index and value
    for index, num in enumerate(nums):
        # Step 3: Calculate the complement needed to reach the target
        complement = target - num
        
        # Step 4: Check if the complement is already in the hash map
        if complement in num_to_index:
            # Step 5: If found, return the indices of the complement and the current number
            return [num_to_index[complement], index]
        
        # Step 6: If not found, add the current number and its index to the hash map
        num_to_index[num] = index

Detailed Explanation:

• Step 1: Initialization
  • We start by creating an empty dictionary num_to_index to map numbers to their indices for quick lookup.
• Step 2: Iteration
  • We loop through the array using enumerate, which provides both the current index and the num (value) at that index.
• Step 3: Complement Calculation
  • For each num, we calculate its complement by subtracting it from the target.
  • This complement is the number we need to find in the array to sum up to the target.
• Step 4: Complement Check
  • We check if this complement exists in our num_to_index dictionary.
    • If it does: We’ve previously encountered the complement, so we can return the indices of the two numbers.
    • If it doesn’t: We proceed to the next step.
• Step 5: Returning the Result
  • When the complement is found in the hash map, we return a list containing the index of the complement (retrieved from the dictionary) and the current index.
• Step 6: Updating the Hash Map
  • If the complement is not found, we add the current num and its index to num_to_index.
  • This ensures that future iterations can find this number as a complement if needed.

Why This Approach Works:

• By continuously updating the hash map with numbers we’ve seen, we ensure that at any point, we can check if the complement to the current number has already been encountered.
• This method leverages the fact that the array may contain duplicates, but the problem requires us not to use the same element twice, which is handled by ensuring the indices are different.
• The approach guarantees that we find the solution in linear time, making it highly efficient for large datasets.

Optimization Tips

Use the Walrus Operator (Python 3.8+): Simplify code by combining assignment and condition checking.

def two_sum(nums, target):
    num_to_index = {}
    for index, num in enumerate(nums):
        if (complement := target - num) in num_to_index:
            return [num_to_index[complement], index]
        num_to_index[num] = index

Avoid Redundant Checks: Since we add num to num_to_index after checking for the complement, we ensure we don’t use the same element twice.

Pythonic Practices:

• Use meaningful variable names for readability.
• Keep functions concise and focused on a single task.

LeetCode #1 Solution – Summary

By utilizing a hash map, we’ve optimized the LeetCode #1 solution – Two Sum from O(n²) to O(n) time complexity. This efficient approach is crucial for handling large datasets within acceptable time frames. Understanding this solution provides valuable insights into algorithm optimization and the effective use of data structures.

Key Takeaways:

• Importance of Choosing the Right Data Structure: The hash map was instrumental in reducing the time complexity.
• Algorithmic Efficiency Matters: Optimized algorithms perform significantly better, especially with large inputs.
• Problem-Solving Skills: Breaking down the problem and exploring different approaches leads to better solutions.

Remember, practice and familiarity with various data structures and algorithms are essential for mastering coding challenges like this one.

---

Happy coding!

Continue to challenge yourself with more problems, and don’t hesitate to revisit and refine your solutions as you learn new techniques.

---

Looking for more LeetCode solutions? Stay tuned for upcoming guides on tackling other LeetCode challenges in Python. Whether you’re preparing for technical interviews or aiming to improve your coding skills, exploring a variety of problems will enhance your understanding and proficiency.

You can find this problem on LeetCode, click here.