Solving the Two Sum Problem on LeetCode with Python

Hello! Today, we’re going to tackle a popular LeetCode topic problem known as Two Sum. This problem is a great introduction to algorithmic thinking and problem-solving in software engineering. Let’s dive into the problem, break it down step by step, and solve it using Python. Even though I am using Python to solve this Two Sum problem, the fundaments and concepts of solving the problem are similar in other coding languages:

The Problem Break Down

Problem Statement

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

Assumptions:

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

Examples

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

Constraints

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Only one valid answer exists.

Difficult: Easy

Our Goal

Our goal is to find an algorithm to solve this problem efficiently. The naive approach involves nested loops, leading to O(n^2) time complexity, which isn’t optimal for large inputs. We aim to find a solution with a better time complexity.

Approach

We can solve this problem in O(n) time complexity using a dictionary (hash map). The idea is to store each number and its index in the dictionary as we iterate through the array. For each number, we check if the complement (i.e., target - number) exists in the dictionary. If it does, we have found the solution.

Here’s how we can implement this approach:

1. Initialize an empty dictionary to store numbers and their indices.
2. Iterate through the array.
3. For each number, calculate its complement (target - number).
4. Check if the complement exists in the dictionary.
   • If it does, return the indices of the current number and its complement.
   • If not, add the number and its index to the dictionary.
5. If no solution is found during the iteration, return an empty list (though the problem guarantees one solution).

Python code solution typed:

class Solution(object):
    def twoSum(self, nums, target):
        # Create a dictionary for values
        num_dict = {}
        
        # Iteration
        for index, num in enumerate(nums):
            # Calculate complement blue
            complement = target - num
            
            # Check if the complement in the dictionary
            if complement in num_dict:
                # Return the indices of the complement and the current number
                return [num_dict[complement], index]
            
            # Add the current number and its index to the dictionary
            num_dict[num] = index