LeetCode #1 - Two Sum

Hey there, 👋 Today, we’re going to dive into the very first problem on LeetCode, the classic “Two Sum”. So, grab a cup of coffee and let’s get started!

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.

Constraints

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists.

Analysis

Let’s break down the problem. We need to find two numbers in the array that, when added together, equal the target number.

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

Approach

Now, how do we find these two numbers? We could check every pair of numbers, but that would take a lot of time. Instead, we’ll use a neat trick with a hash map to make things faster. Here’s how:

Create a hash map: This map will keep track of each number in the array and its index.
Loop through the array: For each number, we calculate its complement (i.e., target - number).
Look for the complement in the map: If it’s there, bingo! We’ve found our two numbers. We return the indices of these two numbers.
If the complement isn’t in the map: We store the current number and its index in the map. Maybe it’ll be the complement for a future number.
Keep going: We repeat this process for all the numbers in the array.

Time Complexity

This approach only goes through the array once, so its time complexity is O(n), where n is the size of the array.

Space Complexity

We’re using a hash map to store the numbers from the array, so the space complexity is also O(n).

Code

Alright, enough talk. Let’s see some code! Here’s how you can implement this approach in Python and JavaScript:

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_map = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_map:
                return [num_map[complement], i]
            num_map[num] = i
        return []

JavaScript

var twoSum = function(nums, target) {
    let num_map = {};
    for(let i = 0; i < nums.length; i++) {
        let complement = target - nums[i];
        if(complement in num_map) {
            return [num_map[complement], i];
        }
        num_map[nums[i]] = i;
    }
    return [];
};

Conclusion

And there you have it! We’ve just tackled the “Two Sum” problem from LeetCode using a hash map. This solution is pretty efficient with a time complexity of O(n) and a space complexity of O(n).

Remember, coding is a journey. Keep exploring, keep learning, and most importantly, have fun doing it!

Happy coding 😄

Learn More:

LeetCode #1 – Two Sum