Check If N and Its Double Exist solution and explanation
Google
9 more videos on this problem
Check If N and Its Double Exist | Special Motivation | Leetcode 1346 | codestorywithMIKcodestorywithMIK · 14:57 · 5K views
Check If N and Its Double Exist | Leetcode 1346Techdose · 6:04 · 2K views
1346. Check If N and Its Double Exist | shashcode30 | java | dsa | leetcode daily challengeShashCode · 10:48 · 1K views
1346. Check If N and Its Double Exist | Interview Preparation | English | code iocode io - English · 8:35 · 1K views
LeetCode 1346: Check If N and Its Double Exist (Go)devtopics · 10:07 · 1K views
GOOGLE INTERVIEW QUESTION | Check if N and Its Double Exist (LeetCode problem 1346)MCCOMP · 5:35 · 883 views
LeetCode - 1346 Check If N and Its Double Exist | Arrays CardAditya Mahajan · 4:42 · 809 views
CHECK IF N AND ITS DOUBLE EXIST | LEETCODE 1346 | PYTHON DICTIONARY SOLUTIONCracking FAANG · 4:23 · 781 views
Leetocode 1346. Check If N and Its Double Exist (Solution + Explanation)ultcode · 3:05 · 730 views
LeetCode Problem 1346. Check If N and Its Double Exist || Java Solution WalkthroughUnknown Koder · 7:23 · 610 views
The problem
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.
def checkIfExist(arr):
seen = set()
for num in arr:
if 2 * num in seen or (num % 2 == 0 and num // 2 in seen):
return True
seen.add(num)
return Falseimport java.util.HashSet;
public class Solution {
public boolean checkIfExist(int[] arr) {
HashSet<Integer> set = new HashSet<>();
for (int num : arr) {
if (set.contains(2 * num) || (num % 2 == 0 && set.contains(num / 2))) {
return true;
}
set.add(num);
}
return false;
}
}#include <unordered_set>
#include <vector>
using namespace std;
bool checkIfExist(vector<int>& arr) {
unordered_set<int> seen;
for (int num : arr) {
if (seen.count(2 * num) || (num % 2 == 0 && seen.count(num / 2))) {
return true;
}
seen.insert(num);
}
return false;
}var checkIfExist = function(arr) {
const seen = new Set();
for (let num of arr) {
if (seen.has(2 * num) || (num % 2 === 0 && seen.has(num / 2))) {
return true;
}
seen.add(num);
}
return false;
};#include <stdbool.h>
#include <stdlib.h>
bool checkIfExist(int* arr, int arrSize) {
bool *hashMap = (bool*)calloc(2001, sizeof(bool)); // Hash set to store the presence of numbers
for (int i = 0; i < arrSize; i++) {
if (arr[i] >= -1000 && arr[i] <= 1000) {
if (arr[i] % 2 == 0 && hashMap[(arr[i] / 2) + 1000]) {
free(hashMap);
return true;
}
if (hashMap[(arr[i] * 2) + 1000]) {
free(hashMap);
return true;
}
hashMap[arr[i] + 1000] = true;
}
}
free(hashMap);
return false;
}using System.Collections.Generic;
public class Solution {
public bool CheckIfExist(int[] arr) {
HashSet<int> seen = new HashSet<int>();
foreach (int num in arr) {
if (seen.Contains(2 * num) || (num % 2 == 0 && seen.Contains(num / 2))) {
return true;
}
seen.Add(num);
}
return false;
}
}The Python solution employs a set to track numbers that have been visited. For each number, we check if its double or its half (provided the number is even) is already in the set.
Time Complexity: O(n), due to the single traversal and set operations.
Space Complexity: O(n) for the set storing elements.
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.
def checkIfExist(arr):
arr.sort()
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[j] > 2 * arr[i]:
break
if arr[j] == 2 * arr[i] or arr[i] == 2 * arr[j]:
return True
return Falseimport java.util.Arrays;
public class Solution {
public boolean checkIfExist(int[] arr) {
Arrays.sort(arr);
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length && arr[j] <= 2 * arr[i]; j++) {
if (arr[j] == 2 * arr[i] || arr[i] == 2 * arr[j]) {
return true;
}
}
}
return false;
}
}#include <vector>
#include <algorithm>
using namespace std;
bool checkIfExist(vector<int>& arr) {
sort(arr.begin(), arr.end());
for (int i = 0; i < arr.size(); i++) {
for (int j = i + 1; j < arr.size() && arr[j] <= 2 * arr[i]; j++) {
if (arr[j] == 2 * arr[i] || arr[i] == 2 * arr[j]) {
return true;
}
}
}
return false;
}var checkIfExist = function(arr) {
arr.sort((a, b) => a - b);
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length && arr[j] <= 2 * arr[i]; j++) {
if (arr[j] == 2 * arr[i] || arr[i] == 2 * arr[j]) {
return true;
}
}
}
return false;
};#include <stdbool.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)a) - (*(int*)b);
}
bool checkIfExist(int* arr, int arrSize) {
qsort(arr, arrSize, sizeof(int), compare);
for (int i = 0; i < arrSize; i++) {
for (int j = i + 1; j < arrSize && arr[j] <= 2 * arr[i]; j++) {
if (arr[j] == 2 * arr[i] || arr[i] == 2 * arr[j]) {
return true;
}
}
}
return false;
}using System;
public class Solution {
public bool CheckIfExist(int[] arr) {
Array.Sort(arr);
for (int i = 0; i < arr.Length; i++) {
for (int j = i + 1; j < arr.Length && arr[j] <= 2 * arr[i]; j++) {
if (arr[j] == 2 * arr[i] || arr[i] == 2 * arr[j]) {
return true;
}
}
}
return false;
}
}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.
Time Complexity: O(n log n) due to sorting and O(n^2) in the worst-case check.
Space Complexity: O(1) for in-place sorting.
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.
function checkIfExist(arr: number[]): boolean {
const s: Set<number> = new Set();
for (const x of arr) {
if (s.has(x * 2) || (x % 2 === 0 && s.has((x / 2) | 0))) {
return true;
}
s.add(x);
}
return false;
}func checkIfExist(arr []int) bool {
s := map[int]bool{}
for _, x := range arr {
if s[x*2] || (x%2 == 0 && s[x/2]) {
return true
}
s[x] = true
}
return false
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using a Hash Set | Time Complexity: O(n), due to the single traversal and set operations. |
| Approach 2: Sorting and Two Pointers | Time Complexity: O(n log n) due to sorting and O(n^2) in the worst-case check. |
| Hash Table | – |
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 |
Frequently asked questions
Is Check If N and Its Double Exist easy or hard?
LeetCode classifies this problem as Easy. The main skill tested is recognizing that a pair relationship can be detected with a hash set instead of checking every pair, reducing the complexity from O(n^2) to O(n).
Check If N and Its Double Exist Python/Java solution
Python solutions typically use a built-in set for O(1) lookups, while Java implementations use HashSet<Integer>. Both follow the same logic: iterate through the array, check for double or half in the set, and insert the current value.
How to solve Check If N and Its Double Exist in O(n)?
Traverse the array while storing seen numbers in a hash set. For each value x, check if 2*x exists in the set or if x is even and x/2 exists. If either condition is true, a valid pair has been found. Insert x into the set and continue scanning.
What is the best approach for Check If N and Its Double Exist?
The most efficient approach uses a hash set. Iterate through the array and check whether 2*x or x/2 already exists in the set before inserting the current number. Each lookup is O(1), so the overall time complexity becomes O(n) with O(n) extra space.
Is Check If N and Its Double Exist asked at Google/Amazon/Meta?
Problems involving hash sets, array scanning, and pair relationships appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying pattern of using hash-based lookups to detect relationships between numbers is commonly tested.
What data structure is used in Check If N and Its Double Exist?
The primary data structure is a hash set (or hash table). It allows constant-time membership checks, which makes it possible to detect whether the required double or half value already appeared in the array.
What is the time complexity of Check If N and Its Double Exist?
The optimal solution runs in O(n) time using a hash set for constant‑time lookups. A sorting-based approach takes O(n log n) time due to the sort operation, while a naive brute force solution that checks every pair would take O(n^2).