1346. Check If N and Its Double Exist

EasyArrayHash TableTwo PointersBinary SearchSorting

Problem Description

In this problem, we are given an array arr consisting of integers. Our task is to determine if there are two distinct indices i and j in the array such that:

The indices i and j are not the same (i != j).
Both indices are within the bounds of the array (0 <= i, j < arr.length).
The value at index i is double the value at index j (arr[i] == 2 * arr[j]).

We need to return a boolean value, true if such a pair of indices exists, and false otherwise.

Intuition

To solve this problem, we aim to efficiently check if for any given element arr[i], there exists another element arr[j] which is exactly half of arr[i]. Instead of using a brute-force approach which checks all possible combinations and results in quadratic time complexity, we can use a hash map to optimize the search process. A hash map allows for constant time lookups, reducing our overall time complexity.

The intuition behind using a hash table is:

First, we create a hash map (denoted as m) that stores the value to index mapping of the array elements. This step helps us to quickly check if a value exists in the array and simultaneously ensures that the indices are distinct.
Next, we iterate over the array, and for each element arr[i], we check whether double that element (2 * arr[i]) exists in the hash map.
If it does exist, we should also ensure the indices are not the same to satisfy the condition i != j. This is confirmed by checking if the index associated with 2 * arr[i] in the hash map m is different from i.
If such a condition is satisfied, we can return true, indicating that we've found two indices meeting the problem's criteria.

By hash mapping and searching for the double of the current element, we reduce the search complexity, which makes our algorithm more efficient than a naive approach.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The solution approach involves the following steps, making use of hash maps and list comprehensions in Python:

Creation of a Hash Map: A hash map m is created to store values from the arr list, mapping them to their corresponding indices. We do this using a dictionary comprehension in Python:
```
m = {v: i for i, v in enumerate(arr)}
```
Here, for every element v in arr, we associate its value as the key and its index i as the value in the hash map m.
Iterate and Check for Double Existence: We iterate through the array using the enumerate function which gives us both the index and value.
```
return any(v << 1 in m and m[v << 1] != i for i, v in enumerate(arr))
```
- For each element v, we check if v << 1 (which is equivalent to 2 * v) exists in the hash map m. The << operator is a bit manipulation technique used for efficiency and is the same as multiplying by 2.
- If the double exists (v << 1 in m), we then check if the index corresponding to that doubled value is different from the index of the current value v (m[v << 1] != i). This ensures that i != j.
- The any function is used to check if there's at least one element in the array satisfying this condition. If such an element is found, any will return True, otherwise, it will return False.

In summary, this approach uses a hash map to map each value to its index and then uses list comprehension combined with bit manipulation to check efficiently if there's any element in the array that has a corresponding element that is double its value, while ensuring the indices are distinct.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example array arr = [10, 2, 5, 3] to illustrate the solution approach described above.

Creation of a Hash Map: We initialize an empty hash map, m. Then we iterate over the arr and fill up m with elements from arr as keys and their indices as values. After this step, the hash map looks like this:
```
m = {10: 0, 2: 1, 5: 2, 3: 3}
```
The keys of the hash map m are the values from the array, and the values of the hash map m are their respective indices in the array.
Iterate and Check for Double Existence: We now use a list comprehension to check each element and its double's existence in a single pass. For each element v in the array, we check if 2 * v exists in m:
- Checking for the first element, 10: We see that 10 << 1 (which is 20) is not present in m. So we move to the next element.
- Checking for the second element, 2: 2 << 1 is 4 and is similarly not present in m.
- Checking for the third element, 5: 5 << 1 is 10, and it is present in m with an index of 0. Since the current index 2 is not the same as 0, we have found our i and j (i=2, j=0) which satisfies arr[i] == 2 * arr[j].
There is no need to check the fourth element, 3, as we have already found a valid pair. However, if we did, we'd see that 3 << 1 (which is 6) is not present in m.

According to the list comprehension, it would return True after finding the valid pair for the element 5. This confirms that such a pair with the specified criteria exists in the array.

In conclusion, for our example array arr = [10, 2, 5, 3], the function implementing the solution approach would return True, indicating that the array contains at least one pair of indices fitting the problem's requirements.

Solution Implementation

