Code Implementation

class Solution:
    def checkIfExist(self, arr):
        seen = set()
        for num in arr:
            if 2 * num in seen or (num % 2 == 0 and num // 2 in seen):
                return True
            seen.add(num)
        return False
      

class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        unordered_set<int> seen;
        for (int num : arr) {
            if (seen.count(2 * num) || (num % 2 == 0 && seen.count(num / 2)))
                return true;
            seen.insert(num);
        }
        return false;
    }
};
      

import java.util.HashSet;
class Solution {
    public boolean checkIfExist(int[] arr) {
        HashSet<Integer> seen = new HashSet<>();
        for (int num : arr) {
            if (seen.contains(2 * num) || (num % 2 == 0 && seen.contains(num / 2)))
                return true;
            seen.add(num);
        }
        return false;
    }
}
      

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

Problem Description

Given an array of integers arr, determine if there exist two distinct indices i and j such that arr[i] == 2 * arr[j]. In other words, check if the array contains an element and its double somewhere else in the array.

• You cannot use the same element twice (i.e., i != j).
• Return true if such a pair exists, otherwise return false.
• The array can contain both positive and negative numbers, as well as zero.

Thought Process

To solve this problem, the first idea that comes to mind is to check every possible pair in the array to see if one number is double the other. This would work, but it could be slow for large arrays because it checks all possible pairs.

We can make this process faster by using a set to keep track of the numbers we've seen so far. For each number, we can quickly check if its double or its half (if it's even) has already appeared. This avoids redundant checks and speeds up the solution.

The key insight is that, for each number, there are only two possibilities to check: does the set contain 2 * num or, if num is even, does it contain num / 2?

Solution Approach

Let's break down the optimized solution step by step:

1. Initialize a set: Start with an empty set to keep track of numbers we've seen so far.
2. Iterate through the array: For each number in arr:
   • Check if 2 * num is already in the set. If it is, we've found a valid pair.
   • If num is even, check if num / 2 is in the set. This covers the case where the current number is the double of a previously seen number.
3. Add the current number to the set: This ensures future numbers can check against it.
4. If no pair is found: Return false at the end.

We use a set because it allows for constant time lookups, making the solution efficient.

Example Walkthrough

Let's use the input arr = [10, 2, 5, 3] as an example.

1. Start with an empty set: {}
2. First number is 10:
   • Is 20 in the set? No.
   • Is 5 in the set? (since 10 is even) No.
   • Add 10 to the set: {10}
3. Next number is 2:
   • Is 4 in the set? No.
   • Is 1 in the set? (since 2 is even) No.
   • Add 2 to the set: {10, 2}
4. Next number is 5:
   • Is 10 in the set? Yes! We've found a pair: 5 and 10.
   • Return true.

The process stops as soon as a valid pair is found.

Time and Space Complexity

• Brute-force approach:
  • Check every pair of elements, leading to O(n^2) time complexity.
  • No extra space needed beyond a few variables: O(1) space.
• Optimized set-based approach:
  • Each element is processed once, with constant-time set operations: O(n) time complexity.
  • We store up to n elements in the set: O(n) space complexity.

The set-based approach is much more efficient for large arrays.

Summary

This problem asks us to determine if an array contains an element and its double at different positions. While a brute-force solution is possible, it is inefficient. By using a set to track seen numbers, we can quickly check for the required conditions in a single pass, making the solution both simple and efficient. The key insight is to check for both double and half (when the number is even) for each element, leveraging the power of constant-time set lookups.