Check If N and Its Double Exist

LeetCode 1468 | Difficulty: Easy

Easy

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`

- `-10^3 <= arr[i] <= 10^3`

Topics: Array, Hash Table, Two Pointers, Binary Search, Sorting

---

Approach

Two Pointers

Use two pointers to traverse the array, reducing the search space at each step. This avoids the need for nested loops, bringing complexity from O(n²) to O(n) or O(n log n) if sorting is involved.

When to use

Array is sorted or can be sorted, and you need to find pairs/triplets that satisfy a condition.

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 100 ms)

Metric	Value
Runtime	100 ms
Memory	25.1 MB
Date	2020-02-11

Solution

public class Solution {
    public bool CheckIfExist(int[] arr) {
        List<int> vals = new List<int>();
    vals.Add(arr[0]);
    for (int i = 1; i < arr.Length; i++)
    {
        if (arr[i] % 2 == 0)
        {
            if (vals.Contains(arr[i] / 2) || vals.Contains(arr[i] * 2))
            {
                return true;
            }
        }
        else
        {
            if (vals.Contains(arr[i] * 2))
            {
                return true;
            }
        }
        vals.Add(arr[i]);
    }
    return false;
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Binary Search	$O(log n)$	$O(1)$
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Ask: "Can I sort the array?" — Sorting often enables two-pointer techniques.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• Precisely define what the left and right boundaries represent, and the loop invariant.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Loop from i = 0 to arr.length, maintaining in a hashTable the array elements from [0, i - 1].

Hint 2: On each step of the loop check if we have seen the element 2 * arr[i] so far.

Hint 3: Also check if we have seen arr[i] / 2 in case arr[i] % 2 == 0.