How do you solve Check If N and Its Double Exist on LeetCode?

Check If N and Its Double Exist (LeetCode #1346) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a hash set can significantly reduce the time complexity of the solution.

What is the time complexity of Check If N and Its Double Exist?

The optimal solution for Check If N and Its Double Exist runs in O(n) time and uses O(n) space. This complexity is linear because we traverse the array once, and the hash set operations (add and check) are average O(1).

What is the brute force solution for Check If N and Its Double Exist?

The brute force approach for Check If N and Its Double Exist is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every possible pair of indices in the array to see if one element is double the other. This is straightforward but inefficient for larger arrays. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Check If N and Its Double Exist?

Check If N and Its Double Exist uses the following concepts: Array, Hash Table, Two Pointers, Binary Search, Sorting. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Check If N and Its Double Exist?

Always clarify the problem requirements before jumping into coding. Think about edge cases, such as negative numbers or zero. Explain your thought process as you code; it helps interviewers follow your logic.

What are common mistakes when solving Check If N and Its Double Exist?

Not considering the case where the number could be half of another number. Confusing index checks and element checks, leading to incorrect conditions.

#1346

Check If N and Its Double Exist

Easy

ArrayHash TableTwo PointersBinary SearchSortingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Using a hash set allows us to store elements we have seen so far, enabling O(1) average time complexity for lookups. This significantly reduces the number of comparisons needed.

⚙️

Algorithm

5 steps

1Step 1: Initialize an empty hash set.
2Step 2: Loop through each element in the array.
3Step 3: For each element, check if double the value exists in the hash set. If it does, return true.
4Step 4: Add the current element to the hash set.
5Step 5: If no pairs are found after the loop, return false.

solution.py10 lines

1# Full working Python code
2arr = [10, 2, 5, 3]
3def checkIfExist(arr):
4    seen = set()
5    for num in arr:
6        if 2 * num in seen or (num % 2 == 0 and num // 2 in seen):
7            return True
8        seen.add(num)
9    return False
10print(checkIfExist(arr))

ℹ

Complexity note: This complexity is linear because we traverse the array once, and the hash set operations (add and check) are average O(1).

1Using a hash set can significantly reduce the time complexity of the solution.
2Checking both conditions (double and half) ensures we cover all cases.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.