NOTE: You can also read this in LeetCode.
Problem: Check if N and Its Double Exist
Given an array arr of integers, check if there exists two integers N and M such that N is the double of M ( i.e. N = 2 * M).
More formally check if there exists two indices i and j such that :
- i != j
- 0 <= i, j < arr.length
- arr[i] == 2 * arr[j]
Input: arr = [10,2,5,3] Output: true Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5.
Input: arr = [7,1,14,11] Output: true Explanation: N = 14 is the double of M = 7,that is, 14 = 2 * 7.
Input: arr = [3,1,7,11] Output: false Explanation: In this case does not exist N and M, such that N = 2 * M.
- 2 <= arr.length <= 500
- -10^3 <= arr[i] <= 10^3
We could use a for loop nested in a for loop to check for each element if there is a corresponding number that is its double.
But even though we would have a constant space complexity of O(1), we would have a quadratic time complexity of O(n²) which is not good and should be avoided if possible.
It also allows us to solve this problem by traversing the array only once:
In each iteration of a for statement we check if the current value already exists as a key in our object.
- If so, a number and its double exist in the array, we must return true.
- If not, store key/value pairs where one pair has the current element divided by 2 as a key and the other pair has the current element multiplied by 2 as a key. Notice that the values we store with each key do not matter, since we only check the keys.
If the for loop ends without finding a match, it means that the array does not contain a number and its double, we must return false.
Since we created a Hash Table with a size that scales linearly according to the size of our input array, it has a linear space complexity of O(n).
This time we only traverse the array once, so it has a linear time complexity of O(n).
The main difference in our use case would be that instead of storing each key in the Hash Table as a string, we would store each key in a Map as a number. An Object only supports string and symbol as a key, but a Map supports objects and any primitive type as keys.
The problem with using a Hash Table (object) or Map is that when we insert a key/value pair, the key is required but its value is not.
When we need a Hash Table data structure's properties to solve the problem, but we only need keys instead of key/value pairs it makes sense to use a Set data collection.
Similar to an object and a Map, we can assume that we can retrieve a value from a Set with a constant time complexity of O(1).
We created a Set with a size that scales linearly according to the size of our input array, it has a linear space complexity of O(n).
Just like our previous solution we only traverse the array once, so it has a linear time complexity of O(n).
Share with us your solutions for this problem.