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] <= 103Problem Overview: Given an integer array arr, determine whether there exist two indices i and j such that i != j and arr[i] == 2 * arr[j]. In simpler terms, check if any number in the array has its double also present.
The challenge is not the comparison itself but doing it efficiently. A naive solution checks every pair, which quickly becomes slow as the array grows. Efficient solutions rely on fast lookups or ordering the array to detect the relationship between values.
Approach 1: Using a Hash Set (O(n) time, O(n) space)
This approach scans the array once while storing previously seen numbers in a hash set. For each element x, check whether 2 * x or x / 2 already exists in the set. The key insight is that if either of those values has appeared earlier, the required pair exists immediately. Hash lookups run in constant time, so each iteration performs a few O(1) checks and inserts.
This method works for any unsorted array and handles negative numbers and zero correctly. The special case with 0 is naturally handled because the set check detects a second zero. Since the algorithm processes each element once and performs constant-time operations, the total runtime is O(n) with O(n) extra space for the set. This approach heavily relies on fast membership checks provided by a hash table and is the most practical solution in interviews.
Approach 2: Sorting and Two Pointers (O(n log n) time, O(1) extra space)
Another strategy first sorts the array, then searches for pairs where one value equals double the other. After sorting, you can use a pointer for each number and apply binary search or a two‑pointer technique to locate 2 * arr[i]. Sorting ensures the numbers are ordered, which makes these searches efficient.
A common implementation sorts the array and, for each index, performs a binary search for its double. Sorting costs O(n log n), and each lookup costs O(log n). Another variation moves two pointers through the sorted list to maintain the doubling relationship. Both approaches leverage ordering provided by sorting and pointer movement similar to patterns used in two pointers problems.
The advantage of this approach is lower auxiliary memory usage because the algorithm works directly on the sorted array. The tradeoff is slower runtime compared with the hash set method due to the initial sort.
Recommended for interviews: The hash set solution is typically expected. It demonstrates that you recognize the pattern of converting a pair-search problem into constant-time lookups using a hash structure. Discussing the sorting approach still helps because it shows awareness of alternative strategies and space–time tradeoffs. Strong candidates often mention the brute force O(n²) idea briefly, then move quickly to the O(n) hash-based optimization.
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.
This C solution allocates a fixed-size boolean array to act as a hash set for values that have been seen. For each number, it checks if twice the number or half (if even) exists by using offset indexing for negative values.
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.
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.
This C code sorts the array and then uses a nested loop to check for any two elements where one is twice the other, leveraging the sorted order to avoid unnecessary comparisons.
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.
We define a hash table s to record the elements that have been visited.
Traverse the array arr. For each element x, if either double of x or half of x is in the hash table s, then return true. Otherwise, add x to the hash table s.
If no element satisfying the condition is found after the traversal, return false.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array arr.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Using a Hash Set | Time Complexity: O(n), because we iterate through the array once and do constant time operations for each element. |
| Approach 2: Sorting and Two Pointers | Time Complexity: O(n log n) for sorting, then O(n^2) for the two-pointer search. |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Set Lookup | O(n) | O(n) | Best general solution for unsorted arrays and typical interview expectations |
| Sorting + Two Pointers / Binary Search | O(n log n) | O(1) extra | Useful when minimizing additional memory or when the array is already sorted |
Check If N and Its Double Exist | Special Motivation | Leetcode 1346 | codestorywithMIK • codestorywithMIK • 5,101 views views
Watch 9 more video solutions →Practice Check If N and Its Double Exist with our built-in code editor and test cases.
Practice on FleetCode