Back to blog
Dec 01, 2024
3 min read

LeetCode 1346: Check If N and Its Double Exist

Leetcode 1346: Check If N and Its Double Exist solution in Python

Problem Description

LeetCode Problem 1346

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]

 

Example 1:

Input: arr = [10,2,5,3] Output: true Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

Example 2:

Input: arr = [3,1,7,11] Output: false Explanation: There is no i and j that satisfy the conditions.

 

Constraints:

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

Difficulty: Easy

Tags: array, hash table, two pointers, binary search, sorting

Rating: 90.79%

Solution Approaches

1. Hash Set Solution

This is the most efficient approach using a hash set for O(1) lookups.

def checkIfExist(self, arr: List[int]) -> bool:
    seen = set()
    zero_count = 0
    
    for num in arr:
        if num == 0:
            zero_count += 1
            if zero_count > 1:
                return True
        else:
            if 2 * num in seen or (num % 2 == 0 and num // 2 in seen):
                return True
            seen.add(num)
    
    return False

Key Points:

  1. Special handling for zeros because we need two different zeros
  2. For each non-zero number, check both:
    • If its double exists
    • If its half exists (for even numbers)
  3. Add each number to the set after checking

Time Complexity: O(n)
Space Complexity: O(n)

2. Two Pointers Solution

A different approach using sorting and two pointers.

def checkIfExist(self, arr: List[int]) -> bool:
    arr.sort()
    n = len(arr)
    
    for i in range(n):
        target = 2 * arr[i]
        # Skip adjacent duplicate elements for zero
        if i > 0 and arr[i] == arr[i-1] == 0:
            return True
            
        # Binary search for the double
        left, right = 0, n-1
        while left <= right:
            mid = (left + right) // 2
            if mid != i and arr[mid] == target:
                return True
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
                
    return False

Time Complexity: O(n log n)
Space Complexity: O(1)
(Better space complexity but worse time complexity)

Edge Cases to Consider

  1. Zeros: Need special handling because 0 * 2 = 0

    arr = [0, 0]  # Should return True
    arr = [0]     # Should return False
    
  2. Negative Numbers: Work the same as positive numbers

    arr = [-2, -4]  # Should return True (-2 * 2 = -4)
    
  3. Duplicate Non-Zero Numbers: Need different indices

    arr = [2, 2]  # Should return False (same index not allowed)