algoadvance

Leetcode 1346. Check If N and Its Double Exist

Problem Statement

Given an array arr of integers, check if there exist two indices i and j such that:

• i != j
• 0 <= i, j < arr.length
• arr[i] == 2 * arr[j]

Return true if such elements exist, otherwise return false.

Clarifying Questions

1. Are the elements of the array positive or negative?
   • They can be both positive and negative integers.
2. What should be returned if the array is empty or contains one element?
   • If the array is empty or contains one element, return false.
3. Is there any constraint on the size of the array?
   • Typical constraints as per competitive programming context, assume 1 <= arr.length <= 500.

Strategy

1. Using a Hash Set for O(n) time complexity:
   • Use a hash set to keep track of the visited numbers.
   • Iterate through the array and for each element x:
     • Check if x * 2 or x / 2 (only if x is even) exists in the set.
     • If found, return true.
     • Otherwise, add x to the set.
   • If no such pair is found, return false.

This approach ensures we check every possible pair in linear time, making it efficient.

Code

import java.util.HashSet;

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

Time Complexity

• Time Complexity: O(n)
  • We traverse the array once, and each operation with the hash set (check contains and add) is O(1) on average.
• Space Complexity: O(n)
  • In the worst case, we store all elements in the hash set.

This solution is efficient both in terms of time and space, making it suitable for the given constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?