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
Difficulty
and has an acceptance rate of about 37% (900k+ submissions).
Typical patterns to solve this problem:
- Array
- Binary Search
- Hash Table
- Sorting
- Two Pointers
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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 |
Videos
Similar Problems
- problem 2154: Keep Multiplying Found Values by Two
Solved On The Same Day
- problem 859: Buddy Strings
- problem 914: X of a Kind in a Deck of Cards
- problem 925: Long Pressed Name
- problem 1805: Number of Different Integers in a String
- problem 1909: Remove One Element to Make the Array Strictly Increasing
- problem 2047: Number of Valid Words in a Sentence
- problem 2469: Convert the Temperature
- problem 2525: Categorize Box According to Criteria
- problem 2591: Distribute Money to Maximum Children
- problem 2614: Prime In Diagonal
- problem 2660: Determine the Winner of a Bowling Game
- problem 2760: Longest Even Odd Subarray With Threshold
- problem 2765: Longest Alternating Subarray
- problem 1255: Maximum Score Words Formed by Letters
- problem 2251: Number of Flowers in Full Bloom
Extra
- 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