Check If N and Its Double Exist: Hash Set Lookup

1346. Check If N and Its Double Exist asks you a simple question: given an array of integers arr, is there any pair of indices i and j such that arr[i] == 2 * arr[j] and i != j? In other words, does the array contain some number along with its double?

The problem is easy to state, but the way you solve it reveals whether you know how to use a hash set for fast lookups. Let's look at two examples.

Brute force: check every pair

The most direct approach: for every element, scan the rest of the array looking for its double (or its half). Two nested loops get the job done.

def check_if_exist(arr: list[int]) -> bool:
    for i in range(len(arr)):
        for j in range(len(arr)):
            if i != j and arr[i] == 2 * arr[j]:
                return True
    return False

This works, but it runs in O(n^2) time. For small inputs that is fine, but we can do better.

Hash set approach

Here is the key insight: for each element x, you only need to know two things. Is 2 * x already in the set of numbers you have seen? Or, if x is even, is x / 2 in the set? If either check hits, you have found a valid pair. If neither hits, add x to the set and move on.

One pass. One O(1) lookup per element. O(n) total.

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

Why do we check both 2 * x and x // 2? Because the matching element could appear before or after x in the array. If x comes first, we will not find 2 * x in the set yet, but later when 2 * x arrives, it will find x via the x // 2 path. By checking both directions, we catch the pair no matter which element we encounter first.

Step-by-step walkthrough

Let's trace through [10, 2, 5, 3] to see exactly how the hash set solution works.

At step 3, we check whether 2 * 5 = 10 is in the set, and it is. That means 10 = 2 * 5, so we return True. We never even look at the last element.

Alternative: sort + binary search

If you want to avoid extra space, you can sort the array first and then use binary search to find the double of each element.

import bisect

def check_if_exist(arr: list[int]) -> bool:
    arr.sort()
    for i, x in enumerate(arr):
        target = 2 * x
        j = bisect.bisect_left(arr, target)
        if j < len(arr) and arr[j] == target and j != i:
            return True
    return False

After sorting in O(n log n), each binary search takes O(log n), and we do n of them. Total time is O(n log n). This uses O(1) extra space (ignoring the sort), which can matter in constrained environments.

The tricky part with this approach is making sure j != i. If x is 0, then target is also 0, and binary search might land on the same index. You need to verify you found a different element.

Complexity analysis

The hash set approach wins on time. The sort + binary search approach saves memory. For interviews, the hash set version is usually what they want to see.

Building blocks

This problem exercises two reusable patterns:

1. Hash set for complement lookup

The idea of computing a "target" value from the current element and checking whether you have seen it before. This is the same technique behind Two Sum (where you look for target - x), Contains Duplicate (where you look for x itself), and many other problems. Any time you need to ask "have I already seen a value that pairs with the current one?", a hash set or hash map is your tool.

2. Binary search on a sorted array

When the data is sorted, binary search lets you find (or rule out) a target in O(log n) time. This building block shows up in problems like Two Sum II, Binary Search, and any problem where you can reduce a search to a sorted range.

Edge cases

Zeros. If the array contains [0, 0], the answer is True because 0 = 2 * 0, and the two zeros are at different indices. The hash set approach handles this correctly: when we reach the second 0, we check if 2 * 0 = 0 is in the set, and it is (we added the first 0 already).

Negative numbers. Negative values work fine. If the array has -3 and -6, then -6 = 2 * (-3). The arithmetic and set lookups are the same. Just remember that checking x % 2 == 0 before doing x // 2 prevents you from checking non-integer halves of odd numbers.

Single element. An array with one element can never have a valid pair, since i != j is required. The loop simply finishes without returning True.

From understanding to recall

This problem feels almost too easy once you see the hash set trick. "Of course you check for 2 * x and x / 2 in a set." But the real skill is reaching for that pattern the moment you see a problem that asks "does a complement exist?" Three weeks from now, when a harder problem uses the same structure, you want the hash set complement lookup to fire automatically.

That takes practice, not just reading. You drill the pattern at increasing intervals until the code comes from muscle memory, not from re-reading a blog post.

Related posts

• Two Sum - The classic complement lookup problem using a hash map
• Contains Duplicate - The simplest hash set membership check
• Two Sum II - Two pointers on a sorted array instead of a hash map