Two Sum LeetCode Problem #1 [Python Solution]

Are you ready to tackle a popular LeetCode problem? Let’s dive into the Two Sum LeetCode problem where we’re given an array of integers and a target value.

Our goal is to find two numbers in the array that add up to the target and return their indices.

Question

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]

Problem Overview

Imagine we have an array like this: [2, 7, 11, 15], and our target is 9. We need to identify the two numbers that sum up to 9 and return their indices. In this case, it’s 2 and 7 at indices 0 and 1, respectively.

Two Sum LeetCode Problem

Brute Force Approach

The most intuitive way to solve this problem is by checking every possible combination of two values in the array. For each value, scan through the remaining elements to see if any of them, when added to the current value, equal the target.

This brute force method has a time complexity of O(N^2), where N is the number of elements in the array. It’s not very efficient for large arrays.

A Clever Hash Map Solution

Here’s where it gets interesting. We can significantly optimize this using a hash map. Instead of checking every combination, we’ll utilize a hash map to store each element’s value along with its index.

Here’s a step-by-step breakdown of how this works:

We initialize an empty hash map, let’s call it prev_nums, to store each value and its index.
We iterate through the array of numbers.
For each number, we calculate the difference between the target and the current number. This difference is the value we’re looking for to complete the sum.
We check if this difference exists in our prev_nums hash map.
If it does, we’ve found the pair of numbers that sum to the target, and we return their indices.
If it doesn’t, we add the current number to the prev_nums hash map, along with its index.

By doing this, we only need to traverse the array once, and our solution’s time complexity becomes O(N), a significant improvement over the brute force method.

Code Implementation

Now, let’s put this into Python code:

View on GitHub ➹

def twoSum(self, nums: List[int], target: int) -> List[int]:
    prev_nums = {}

    for index, value in enumerate(nums):
        diff = target - value
        if diff in prev_nums:
            return [index, prev_nums[diff]]
    prev_nums[value] = index

Time and Space Complexity

Time Complexity: O(N) – We iterate through the array once.
Space Complexity: O(N) – In the worst case, we might store all elements in the hash map.

Constraints

The length of the input array (nums) is between 2 and 10^4.
Each element in nums is between -10^9 and 10^9.
The target is between -10^9 and 10^9.
There is only one valid solution.

Conclusion: Efficiently Solve Two Sum LeetCode Problem

In this guide, we’ve delved into a popular LeetCode problem known as “Two Sum.” Our goal was to find a pair of numbers in an array that adds up to a target value and return their indices. We explored two approaches: a brute-force method and a clever hash map solution.

The brute-force approach involves checking every possible combination of two values in the array, resulting in a time complexity of O(N^2). While it works, it’s not the most efficient solution, especially for large arrays.

However, we discovered a smarter way to tackle this problem using a hash map.

By creating a hash map that stores each element’s value and index as we iterate through the array, we can significantly optimize the algorithm. This approach reduces the time complexity to O(N), making it much more efficient.

To sum it up, when facing the Two Sum problem, consider the hash map approach. It not only simplifies your code but also ensures faster execution, making it a powerful tool in your problem-solving arsenal.

Now, armed with this optimized approach, you’re well-prepared to tackle the Two Sum LeetCode problem efficiently and with confidence.

Solve Two Sume on LeetCode now.

Happy coding!