#1346

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Check If N and Its Double Exist

Solve Check If N and Its Double Exist by scanning once and checking doubles or halves in a hash set.

array hash table two pointers binary search sorting

Problem Statement

You are given an integer array and need to decide whether two different positions form the relation where one value is exactly twice the other. The task is not to return the pair, only to report whether such indices exist anywhere in the array. For example, in arr = [10,2,5,3], the answer is true because 10 is double 5 at a different index.

A second example shows the opposite case: arr = [3,1,7,11] returns false because no value is paired with its double anywhere else in the array. The input size is small enough for brute force to pass, but the intended pattern is faster: scan the array, remember earlier numbers, and detect a matching double or half as soon as it appears.

Examples

Example 1

Input: arr = [10,2,5,3]

Output: true

For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

Example 2

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

Output: false

There is no i and j that satisfy the conditions.

Constraints

2 <= arr.length <= 500
-103 <= arr[i] <= 103

Solution Approach

Use a seen set while scanning left to right

The core pattern for Check If N and Its Double Exist is array scanning plus hash lookup. As you iterate through arr, maintain a hash set containing values from earlier indices only. For the current number x, you want to know whether some previous value is x * 2 or whether x itself is double some previous value, which means x must be even and x / 2 must already be present.

Why checking both directions matters

Only checking whether 2 * x exists in the seen set misses cases like arr = [10,2,5,3], where 10 appears before 5. When you reach 5, you must detect that 10 was already seen. Likewise, when you reach a larger even number, checking x / 2 catches cases where the smaller value appeared first. This symmetric lookup is the exact failure mode that trips up one-sided implementations.

Stop immediately when a valid pair appears

At each index, do the lookups before inserting the current value into the set. That order prevents accidentally pairing a number with itself at the same index, which matters especially for 0 because 0 is double 0 only if there are two zero entries. If either lookup succeeds, return true immediately. If the loop finishes with no match, return false.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The hash set approach runs in O(n) time because each array element is processed once and each lookup is O(1) on average. It uses O(n) space in the worst case to store previously seen values. This is better than the O(n^2) nested-loop check and simpler than sorting-based variants that add ordering work for a problem that only needs existence.

What Interviewers Usually Probe

They mention storing values from indices [0, i - 1] while scanning, which points directly to a seen-set solution.
They ask how to avoid comparing every pair, which usually means replace brute force with O(1) membership checks.
They emphasize different indices i and j, which is a clue to check before inserting the current value into the hash set.

Common Pitfalls or Variants

Common pitfalls

Checking only one direction, such as whether 2 * x was seen, misses pairs where the larger number appears earlier.
Forgetting the even-number guard before checking x / 2 can create incorrect matches for odd values.
Adding the current number to the set before lookup can falsely treat one element as both sides of the pair, especially around 0.

Follow-up variants

Sort the array and use binary search for each value, but the logic becomes less direct than the hash lookup pattern.
Use a frequency map if you also want to reason explicitly about duplicates like two zeroes.
Return the actual index pair instead of a boolean, which requires storing positions rather than only seen values.

FAQ

What is the best pattern for Check If N and Its Double Exist?

The best pattern is a single pass with a hash set of previously seen numbers. For each value x, check whether 2 * x is already seen or whether x is even and x / 2 is already seen.

Why is the hash set solution better than sorting here?

Sorting can work, but it adds extra work to a problem that only asks whether any valid pair exists. The hash set scan matches the condition directly and finishes in linear time on average.

Why do we check before inserting the current number?

That preserves the requirement that the two values come from different indices. It also avoids incorrect self-matching when the current value could satisfy the relation with itself, especially for 0.

Do we really need to check x / 2 as well as 2 * x?

Yes, because the array order is arbitrary. In arr = [10,2,5,3], the larger value 10 appears before 5, so checking only doubles would miss the valid pair.

How should I think about the zero case in this problem?

Zero only forms a valid answer when there are at least two zeroes at different indices. The check-before-insert order handles this cleanly because the second zero will find the first one already in the set.

terminal

Solution

Solution 1: Hash Table

We define a hash table $s$ to record the elements that have been visited.

1

2

3

4

5

6

7

8

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

Continue Practicing

#1782 count pairs of nodes #532 k diff pairs in an array #350 intersection of two arrays ii