Problem 1346

Abstract / Summary

Check if an array contains a number and its double.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1346.py

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        freq = defaultdict(int)
        for a in arr:
            freq[a] += 1

        for f in freq:
            if f == 0 and freq[f] > 1:
                return True
            if f != 0 and 2*f in freq:
                return True

        return False
13 lines | 340 bytes | submitted October 11, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 37% (900k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Binary Search
  • Hash Table
  • Sorting
  • Two Pointers
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a method that determines whether an integer array contains a pair of elements where one element is exactly double the other. The algorithm proceeds in two distinct phases: first it aggregates the occurrence count of each distinct value, then it inspects the aggregated data to decide if the required relationship exists. By separating counting from checking, the solution avoids repeated scans of the original list and leverages constant-time dictionary lookups.

Frequency Map Construction

The initial loop iterates over the input list and populates a dictionary that maps each integer to the number of times it appears. The use of a defaultdict with an integer default simplifies the increment operation.

freq = defaultdict(int)
for a in arr:
    freq[a] += 1

This step creates a compact representation of the input where duplicate values are collapsed into a single entry with an associated count. The dictionary keys correspond to the unique numbers in the array, and the values represent their frequencies.

Pair Detection Logic

After the frequency map is ready, the method examines each distinct value to see whether a qualifying counterpart exists. Two conditional branches cover the two possible scenarios.

for f in freq:
    if f == 0 and freq[f] > 1:
        return True
    if f != 0 and 2*f in freq:
        return True

The first branch handles the special case where the value is zero. Because zero doubled is still zero, the condition requires at least two occurrences of zero to form a valid pair. The second branch applies to all non-zero values, checking whether the double of the current key is present among the keys of the frequency map. If either condition is satisfied, the method returns True immediately, terminating further processing.

If the loop completes without finding a matching pair, the method returns False, indicating that no such relationship exists in the input.

Edge Cases Handled

The algorithm explicitly addresses the situation where the array contains multiple zeros. Since 0 * 2 equals 0, a single zero does not satisfy the requirement; the code checks that the count of zero exceeds one before confirming a valid pair. This ensures that arrays like [0] correctly yield False, while [0, 0] yields True.

Another implicit edge case involves negative numbers. Because the check multiplies the current value by two, a negative number will correctly be paired with its double, which is also negative. For example, [-2, -4] satisfies the condition because -4 is double -2. The algorithm does not need separate handling for sign; the arithmetic works uniformly for positive, negative, and zero values.

Performance Optimizations

The design leverages a hash-based dictionary to achieve constant-time insertion and lookup for each element. By constructing the frequency map in a single pass, the solution avoids nested loops that would otherwise increase the number of element comparisons. The subsequent inspection iterates only over the distinct keys rather than the entire original list, reducing the amount of work when many duplicates are present.

Early termination is another optimization. As soon as a qualifying pair is detected, the method returns True without scanning the remaining keys. This short-circuit behavior can significantly cut execution time for inputs where the condition is met early in the iteration.

Overall, the combination of a single pass for counting, dictionary-based lookups, and immediate exit upon success yields an efficient solution for the problem of detecting a double relationship within an integer array.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a box full of numbered blocks. The computer takes all those blocks and sorts them into little piles so it knows exactly how many of each number are sitting in the box. One pile might have all the twos, and another pile might have all the fours.

Once everything is organized, the computer looks through the piles to play a game of hide and seek. It looks at a number and asks if there is another block that is exactly twice as big as that one. For example, if it finds a two, it checks the piles to see if a four is hiding nearby. If it finds the pair, it says everything is found. There is also a special rule for the number zero. If the computer finds two different zero blocks, that also counts as a win. If it checks all the numbers and never finds a matching pair, the game ends.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 7 | μ = 6.88 | σ = 1.53

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java Python
leetcode.ca C++ JS Java Python Go PHP Rust TS
Progiez C++ Java Python
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
DimitrisJim JS
fartem Ruby
fpdjsns C++
fsq C++
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
lzl124631x C++
Shamik07 Dart
suxrobGM C#
varunu28 Java
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, JavaScript, PHP, Python, Rust, TypeScript
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
DimitrisJim JavaScript
fartem Ruby
fpdjsns C++
fsq C++
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
lzl124631x C++
Shamik07 Dart
suxrobGM C#
varunu28 Java
32 links | 18 authors | 11 languages

Videos

10 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

16 solutions   October 11, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality