Given an array arr of integers, check if there exist two indices i and j such that :
i != j0 <= i, j < arr.lengtharr[i] == 2 * arr[j]Example 1:
Input: arr = [10,2,5,3] Output: true Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]
Example 2:
Input: arr = [3,1,7,11] Output: false Explanation: There is no i and j that satisfy the conditions.
Constraints:
2 <= arr.length <= 500-103 <= arr[i] <= 103The goal of #1346 Check If N and Its Double Exist is to determine whether an array contains two integers N and 2 * N. A straightforward idea is to check every pair of numbers, but that leads to unnecessary comparisons and poor performance for large arrays.
A more efficient strategy uses a Hash Set. As you iterate through the array, store previously seen values and check whether the current number's double or half already exists in the set. This allows constant-time lookups and avoids nested loops.
Another possible method is to sort the array and use techniques like binary search or two pointers to look for the required relationship between elements. Sorting introduces an extra cost but still keeps the solution efficient.
The hash-based approach typically achieves O(n) time complexity with O(n) additional space, making it the most practical method for interview settings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Set lookup | O(n) | O(n) |
| Sorting + Binary Search | O(n log n) | O(1) to O(n) |
Techdose
Use these hints if you're stuck. Try solving on your own first.
Loop from i = 0 to arr.length, maintaining in a hashTable the array elements from [0, i - 1].
On each step of the loop check if we have seen the element <code>2 * arr[i]</code> so far.
Also check if we have seen <code>arr[i] / 2</code> in case <code>arr[i] % 2 == 0</code>.
This approach uses a Hash Set to store elements as we iterate through the array. For each element, we check if its double or half (only if it's even) exists in the set. This allows for efficient lookup and insertion operations.
Time Complexity: O(n), because we iterate through the array once and do constant time operations for each element.
Space Complexity: O(1), since the hash set size is fixed regardless of input size.
1var checkIfExist = function(arr) {
2 const seen = new Set();
3 for (let num of arr) {
4This JavaScript solution uses a Set to store numbers as they are encountered. For each number, it checks if twice the number or half if the number is even is in the set.
This approach involves sorting the array first. Once sorted, we can use two pointers to find if there exist indices i and j such that one element is twice the other. Sorting helps to systematically check this condition.
Time Complexity: O(n log n) for sorting, then O(n^2) for the two-pointer search.
Space Complexity: O(1) as it sorts in place.
1Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, you can sort the array and then use binary search to check whether double the current value exists. While this approach works, it increases the time complexity to O(n log n) due to the sorting step.
Yes, this type of array and hash-table problem is common in technical interviews. It tests a candidate's ability to optimize from brute-force solutions to efficient hash-based approaches.
A hash set is the most effective data structure for this problem. It allows fast membership checks while iterating through the array, which helps quickly determine whether a number or its double has already appeared.
The optimal approach uses a hash set to track numbers seen so far. For each element, you check whether its double or half already exists in the set. This enables constant-time lookups and results in an overall O(n) time complexity.
This Python solution sorts the array and uses a nested loop to efficiently check conditions, terminating early when further comparisons are unnecessary due to the sorted order.