Check If N and Its Double Exist - Solution & Explanation
Problem Statement
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] <= 103
Approach Overview
Problem 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.
Approach 1: Approach 1: Using a Hash Set
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.
Complexity
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.
Approach 2: Approach 2: Sorting and Two Pointers
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.
Complexity
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.
Approach 3: Hash Table
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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Check If N and Its Double Exist | Special Motivation | Leetcode 1346 | codestorywithMIK • codestorywithMIK • 5,297 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Check If N and Its Double Exist easy or hard?
Check If N and Its Double Exist Python/Java solution
How to solve Check If N and Its Double Exist in O(n)?
What is the best approach for Check If N and Its Double Exist?
Is Check If N and Its Double Exist asked at Google/Amazon/Meta?
What data structure is used in Check If N and Its Double Exist?
What is the time complexity of Check If N and Its Double Exist?
Ready to solve this problem?
Practice Check If N and Its Double Exist with our built-in code editor and test cases.
Practice on FleetCode