Problem Description

You are given an array arr of integers. Your task is to check if there exist two different indices i and j in the array such that the value at index i is exactly double the value at index j.

In other words, you need to find if there are two elements in the array where one element is twice the value of another element. The two elements must be at different positions in the array (i.e., i != j).

The conditions that must be satisfied are:

• The indices i and j must be different (i != j)
• Both indices must be valid within the array bounds (0 <= i, j < arr.length)
• The relationship between the values must be: arr[i] == 2 * arr[j]

For example:

• If arr = [10, 2, 5, 3], the function should return true because 10 = 2 * 5
• If arr = [3, 1, 7, 11], the function should return false because no element is double of another

The solution uses a hash table to efficiently track elements we've already seen. As we traverse the array, for each element x, we check if either 2 * x (double of current element) or x / 2 (half of current element, when x is even) exists in our hash table. If either condition is met, we've found our pair and return true. Otherwise, we add the current element to the hash table and continue. If we finish traversing without finding such a pair, we return false.

Intuition

The key insight is that for any element x in the array, we need to find if there exists another element that is either 2 * x or x / 2. This is a classic "pair finding" problem where we need to check if a specific relationship exists between two elements.

The brute force approach would be to use two nested loops to check every pair of elements, which would take O(n²) time. However, we can optimize this by recognizing that as we traverse the array, we only need to check if the "matching" element for the current element has already been seen.

Think of it this way: when we encounter an element x, there are only two possibilities for it to form a valid pair:

1. It could be the smaller element in the pair, meaning we need to find 2 * x somewhere else
2. It could be the larger element in the pair, meaning we need to find x / 2 somewhere else

By using a hash table to store elements we've already processed, we can check in O(1) time whether the required counterpart exists. As we iterate through the array:

• For each element x, we check if 2 * x exists in our hash table (checking if x is the smaller element of a pair)
• We also check if x / 2 exists in our hash table, but only when x is even (checking if x is the larger element of a pair)
• If either condition is true, we've found our answer
• If not, we add x to the hash table for future elements to check against

This approach reduces the time complexity from O(n²) to O(n) by trading space for time, using O(n) additional space for the hash table.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Solution Approach

We implement the solution using a hash table to track elements we've already visited while traversing the array.

Algorithm Steps:

1. Initialize an empty hash set s to store the elements we've seen so far.

2. Iterate through each element x in the array arr:

   • Check if x * 2 exists in the hash set s (this checks if the current element can be the smaller element in a valid pair)
   • Check if x // 2 exists in the hash set s, but only when x % 2 == 0 (this checks if the current element can be the larger element in a valid pair, and we only check when x is even because odd numbers don't have integer halves)
   • If either condition is true, immediately return True as we've found a valid pair
   • If neither condition is met, add x to the hash set s for future comparisons

3. If we complete the entire traversal without finding a valid pair, return False.

Implementation Details:

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

The condition x * 2 in s checks if we've previously seen an element that is double the current element. The condition (x % 2 == 0 and x // 2 in s) first verifies that x is even (using x % 2 == 0) before checking if half of x exists in the set.

Time and Space Complexity:

• Time Complexity: O(n) where n is the length of the array, as we traverse the array once and hash set operations are O(1) on average
• Space Complexity: O(n) in the worst case when all elements are unique and we store them all in the hash set

Example Walkthrough

Let's walk through the solution with the array arr = [7, 1, 14, 11].

Initial State:

• Hash set s = {}
• We'll check each element to see if its double or half exists in the set

Step 1: Process element 7

• Check if 7 * 2 = 14 is in s? No, s is empty
• Check if 7 // 2 = 3 is in s? No need to check (7 is odd)
• No match found, add 7 to the set
• s = {7}

Step 2: Process element 1

• Check if 1 * 2 = 2 is in s? No, 2 is not in {7}
• Check if 1 // 2 = 0 is in s? No need to check (1 is odd)
• No match found, add 1 to the set
• s = {7, 1}

Step 3: Process element 14

• Check if 14 * 2 = 28 is in s? No, 28 is not in {7, 1}
• Check if 14 // 2 = 7 is in s? Yes! 14 is even, and 7 exists in {7, 1}
• Match found! Return True

We found that 14 = 2 * 7, where 7 was seen at index 0 and 14 is at index 2, satisfying our condition that one element is exactly double another at different indices.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array arr. This is because the algorithm iterates through the array exactly once, and for each element, it performs constant-time operations: checking membership in a set (x * 2 in s and x // 2 in s) and adding an element to the set (s.add(x)), which are all O(1) operations on average for hash sets.

The space complexity is O(n), where n is the length of the array arr. In the worst case, when no early return occurs (meaning no element satisfies the condition), all n elements from the array will be added to the set s, requiring O(n) additional space to store them.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Handling Zero Values Incorrectly

The Problem: When the array contains zeros, a subtle bug can occur. Since 0 * 2 = 0 and 0 // 2 = 0, a single zero would satisfy the condition arr[i] == 2 * arr[j] with itself. However, the problem requires two different indices, so we need at least two zeros in the array for this to be valid.

Example of the Issue:

• arr = [0, 1, 3] - Should return false (single zero can't pair with itself)
• arr = [0, 1, 0] - Should return true (two zeros at different indices)

Why the Current Solution Works: The hash set approach naturally handles this case correctly because:

1. When we encounter the first 0, we check if 0 * 2 = 0 or 0 // 2 = 0 exists in the set
2. Since the set is initially empty (or doesn't contain 0 yet), both checks fail
3. We then add 0 to the set
4. If we encounter another 0 later, now the check succeeds and we return true

Pitfall 2: Integer Division vs Float Division

The Problem: Using regular division / instead of integer division // could lead to incorrect comparisons when checking if half of a number exists.

Incorrect Implementation:

if x * 2 in s or (x % 2 == 0 and x / 2 in s):  # Wrong: x / 2 returns float

Why It's Wrong:

• x / 2 returns a float (e.g., 6 / 2 = 3.0)
• The set contains integers (e.g., 3)
• In Python, 3.0 == 3 is True, but 3.0 in {3} depends on hash equality
• While this often works in Python due to hash equality between equivalent ints and floats, it's not semantically correct and could cause issues in other languages

Correct Implementation:

if x * 2 in s or (x % 2 == 0 and x // 2 in s):  # Correct: x // 2 returns int

Pitfall 3: Forgetting to Check if Number is Even

The Problem: Attempting to check for half of an odd number without verifying it's even first.

Incorrect Implementation:

if x * 2 in s or x // 2 in s:  # Wrong: doesn't check if x is even

Why It's Wrong:

• For x = 5, we get x // 2 = 2
• If 2 exists in the set, we'd incorrectly return true
• But 2 * 2 = 4, not 5, so this is a false positive

Example:

• arr = [2, 5] would incorrectly return true
• When processing 5, we'd check if 5 // 2 = 2 is in the set
• Since 2 was added first, the check succeeds incorrectly

Correct Implementation: Always verify the number is even before checking for its half:

if x * 2 in s or (x % 2 == 0 and x // 2 in s):