Let’s start with the example given in the LeetCode problem. Suppose we’re given the array [2, 7, 11, 18] and a target value of 9. We’re tasked with finding two number within the array that add up to the target and then return the indices of those respective number.
Approach #1: Brute Force (Naive)
The naive approach typically involves using two nested for loops. How would we use them to solve the problem? Begin by iterating via the array starting with the zero index and we’ll have another for loop nested within which starts with the first index (j = i + 1). We’ll iterate through the rest of array and for every value within that array, we’ll check if any of those values is the complement to the value in the zero index.
Key: loop via each element (x) and if there is another value that equals to (target — x).
Figure 1: Having ‘j’ start at index 1, we have it iterate via the rest of the array and check if any of those values is the complement to the value where index ‘i’ is pointing to. If it is, then nums[i] + nums[j] = target. If not, then increment the ‘i’ pointer by 1 and then run through the 2nd for loop again, etc.
Time Complexity: O(n²) — For each element, we try to find its complement by looping via the rest of the array which takes O(n) time
Space Complexity: O(1)
Approach #2: Two Pass Hash Table
When talking about a more real world and optimal solution, a brute force solution just doesn’t cut it.
This is where data structures come into play.
In order to improve our run-time complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to look up its index. Writing an algorithm with nested for-loops is a no no at this point. The best way to maintain a mapping of each element in the array to its index? A hash table.
Implementing a hash table can reduce the look-up time from O(n) to O(1) by trading space for speed.
A hash table is built recently for this purpose, it supports fast look up in near constant time. We say “near” constant time because if a collision occurred, a lookup could be degenerated to O(n) time. However, lookup’s in hash tables should be amortized O(1) as long as the hash table was chosen carefully.
A simple implementation uses two iterations of the array. In the first iteration, we add each elements value and its index to the table (which makes sense because hash table accept key-value pairs (K, V)). In the second iteration we then check if each element’s complement (target — nums[i]) exists in the same.
NOTE: the complement must not be nums[i] itself.
Time Complexity: O(n) — each lookup cost only O(1)
Space Complexity: O(n)
Approach #3: One Pass Hash Table
As the approach suggests, this solution will implement a one pass hash table. While we iterate through the array and insert the elements into the table, we can also look back to check if the current element’s complement already exists in the table. If it exists, we have found a solution and return it immediately.
Time Complexity: O(n) — traverses list iterating n elements only once. Each lookup is O(1) constant time.
Space Complexity: O(n) — Extra space required depends on the number of items in the hash table which stores at most, n elements.
Top comments (0)