Explore - LeetCode

One of the most common applications of a hash table or set is determining if an element exists in 𝑂 ( 1 ) O(1). Since an array needs 𝑂 ( 𝑛 ) O(n) to do this, using a hash map or set can improve the time complexity of an algorithm greatly, usually from 𝑂 ( 𝑛 2 ) O(n 2 ) to 𝑂 ( 𝑛 ) O(n). Let's look at some example problems. Example 1: 1. Two Sum Given an array of integers nums and an integer target, return indices of two numbers such that they add up to target. You cannot use the same index twice. The brute force solution would be to use a nested for loop to iterate over every pair of indices and check if the sum is equal to target. This will result in a time complexity of 𝑂 ( 𝑛 2 ) O(n 2 ). In the brute force solution, the first for loop focuses on a number num and does a second for loop which looks for target - num in the array. With an array, looking for target - num is 𝑂 ( 𝑛 ) O(n), but with a hash map, it is 𝑂 ( 1 ) O(1). We can build a hash map as we iterate alon

saved by

• Micah Carroll