Check If N and Its Double Exist — Hash Set or Binary Search [LC 1346]

Problem Statement#

Given an integer array arr, check if there exist two indices i and j such that i != j, arr[i] == 2 * arr[j].

Constraints:

• 2 <= arr.length <= 500
• -10^3 <= arr[i] <= 10^3

Input:  arr = [10,2,5,3]
Output: true
Explanation: 10 = 2 * 5

Input:  arr = [3,1,7,11]
Output: false

Why This Problem Matters#

LC 1346 is an easy problem that serves as a warm-up for the two-sum family of problems. It tests whether candidates reach for the O(n) hash set approach over the O(n^2) brute force, and whether they can correctly handle the edge case where the element is zero (zero doubled is zero, requiring two distinct indices).

The binary search alternative (sort + bisect_left per element) demonstrates the "sort one array, search per element" pattern used in harder problems like LC 2300 (Successful Pairs).

The Core Insight#

Hash set (O(n)): Process elements one by one. For each element x, check if 2 * x is already in the set (previous element is half of current) or if x is even and x // 2 is already in the set (current element is double of a previous one). Then add x to the set.

Binary search (O(n log n)): Sort the array. For each element at index i, binary search for 2 * arr[i]. If found at index j != i, return true. Handle zero specially since both 0 * 2 = 0 and 0 / 2 = 0 need distinct indices.

Visual Dry Run#

arr = [10, 2, 5, 3]

Hash set approach:

• x=10: check 20 in {} (no), check 5 in {} (no). Add 10. seen={10}
• x=2: check 4 in {10} (no), check 1 in {10} (no). Add 2. seen={10,2}
• x=5: check 10 in {10,2} (YES!) → return true

Solution (Optimal)#

class Solution:
    def checkIfExist(self, arr: list[int]) -> bool:
        seen = set()
        for x in arr:
            if 2 * x in seen:
                return True
            if x % 2 == 0 and x // 2 in seen:
                return True
            seen.add(x)
        return False

var checkIfExist = function(arr) {
    const seen = new Set();
    for (const x of arr) {
        if (seen.has(2 * x)) return true;
        if (x % 2 === 0 && seen.has(x / 2)) return true;
        seen.add(x);
    }
    return false;
};

Time: O(n) — single pass with O(1) set lookups Space: O(n) — hash set stores up to n elements

Binary search approach (O(n log n) time, O(1) extra space):

import bisect
 
def checkIfExist(arr):
    arr.sort()
    n = len(arr)
    for i, x in enumerate(arr):
        target = 2 * x
        j = bisect.bisect_left(arr, target)
        if j < n and arr[j] == target and j != i:
            return True
    return False

var checkIfExist = function(arr) {
    arr.sort((a, b) => a - b);
    const n = arr.length;
 
    for (let i = 0; i < n; i++) {
        const target = 2 * arr[i];
        let lo = 0, hi = n - 1;
        while (lo <= hi) {
            const mid = lo + Math.floor((hi - lo) / 2);
            if (arr[mid] === target) {
                if (mid !== i) return true;
                // Found but same index — could be duplicate (e.g., [0,0])
                // Check adjacent elements
                if (mid > 0 && arr[mid - 1] === target) return true;
                if (mid < n - 1 && arr[mid + 1] === target) return true;
                break;
            } else if (arr[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return false;
};

Common Mistakes#

• Not handling zero: 0 * 2 = 0. If there are two zeros in the array, the answer is true. With a single zero, 2 * 0 = 0 would match 0 itself — need j != i.
• In the binary search version: finding the target but not checking j != i — you might find the element itself.
• Not sorting before binary search — binary search requires sorted input.
• Using a single condition 2*x in seen — this only checks the forward direction (current is half). Also need x/2 in seen for the backward direction.

Interview Tips#

• State the hash set approach first — it is O(n) and simpler.
• Mention the binary search alternative if the interviewer wants O(1) extra space (ignoring input modification).
• Handle zero explicitly when discussing the algorithm — it is the most common edge case in this problem.
• This is a two-sum variant: "does a pair (x, 2x) exist?" — recognise the family.

Follow-up Questions#

• What if you want all pairs? Collect all valid pairs instead of returning on the first one.
• Two Sum (LC 1): Does any pair sum to target? Same hash set pattern.
• LC 2300 (Successful Pairs): For each spell, count potions that multiply above success. Sort potions, binary search per spell — the pattern applied to counts.
• What about negative numbers? The hash set approach handles negatives correctly (e.g., -4 and -2: 2 * (-2) = -4 or -4 / 2 = -2).

Key Takeaways#

• LC 1346 has two valid approaches: O(n) hash set (preferred) and O(n log n) sort + binary search (preferred when O(1) space is required).
• Hash set: for each x, check 2*x and (if x is even) x//2 in previously seen elements — handles both directions.
• Binary search: sort the array, then for each element find 2 * arr[i]; verify the found index is different from the search index.
• Zero is the critical edge case: 0 * 2 = 0, so two zeros make the answer true but one zero does not — the j != i check handles this.
• The hash set approach builds the set incrementally, so it automatically avoids matching an element with itself in the equal-zero case.
• Amazon and Microsoft ask this as a warm-up to verify two-sum pattern recognition and edge-case handling.
• This pattern — "check if a transformed version of each element exists" — generalises to LC 560, LC 2300, and many other search-in-array problems.