• Leetcode POTDs

Problem 1346 Check If N and Its Double Exist

Problem Statement

Link - Problem 1346

Question

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

Solution

class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        unordered_map<int,int>check;
        for(auto num:arr){
            check[num]++;
        }
        for(auto num:arr){
            if(num!= 0 && check.find(num*2)!=check.end())
                return true;
            if(num == 0 && check[num]>1)
                return true;
        }
        return false;

    }
};

Complexity Analysis

| Algorithm     | Time Complexity | Space Complexity |
| ------------- | --------------- | ---------------- |
| Hash counting | O(n)            | O(n)             |

Explanation

Intial Thoughts

First, consider the nature of the problem which is to find two indices, i and j, with the given constraints. Since the array can be quite large, we need an efficient strategy. A key point is to think of the relationship arr[i] == 2 * arr[j] in terms of pairs of numbers. Is there an existing data structure that can efficiently store these pairs?

Intuitive Analysis

A crucial insight is to recognize that this problem can be solved using a dictionary-like data structure for storing numbers as keys. An intuitive explanation would be the concept of checking for an existing key in a dictionary before adding a new one. This approach is efficient because it leads us to the optimal solution. Think of the potential differences when applying the given condition based on whether the number is zero or not. What special considerations should be taken into account for zero?

1. Intuition

• The problem requires finding two indices i and j in the array such that arr[i] == 2 * arr[j].
• To solve this problem efficiently, we need to think about how to quickly check if a number is present in the array or if its double is present.
• A brute force approach would be to compare each element with every other element, but this would be inefficient due to its O(n^2) time complexity.
• A better approach is to use a hash-based data structure like an unordered_map to store the elements of the array and their counts.
• This allows us to check if a number or its double is present in the array in constant time.
• We also need to handle the case where the number is zero, since zero multiplied by two is still zero.

2. Implementation

• We create an unordered_map called check to store the elements of the array and their counts.
• We iterate over the array and for each number, we increment its count in the check map.
• We then iterate over the array again and for each number, we check if its double is present in the check map.
• If the number is not zero and its double is present in the check map, we return true.
• If the number is zero and its count in the check map is greater than one, we return true.
• If we finish iterating over the array without finding a pair of numbers that satisfy the condition, we return false.

Complexity Analysis

Time Complexity:

• The algorithm iterates over the input array twice: once to populate the ‘check’ unordered map (for(auto num:arr){ check[num]++; }), and once to verify the presence of doubled numbers (for(auto num:arr){ ... }). Both iterations contribute linear complexity.
• Within each iteration, the dominant operation is either a map lookup (check.find(num*2)) or a simple arithmetic operation (num != 0 or check[num] > 1). These operations are constant time, resulting in linear overall complexity.
• Since both loops are of size ’n’ (where ’n’ represents the input array’s size), we can express this complexity as O(n) + O(n) = O(2n). However, constant factors are ignored in Big O notation, yielding O(n).

Space Complexity:

• The additional memory required by this algorithm stems from the ‘check’ unordered map, which stores a separate entry for each distinct number in the input array.
• In the worst-case scenario (e.g., an array of distinct numbers), this map will store ’n’ entries, contributing O(n) space complexity.
• In other scenarios, depending on the level of duplication within the array, the space complexity may decrease proportionally. However, since Big O notation represents the worst-case scenario, we classify the space complexity as O(n).

Footnote

This question is rated as Easy difficulty.

Hints

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

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

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

Similar Questions: