Scale Engineer

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 SearchSorting
Data structures
ArrayHash 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
  • -103 <= arr[i] <= 103

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:

class Solution {    public boolean checkIfExist(int[] arr) {        int n = arr.length;        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                // The indices must be different                if (i != j && arr[i] == 2 * arr[j]) {                    return true;                }            }        }        return false;    }}

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.

Solutions

class Solution {public  boolean checkIfExist(int[] arr) {    Map<Integer, Integer> m = new HashMap<>();    int n = arr.length;    for (int i = 0; i < n; ++i) {      m.put(arr[i], i);    }    for (int i = 0; i < n; ++i) {      if (m.containsKey(arr[i] << 1) && m.get(arr[i] << 1) != i) {        return true;      }    }    return false;  }}

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 →

Next problem