Leetcode 1 - Two Sum

Table of contents

Problem

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(n^2) time complexity?

Explanation/Approach

This problem requires finding two numbers from the given array that add up to the target. We have several ways to approach this problem.

• Brute Force: We can iterate over the array with two loops and check all possible pairs. If a pair adds up to the target, we return the indices. This approach is straightforward but not efficient.
• Two-pass Hash Table: This approach involves two iterations. In the first, we add each element’s value and its index to the hash table. In the second, for each element, we check if the hash table contains the complement (target - current element). If it does, and it’s not the same element, we found the solution.
• One-pass Hash Table: This approach improves the Two-pass Hash Table method by checking and adding elements to the hash table in the same iteration. For each element, we check if its complement is in the table before adding the current element to the table.
  
  

Solution 1: Brute Force

class Solution:
    def two_sum(self, nums: List[int], target: int) -> List[int]:
        # Get the length of the list
        num_count = len(nums)

        # Iterate over the list with two nested loops
        for i in range(num_count - 1):
            for j in range(i + 1, num_count):
                # If a pair adds up to the target, return the indices
                if nums[i] + nums[j] == target:
                    return [i, j]

        return []  # No solution found

Time and Memory Complexity

The time complexity is O(n^2) as there are two nested loops over the array. The space complexity is O(1) as no additional space is required.

Explanation

The solution iterates over the list with two nested loops. For every pair of numbers, it checks if they add up to the target. If they do, it immediately returns the indices. If no pair adds up to the target, it returns an empty list.

Solution 2: Two-pass Hash Table

class Solution:
    def two_sum(self, nums: List[int], target: int) -> List[int]:
        # Create an empty hash table
        num_map = {}
        num_count = len(nums)

        # First pass: build the hash table
        for i in range(num_count):
            num_map[nums[i]] = i

        # Second pass: find the complement
        for i in range(num_count):
            complement = target - nums[i]
            if complement in num_map and num_map[complement] != i:
                return [i, num_map[complement]]

        return []  # No solution found

Time and Memory Complexity

The time complexity is O(n) as we traverse the array twice. The space complexity is O(n) as we need a hash table to store n elements.

Explanation

In the first pass, we add every number and its index to the hash table. In the second pass, we look for each number’s complement in the hash table. If we find it, and it’s not the same number, we return the indices.

Solution 3: One-pass Hash Table

class Solution:
    def two_sum(self, nums: List[int], target: int) -> List[int]:
        # Create an empty hash table
        num_map = {}
        num_count = len(nums)

        # Single pass: find the complement and add the number to the hash table
        for i in range(num_count):
            complement = target - nums[i]
            if complement in num_map:
                return [num_map[complement], i]
            num_map[nums[i]] = i

        return []  # No solution found

Time and Memory Complexity

The time complexity is O(n) as we traverse the array once. The space complexity is O(n) as we need a hash table to store n elements.

Explanation

This solution is an improvement over the two-pass hash table. For every number, it checks if its complement is in the hash table before adding the number to the table. If the complement is found, it returns the indices.