Problem Description
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:
- Special handling for zeros because we need two different zeros
- For each non-zero number, check both:
- If its double exists
- If its half exists (for even numbers)
- 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
-
Zeros: Need special handling because 0 * 2 = 0
arr = [0, 0] # Should return True arr = [0] # Should return False
-
Negative Numbers: Work the same as positive numbers
arr = [-2, -4] # Should return True (-2 * 2 = -4)
-
Duplicate Non-Zero Numbers: Need different indices
arr = [2, 2] # Should return False (same index not allowed)