Check If N and Its Double Exist - Video Solutions

Problem Overview: Given an integer array arr, determine whether there exist two indices i and j such that i != j and arr[i] == 2 * arr[j]. In simpler terms, check if any number in the array has its double also present.

The challenge is not the comparison itself but doing it efficiently. A naive solution checks every pair, which quickly becomes slow as the array grows. Efficient solutions rely on fast lookups or ordering the array to detect the relationship between values.

Approach 1: Using a Hash Set (O(n) time, O(n) space)

This approach scans the array once while storing previously seen numbers in a hash set. For each element x, check whether 2 * x or x / 2 already exists in the set. The key insight is that if either of those values has appeared earlier, the required pair exists immediately. Hash lookups run in constant time, so each iteration performs a few O(1) checks and inserts.

This method works for any unsorted array and handles negative numbers and zero correctly. The special case with 0 is naturally handled because the set check detects a second zero. Since the algorithm processes each element once and performs constant-time operations, the total runtime is O(n) with O(n) extra space for the set. This approach heavily relies on fast membership checks provided by a hash table and is the most practical solution in interviews.

Approach 2: Sorting and Two Pointers (O(n log n) time, O(1) extra space)

Another strategy first sorts the array, then searches for pairs where one value equals double the other. After sorting, you can use a pointer for each number and apply binary search or a two‑pointer technique to locate 2 * arr[i]. Sorting ensures the numbers are ordered, which makes these searches efficient.

A common implementation sorts the array and, for each index, performs a binary search for its double. Sorting costs O(n log n), and each lookup costs O(log n). Another variation moves two pointers through the sorted list to maintain the doubling relationship. Both approaches leverage ordering provided by sorting and pointer movement similar to patterns used in two pointers problems.

The advantage of this approach is lower auxiliary memory usage because the algorithm works directly on the sorted array. The tradeoff is slower runtime compared with the hash set method due to the initial sort.

Recommended for interviews: The hash set solution is typically expected. It demonstrates that you recognize the pattern of converting a pair-search problem into constant-time lookups using a hash structure. Discussing the sorting approach still helps because it shows awareness of alternative strategies and space–time tradeoffs. Strong candidates often mention the brute force O(n²) idea briefly, then move quickly to the O(n) hash-based optimization.