1346. Check If N and Its Double Exist

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

Approach 01:

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    bool checkIfExist(vector<int>& numbers) {
        unordered_map<int, int> numberFrequency;

        // Count the frequency of each number
        for (int number : numbers) {
            numberFrequency[number]++;
        }

        // Check for zeroes
        if (numberFrequency[0] > 1) {
            return true;
        }

        // Check if double exists for any number
        for (const auto& [number, frequency] : numberFrequency) {
            if (numberFrequency.count(2 * number) > 0 && number != 2 * number) {
                return true;
            }
        }

        return false;
    }
};

from collections import Counter
from typing import List

class Solution:
    def checkIfExist(self, numbers: List[int]) -> bool:
        numberFrequency = Counter(numbers)

        # Check for zeroes
        if numberFrequency[0] > 1:
            return True

        # Check if double exists for any number
        for number, frequency in numberFrequency.items():
            if numberFrequency[2 * number] > 0 and number != 2 * number:
                return True

        return False

Time Complexity

• Counting the frequency of each number:

  The first for loop iterates over all elements in the array numbers, which has a size of \(N\). This step takes \(O(N)\).

• Checking for zeroes:

  The condition numberFrequency[0] > 1 is checked in \(O(1)\), as it directly accesses a value in the hash map.

• Checking for double existence:

  The second for loop iterates over all unique keys in the unordered_map. In the worst case (all numbers are unique), this loop runs \(O(N)\). Each count operation in the map is \(O(1)\). Thus, this step takes \(O(N)\).

• Overall Time Complexity:

  The overall time complexity is \(O(N)\), as the operations are linear and performed sequentially.

Space Complexity

• Frequency map:

  The unordered_map stores the frequency of each unique number in the input array. In the worst case (all numbers are unique), it stores \(N\) entries, resulting in \(O(U)\), where \(U\) is the number of unique numbers (at most \(N\)).

• Input array:

  The input array itself uses \(O(N)\) space, but this is not considered extra space as it is part of the input.

• Overall Space Complexity:

  The overall space complexity is \(O(U)\), which simplifies to \(O(N)\) in the worst case when all numbers are unique.