1from typing import List
2
3class Solution:
4    def checkIfExist(self, arr: List[int]) -> bool:
5        # Create a dictionary to hold values as keys and their indices as values.
6        value_to_index_map = {value: index for index, value in enumerate(arr)}
7      
8        # Iterate through each value in the array.
9        for index, value in enumerate(arr):
10            # Check if there is a value that is double the current value
11            # and ensure that it is not the same instance as the current value.
12            if (value * 2 in value_to_index_map) and (value_to_index_map[value * 2] != index):
13                return True  # We found a pair where one value is double the other.
14      
15        # Return False if no pairs were found where one value is double the other.
16        return False
17

1class Solution {
2  
3    // Checks if the array contains any duplicate elements where one element 
4    // is twice as much as another element
5    public boolean checkIfExist(int[] arr) {
6      
7        // Create a HashMap to store the array elements with their corresponding index.
8        Map<Integer, Integer> elementToIndexMap = new HashMap<>();
9      
10        // Get the length of the array to iterate
11        int length = arr.length;
12      
13        // Populate the HashMap with array elements as keys and their indices as values
14        for (int index = 0; index < length; ++index) {
15            elementToIndexMap.put(arr[index], index);
16        }
17      
18        // Iterate over the array to find a duplicate where one number is double the other
19        for (int index = 0; index < length; ++index) {
20            // Calculate the double of the current element
21            int doubleValue = arr[index] * 2;
22
23            // Check if the double of this number exists in the map and it's not the number itself
24            if (elementToIndexMap.containsKey(doubleValue) && elementToIndexMap.get(doubleValue) != index) {
25                return true; // Found the pair where one is double the other
26            }
27        }
28      
29        // If no such pair exists, return false
30        return false;
31    }
32}
33

1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7    // Function to check if there exists any index i such that arr[i] is equal to 2 * arr[j], where i and j are different.
8    bool checkIfExist(vector<int>& arr) {
9        unordered_map<int, int> indexMap; // Create a hash map to store the value to index mapping.
10        int size = arr.size(); // Get the size of the array.
11      
12        // Fill the hash map with elements from the array as keys and their indices as values.
13        for (int i = 0; i < size; ++i) {
14            indexMap[arr[i]] = i;
15        }
16      
17        // Iterate through the array to check if there's an element such that it's double exists and is not at the same index.
18        for (int i = 0; i < size; ++i) {
19            // Check if there is an element in the array which is double the current element and not at the same index.
20            if (indexMap.count(arr[i] * 2) && indexMap[arr[i] * 2] != i) {
21                return true; // If such an element is found, return true.
22            }
23        }
24      
25        return false; // If no such element is found, return false.
26    }
27};
28

1// Function to check if the array contains any element such that 
2// an element is double another element in the array.
3function checkIfExist(arr: number[]): boolean {
4    // Create a Set to keep track of the elements we've seen so far.
5    const seenElements = new Set<number>();
6
7    // Iterate over each value in the array.
8    for (const value of arr) {
9        // Check if we've seen an element that is double the current value
10        // or if we've seen an element that is half the current value.
11        if (seenElements.has(value * 2) || (value % 2 === 0 && seenElements.has(value / 2))) {
12            // If such an element exists, return true.
13            return true;
14        }
15        // Add the current value to the set of seen elements.
16        seenElements.add(value);
17    }
18
19    // If no such pair is found, return false.
20    return false;
21}
22

Time and Space Complexity

Time Complexity

The time complexity of the code is O(N), where N is the length of the array arr. This is because the code consists of two operations that scale linearly with the size of the input:

Creating a dictionary m with array values as keys and their indices as values involves a single pass through all elements in the array.
Then, an any function is used with a generator expression which may traverse up to all elements again to check the condition for each element.

However, the condition v << 1 in m is checked against the dictionary's keys which is an O(1) operation on average due to the hash table implementation of Python dictionaries. Therefore, despite the double pass, each individual check is constant time, resulting in an overall linear time complexity.

Space Complexity

The space complexity of the code is also O(N), as a dictionary m of size proportional to the input array is constructed. This dictionary stores each element and its respective index from the arr, and thus requires space that grows linearly with the number of elements in the array.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: