Check If N and Its Double Exist

Easy

#1250Time: O(N^2), where N is the number of elements in the array. For each element, we iterate through the entire array again, leading to a quadratic number of comparisons.Space: O(1), as we only use a few variables to store indices and the array length, which does not depend on the input size.

Patterns

Two Pointers

Algorithms

Binary Search Sorting

Data structures

Array Hash Table

Prompt

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³ <= arr[i] <= 10³

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward approach is to check every possible pair of elements in the array. We can use two nested loops to iterate through all pairs of indices (i, j) and verify if the condition arr[i] == 2 * arr[j] holds, ensuring that i and j are not the same.

Algorithm

Initialize two nested loops, with iterators i and j, both from 0 to arr.length - 1.
Inside the inner loop, check if the indices are different (i != j).
If the indices are different, check if the condition arr[i] == 2 * arr[j] is met.
If the condition is true, a valid pair has been found, so return true immediately.
If the loops complete without finding any such pair, it means no such pair exists. Return false.

Walkthrough

This method involves a systematic check of all pairs. The outer loop selects an element arr[i], and the inner loop iterates through all other elements arr[j] to see if arr[j] is half of arr[i]. The algorithm is as follows:

1class Solution {2    public boolean checkIfExist(int[] arr) {3        int n = arr.length;4        for (int i = 0; i < n; i++) {5            for (int j = 0; j < n; j++) {6                // The indices must be different7                if (i != j && arr[i] == 2 * arr[j]) {8                    return true;9                }10            }11        }12        return false;13    }14}

Complexity

Time

O(N^2), where N is the number of elements in the array. For each element, we iterate through the entire array again, leading to a quadratic number of comparisons.

Space

O(1), as we only use a few variables to store indices and the array length, which does not depend on the input size.

Trade-offs

Pros

Simple to understand and implement.
Requires no extra memory, making it space-efficient.

Cons

Highly inefficient for large arrays due to its quadratic time complexity.
Performs many redundant checks.

A more optimized approach involves sorting the array first. Once the array is sorted, for each element x, we can use binary search to efficiently find if its double (2*x) exists in the array. This avoids the need for a linear scan for each element.

Algorithm

First, sort the input array arr in non-decreasing order.
Iterate through the sorted array with an index i from 0 to arr.length - 1.
For each element arr[i], calculate the target value, which is 2 * arr[i].
Perform a binary search for the target in the rest of the array, excluding the element at index i.
If the binary search finds the target, return true.
If the loop finishes without finding any such pair, return false.

Walkthrough

By sorting the array, we can leverage the ordered property to speed up the search. For each element arr[i], we calculate the target value (2 * arr[i]). Then, we perform a binary search for this target in the array. A crucial detail is to ensure that if the target is found at an index j, it must be a different element, i.e., j != i. This is particularly important for the case where arr[i] is 0. A robust way to handle this is to define the search space for the binary search to exclude the current index i.

1import java.util.Arrays;2 3class Solution {4    public boolean checkIfExist(int[] arr) {5        Arrays.sort(arr);6        for (int i = 0; i < arr.length; i++) {7            int target = 2 * arr[i];8            // Define the search range to exclude the current element.9            // If target is larger, search to the right. If smaller, search to the left.10            int low, high;11            if (arr[i] >= 0) {12                low = i + 1;13                high = arr.length - 1;14            } else { // arr[i] < 0, so 2 * arr[i] < arr[i]15                low = 0;16                high = i - 1;17            }18            19            // Standard binary search in the defined range20            while (low <= high) {21                int mid = low + (high - low) / 2;22                if (arr[mid] == target) {23                    return true;24                } else if (arr[mid] < target) {25                    low = mid + 1;26                } else {27                    high = mid - 1;28                }29            }30        }31        return false;32    }33}

Complexity

Time

O(N log N). Sorting the array takes O(N log N). The subsequent loop runs N times, with each iteration performing a binary search that takes O(log N). The total time is dominated by the sorting step.

Space

O(log N) to O(N), depending on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitive types has an average space complexity of O(log N) for the recursion stack.

Trade-offs

Pros

Significantly faster than the brute-force approach for larger arrays.
A good trade-off between time and space complexity.

Cons

The in-place sort modifies the original array, which might not be desirable.
More complex to implement correctly, especially handling the i != j condition with binary search.

The most efficient solution uses a HashSet to achieve linear time complexity. We iterate through the array, and for each element, we check if its double or its half already exists in the set of numbers we've seen so far. This avoids repeated computations and searches.

Algorithm

Initialize an empty HashSet called seen to store the numbers encountered so far.
Iterate through each number num in the input array arr.
For each num, check if seen contains 2 * num.
Also, check if num is an even number and if seen contains num / 2.
If either of the above checks is true, it means we have found a valid pair. Return true.
If not, add the current num to the seen set.
If the loop completes, it means no such pair was found. Return false.

Walkthrough

We can use a HashSet for O(1) average time complexity lookups. We iterate through the array arr once. For each number num, we check two conditions before adding it to our set of seen numbers:

Does 2 * num exist in the set? If so, we've found a number that is half of an existing number.
Is num even, and does num / 2 exist in the set? If so, we've found a number that is double an existing number. If either of these conditions is true, we return true. Otherwise, we add the current number num to the set and continue. This ensures we find a pair regardless of the order they appear in the array.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public boolean checkIfExist(int[] arr) {6        Set<Integer> seen = new HashSet<>();7        for (int num : arr) {8            // Check if the double exists or if the half exists9            if (seen.contains(2 * num) || (num % 2 == 0 && seen.contains(num / 2))) {10                return true;11            }12            // Add the current number to the set for future checks13            seen.add(num);14        }15        return false;16    }17}

Complexity

Time

O(N), where N is the number of elements in the array. We iterate through the array once, and each HashSet operation (insertion and lookup) takes O(1) time on average.

Space

O(N), as in the worst-case scenario (no duplicates and no valid pairs), the HashSet will store all N elements from the array.

Trade-offs

Pros

Optimal time complexity of O(N).
The logic is straightforward and handles all cases, including zeros, elegantly.

Cons

Requires extra space proportional to the number of elements in the array.

Solutions

Solution

1class Solution {2public3  boolean checkIfExist(int[] arr) {4    Map<Integer, Integer> m = new HashMap<>();5    int n = arr.length;6    for (int i = 0; i < n; ++i) {7      m.put(arr[i], i);8    }9    for (int i = 0; i < n; ++i) {10      if (m.containsKey(arr[i] << 1) && m.get(arr[i] << 1) != i) {11        return true;12      }13    }14    return false;15  }16}

1/** * @param {number[]} arr * @return {boolean} */ var checkIfExist = function (2  arr,3) {4  const s = new Set();5  for (const v of arr) {6    if (s.has(v << 1) || s.has(v / 2)) {7      return true;8    }9    s.add(v);10  }11  return false;12};

1class Solution {2public:3  bool checkIfExist(vector<int> &arr) {4    unordered_map<int, int> m;5    int n = arr.size();6    for (int i = 0; i < n; ++i)7      m[arr[i]] = i;8    for (int i = 0; i < n; ++i)9      if (m.count(arr[i] * 2) && m[arr[i] * 2] != i)10        return true;11    return false;12  }13};

1class Solution:2    def checkIfExist(self, arr: List[int]) -> bool: m = {v: i for i, v in enumerate(arr)} return any(v << 1 in m and m[v << 1] != i for i, v in enumerate(arr))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  boolean checkIfExist(int[] arr) {4    Map<Integer, Integer> m = new HashMap<>();5    int n = arr.length;6    for (int i = 0; i < n; ++i) {7      m.put(arr[i], i);8    }9    for (int i = 0; i < n; ++i) {10      if (m.containsKey(arr[i] << 1) && m.get(arr[i] << 1) != i) {11        return true;12      }13    }14    return false;15  }16}

1/** * @param {number[]} arr * @return {boolean} */ var checkIfExist = function (2  arr,3) {4  const s = new Set();5  for (const v of arr) {6    if (s.has(v << 1) || s.has(v / 2)) {7      return true;8    }9    s.add(v);10  }11  return false;12};

1class Solution {2public:3  bool checkIfExist(vector<int> &arr) {4    unordered_map<int, int> m;5    int n = arr.size();6    for (int i = 0; i < n; ++i)7      m[arr[i]] = i;8    for (int i = 0; i < n; ++i)9      if (m.count(arr[i] * 2) && m[arr[i] * 2] != i)10        return true;11    return false;12  }13};

1class Solution:2    def checkIfExist(self, arr: List[int]) -> bool: m = {v: i for i, v in enumerate(arr)} return any(v << 1 in m and m[v << 1] != i for i, v in enumerate(arr))

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.