LeetCode 1346 - Check If N and Its Double Exist

The problem gives an integer array arr and asks whether there exist two different indices i and j such that: In simpler

leetcodeeasyarrayhash-tabletwo-pointersbinary-searchsorting

LeetCode Problem 1346

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Two Pointers, Binary Search, Sorting

Solution

Problem Understanding

The problem gives an integer array arr and asks whether there exist two different indices i and j such that:

arr[i] == 2 * arr[j]

In simpler terms, we need to determine whether one number in the array is exactly double another number in the same array.

The indices must be different, meaning we cannot use the same element twice unless it appears multiple times in the array. For example, if the array contains two zeroes, then one zero can be considered the double of the other because:

0 == 2 * 0

The input is an array of integers, which may include:

  • Positive numbers
  • Negative numbers
  • Zero

The expected output is a boolean:

  • true if such a pair exists
  • false otherwise

The constraints are relatively small:

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

Since the array size is at most 500, even an O(n^2) brute-force solution is acceptable in practice. However, the problem is designed to encourage recognizing a more efficient lookup-based approach using a hash set.

Several edge cases are important:

  • Arrays containing zeroes, especially multiple zeroes
  • Negative numbers, because doubling negative values is still valid
  • Duplicate values
  • Very small arrays of size 2
  • Cases where the double appears before the original value

A naive implementation can easily mishandle zero or assume the smaller value always appears first.

Approaches

Brute Force Approach

The most direct solution is to compare every pair of indices (i, j) where i != j.

For each pair, we check:

arr[i] == 2 * arr[j]

If we ever find a valid pair, we immediately return true. If all pairs are checked and none satisfy the condition, we return false.

This approach is correct because it exhaustively examines every possible combination of two different elements. Since the problem only asks whether at least one valid pair exists, a complete search guarantees correctness.

However, this method requires nested loops, resulting in quadratic time complexity. While the constraints are small enough that this still works, it is not the most efficient approach.

Optimal Hash Set Approach

The key observation is that for each number x, we only need to know whether:

  • 2 * x already exists
  • x / 2 already exists, when x is even

A hash set allows constant-time average lookup operations.

As we iterate through the array, we store previously seen numbers in a set. For each current number:

  • If its double already exists in the set, we found a valid pair
  • If it is even and its half already exists in the set, we also found a valid pair

This works because the relationship can appear in either order inside the array. The larger value may appear before the smaller value, or vice versa.

Using a hash set reduces the time complexity from O(n^2) to O(n) on average.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Compare every pair of elements
Optimal O(n) O(n) Uses a hash set for constant-time lookups

Algorithm Walkthrough

  1. Create an empty hash set called seen.

The set will store numbers we have already processed. A hash set is chosen because it provides average O(1) lookup time. 2. Iterate through each number num in the array.

We process elements one at a time and check whether a matching value has already appeared earlier. 3. Check whether num * 2 exists in the set.

If it does, then we previously encountered a number whose double is the current value relationship. 4. Check whether num is even and whether num // 2 exists in the set.

This handles the reverse ordering case where the smaller number appeared earlier. We only check halves for even numbers because doubling integers always produces even results. 5. If either condition is true, return True.

We have found two distinct elements satisfying the condition. 6. Add the current number to the set.

Future elements can now compare against this value. 7. If the loop finishes without finding a valid pair, return False.

Why it works

The algorithm maintains the invariant that seen contains all previously processed numbers.

For every current number x, a valid pair exists if either:

2 * x

has already appeared, or:

x / 2

has already appeared when x is even.

Because every element is checked exactly once against all previously seen values, every valid pair is eventually detected. Therefore, the algorithm always produces the correct answer.

Python Solution

