Leetcode 1346: Check If N and Its Double Exist

This problem is part of the Introduction to Data Structures Arrays-101 section in LeetCode.

Problem Statement

Given an array arr of integers, check if there exists two integers N and M such that N is the double of M ( i.e. N = 2 * M).

More formally check if there exists 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: N = 10 is the double of M = 5,that is, 10 = 2 * 5.

Example 2

Input: arr = [7,1,14,11]
Output: true
Explanation: N = 14 is the double of M = 7,that is, 14 = 2 * 7.

Example 3

Input: arr = [3,1,7,11]
Output: false
Explanation: In this case does not exist N and M, such that N = 2 * M.

Constraints:

• 2 <= arr.length <= 500
• -10^3 <= arr[i] <= 10^3

First thought - Solution 1: two loops

 var checkIfExist = function(arr) {
     for(let i=0;i<arr.length;i++){
         let target = arr[i]
         for(let j=i+1;j<arr.length;j++){
             if(target === arr[j]*2 || target === arr[j]/2){
                 return true
             }
         }
     }
     return false
 };

Time complexity : O(n²)
Space complexity : O(n)

Solution 2: hash table

We could also use hash table data structure to solve this problem using Set object or array.

1. Iterate over the array and check if element in array multiplied by 2 or divided by 2 is equal to the element in the Set object.
2. If existed, then return true
3. If not existed, then add the element in the Set object.

var checkIfExist = function (arr){
    let newSet = new Set()
    for(let i=0;i<arr.length;i++){
        if(newSet.has(arr[i]/2) || newSet.has(arr[i]*2)){
            return true
        }else{
            newSet.add(arr[i])
        }
    }
      return false
}

NOTE: considering 0 in array

• [0,0] - output is True
• [0,10,7,1] - output is False

Time complexity : O(n)
For each element, we try to find its match in the Set object by looping through the array which takes O(n) time.

Space complexity : O(n)
The space complexity is O(n) because it needs a variable newSet to store the data.