Two Sum - Leetcode 1 - HashMap - Python

LeetCode Problem: Two Sum

In this video, the speaker explains how to solve the LeetCode problem of finding two values in an input array that sum up to a target value. The speaker first explains a brute force approach and then introduces a more efficient solution using hash maps.

Brute Force Approach

• The most intuitive way to solve this problem is by checking every combination of two values in the input array and seeing if they can sum up to our target.

• We start with the first element in the array and check every combination we can make that includes it. If none of those combinations add up to our target, we move on to the next element and repeat the process.

• We don't have to check values that came before because we already checked their combinations when iterating through previous elements.

• This algorithm has a worst-case time complexity of O(N^2).

Efficient Solution Using Hash Maps

• For each number in the input array, we can find its complement (the difference between it and our target value).

• By creating a hash map of every value in our input array, we can instantly check if its complement exists.

• We don't need to initialize our hash map; instead, we can add elements as we iterate through them.

• This algorithm has a worst-case time complexity of O(N).

Time and Memory Complexity

In this section, the speaker explains the time and memory complexity of a solution to a problem.

Understanding Time and Memory Complexity

• Iterating through an array once and adding each value to a hash map is a constant time operation.

• Checking if a value exists in the hash map is also a constant time operation.

• The time complexity of this solution is Big O of n.

• The hash map uses extra memory, so the memory complexity is also O of n.

Coding the Solution

In this section, the speaker codes the solution using Python.

Creating a Hash Map

• We need to create a hash map called "previous_map" that stores every element that comes before the current home.

• Each previous element will be stored in this map by mapping its value to its index.

Iterating Through Every Value in Array

• We iterate through every value in the array using Python.

• Before we add each value to our map, we check if the difference (target minus n) is already in our hash map.

Finding Solutions

• If we find that the difference is already in our hash map, we can return the solution which is a pair of indices.

• The first index can be obtained from previous_map[difference].

• The second index is just i (the current index).

Updating Hash Map

• If we don't find any solutions, we update our hash map for this value n by storing its index i as previous_map[n] = i.

• Since we're guaranteed that a solution exists, there's no need to return anything out here.

Conclusion

In this section, the speaker concludes the video by summarizing the solution and its benefits.

Benefits of Solution

• This neat little trick allows us to reduce the amount of code needed to solve a problem.

• By iterating through an array once and using a hash map, we can find solutions in O(n) time complexity and O(n) memory complexity.