from typing import List

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        seen = set()

        for num in arr:
            if (num * 2) in seen:
                return True

            if num % 2 == 0 and (num // 2) in seen:
                return True

            seen.add(num)

        return False

The implementation begins by creating an empty set called seen. This set stores all previously processed numbers.

The loop iterates through each element in the array exactly once. For every number, the code performs two checks.

The first check determines whether the double of the current number already exists in the set. This catches cases where the larger value appeared earlier.

The second check determines whether half of the current number already exists. Since only even numbers can be doubles of integers, the code first checks num % 2 == 0.

If either condition succeeds, the function immediately returns True.

If no match is found, the current number is inserted into the set so later elements can compare against it.

If the loop completes without finding any valid pair, the function returns False.

Go Solution

func checkIfExist(arr []int) bool {
    seen := make(map[int]bool)

    for _, num := range arr {
        if seen[num*2] {
            return true
        }

        if num%2 == 0 && seen[num/2] {
            return true
        }

        seen[num] = true
    }

    return false
}

The Go implementation follows the same logic as the Python solution. Since Go does not have a built-in set type, a map of map[int]bool is used to simulate a hash set.

The lookup operations remain constant time on average.

Integer division in Go behaves correctly here because the code only checks num/2 when num is even. Therefore, no fractional values are lost.

There are no special nil-handling requirements because iterating over an empty slice is safe, although the problem guarantees at least two elements.

Worked Examples

Example 1

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

We trace the algorithm step by step.

Current Number Seen Set Before Check Double Check Half Result
10 {} 20 not found 5 not found Add 10
2 {10} 4 not found 1 not found Add 2
5 {10, 2} 10 found not even Return true

When processing 5, the algorithm sees that 10 already exists in the set.

Since:

10 == 2 * 5

the answer is true.

Example 2

Input: arr = [3, 1, 7, 11]
Output: false
Current Number Seen Set Before Check Double Check Half Result
3 {} 6 not found not even Add 3
1 {3} 2 not found not even Add 1
7 {1, 3} 14 not found not even Add 7
11 {1, 3, 7} 22 not found not even Add 11

No valid pair is ever found, so the algorithm returns false.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed once with constant-time set lookups
Space O(n) The hash set may store all array elements

The algorithm performs a single pass through the array. Each iteration performs only constant-time operations: hash lookups and insertions.

In the worst case, no valid pair exists, so every element is stored in the set. Therefore, the space complexity is linear in the size of the input.

Test Cases

solution = Solution()

assert solution.checkIfExist([10, 2, 5, 3]) is True  # basic positive case
assert solution.checkIfExist([3, 1, 7, 11]) is False  # no valid pair

assert solution.checkIfExist([0, 0]) is True  # zero doubled is still zero
assert solution.checkIfExist([-2, -4]) is True  # negative numbers
assert solution.checkIfExist([7, 14]) is True  # direct double relationship
assert solution.checkIfExist([14, 7]) is True  # reverse order relationship

assert solution.checkIfExist([1, 3, 5, 9]) is False  # all odd numbers
assert solution.checkIfExist([1000, -1000]) is False  # extreme values without match

assert solution.checkIfExist([2, 4, 8, 16]) is True  # multiple valid pairs
assert solution.checkIfExist([1, 2]) is True  # minimum size with match
assert solution.checkIfExist([1, 3]) is False  # minimum size without match

assert solution.checkIfExist([-10, -5, 20]) is True  # negative half relationship
assert solution.checkIfExist([6, 3]) is True  # half found later
assert solution.checkIfExist([5, 10]) is True  # double found later

assert solution.checkIfExist([1, 1, 1, 1]) is False  # duplicates without doubling
Test Why
[10, 2, 5, 3] Standard example with valid pair
[3, 1, 7, 11] Standard example with no match
[0, 0] Verifies correct handling of zero
[-2, -4] Ensures negatives work properly
[7, 14] Basic double relationship
[14, 7] Confirms reverse ordering works
[1, 3, 5, 9] No doubles present
[1000, -1000] Boundary values without match
[2, 4, 8, 16] Multiple valid pair possibilities
[1, 2] Smallest valid input with match
[1, 3] Smallest valid input without match
[-10, -5, 20] Negative numbers with valid relationship
[6, 3] Half relationship detected
[5, 10] Double relationship detected
[1, 1, 1, 1] Duplicate values without valid pair

Edge Cases

One important edge case involves zeroes. Since:

0 == 2 * 0

two zeroes form a valid pair. A buggy implementation might accidentally reject this case by preventing comparisons of equal values. The algorithm handles it correctly because the first zero is added to the set, and the second zero immediately detects that its half and double already exist.

Another important edge case involves negative numbers. Some implementations incorrectly assume doubling relationships only apply to positive integers. However:

-4 == 2 * -2

is completely valid. The hash set approach treats negative values exactly the same as positive values, so the logic remains correct without modification.

A third tricky case occurs when the larger number appears before the smaller number. For example:

[10, 5]

If we only checked whether 2 * num existed earlier, we would miss this relationship. The algorithm avoids this problem by also checking whether half of the current even number already exists in the set.

Another subtle case involves duplicate values that are not zero. For example:

[1, 1, 1]

Even though duplicates exist, none of them are doubles of each other. The algorithm correctly returns False because neither the double nor valid half conditions are satisfied.