1346. Check If N and Its Double Exist
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
andj
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 indexj
(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 with2 * arr[i]
in the hash mapm
is different fromi
. - 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 thearr
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
inarr
, we associate its value as the key and its indexi
as the value in the hash mapm
. -
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 ifv << 1
(which is equivalent to2 * v
) exists in the hash mapm
. 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 valuev
(m[v << 1] != i
). This ensures thati != 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 returnTrue
, otherwise, it will returnFalse
.
- For each element
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 EvaluatorExample 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 thearr
and fill upm
with elements fromarr
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 mapm
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 if2 * v
exists inm
:- Checking for the first element,
10
: We see that10 << 1
(which is20
) is not present inm
. So we move to the next element. - Checking for the second element,
2
:2 << 1
is4
and is similarly not present inm
. - Checking for the third element,
5
:5 << 1
is10
, and it is present inm
with an index of0
. Since the current index2
is not the same as0
, we have found ouri
andj
(i=2, j=0) which satisfiesarr[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 that3 << 1
(which is6
) is not present inm
. - Checking for the first element,
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.
A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Want a Structured Path to Master System Design Too? Donāt Miss This!