Python 0532.py
class Solution:
def findPairs(self, nums: List[int], k: int) -> int:
if k == 0:
result = 0
freq = defaultdict(int)
for n in nums:
freq[n] += 1
if freq[n] == 2:
result += 1
return result
else: # k > 0
unique = set(nums)
return sum([ 1 if u + k in unique else 0 for u in unique ])
Difficulty
and has an acceptance rate of about 46% (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 findPairs method computes the number of distinct integer pairs in the input list nums whose absolute difference equals the integer k. It distinguishes two logical paths: one for the special case where k is zero and another for positive values of k. Each path employs data structures that enable fast membership tests and counting, ensuring that the algorithm scales well with the size of the input.
Zero-difference case
When k is zero the problem reduces to counting how many values appear at least twice in nums. The implementation creates a frequency map using defaultdict(int). As each number is processed, its count is incremented. The moment a count reaches exactly two, the result counter is increased, guaranteeing that each duplicated value contributes only once to the final answer.
if k == 0:
result = 0
freq = defaultdict(int)
for n in nums:
freq[n] += 1
if freq[n] == 2:
result += 1
return result
The edge case of an empty list or a list with all unique elements is naturally handled: the loop never triggers the freq[n] == 2 condition, so result remains zero. Likewise, values that appear more than twice are counted only once because the increment occurs solely when the frequency transitions from one to two.
Positive-difference case
For k greater than zero the method first collapses nums into a set of unique values, eliminating any duplicate entries that are irrelevant for distinct pair counting. It then iterates over this set, checking for the existence of each element plus k. The comprehension yields a 1 for each successful check, and sum aggregates these ones into the final count.
else: # k > 0
unique = set(nums)
return sum([1 if u + k in unique else 0 for u in unique])
By using a set, the lookup u + k in unique executes in constant time on average, which is a key performance optimization. The comprehension avoids the overhead of an explicit loop and conditional branching outside the expression, keeping the core logic concise. The code also gracefully handles cases where nums contains no elements or where no two numbers satisfy the required difference; the comprehension produces an empty list or a list of zeros, and sum returns zero.
Performance considerations
The algorithm leverages hash-based containers (defaultdict and set) to achieve fast insertions and membership checks. In the zero-difference branch, the frequency map grows only as large as the number of distinct elements, and the early increment on the second occurrence prevents unnecessary further counting for the same value. In the positive-difference branch, converting the list to a set removes duplicates in a single pass, reducing the number of iterations needed for the subsequent check. The use of a list comprehension combined with sum provides a compact way to tally qualifying pairs without auxiliary variables or explicit counters.
Overall, the implementation balances clarity with efficiency, employing appropriate data structures to handle both the duplicate-heavy scenario (k == 0) and the distinct-value scenario (k > 0).
ELI5 - Simplified Explanation
Imagine there is a big collection of colorful blocks with numbers written on them. Sometimes the goal is to find pairs of blocks that have a special distance between their numbers. The distance is like a measuring stick told to the computer by the number k.
When the measuring stick is zero, the computer looks through all the blocks to see if any numbers appear exactly twice. It puts the blocks into a magic box that keeps score of how many times each number shows up. If a number hits the count of two, that means a matching pair is found.
When the measuring stick is bigger than zero, the computer does something clever by getting rid of all the extra duplicate blocks so only one of each number remains. Then it picks up each block one by one and asks a simple question. It asks if there is another block in the pile that is exactly k steps away from the one it is holding. If the answer is yes, that counts as a found pair. By looking at all the blocks this way, the computer keeps track of how many pairs exist that match the rule.
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++ | Python | Java | TS | |||||
| WalkCCC | C++ | Python | Java | |||||||
| leetcode.ca | C++ | Python | Java | Rust | Go | TS | ||||
| LeetcodeHelp | C++ | Python | Java | |||||||
| Progiez | C++ | Python | Java | |||||||
| github | AdelDaniel | Dart | ||||||||
| BigEggStudy | C# | |||||||||
| black-shadows | C++ | |||||||||
| charles-wangkai | Java | |||||||||
| everthis | JS | |||||||||
| FelixFan1122 | C# | |||||||||
| fsq | C++ | |||||||||
| gouthampradhan | Java | |||||||||
| halfrost | Go | |||||||||
| haoel | Python | |||||||||
| JoshCrozier | JS | |||||||||
| keineahnung2345 | C++ | |||||||||
| linouk23 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| ruoru | Rust | |||||||||
| shreymehul | C# | |||||||||
| suxrobGM | C# | |||||||||
| trung-hn | Python | |||||||||
| varunu28 | Java | |||||||||
| wisdompeak | C++ | |||||||||
| YuriSpiridonov | Python | |||||||||
| zfang399 | C++ | |||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||
| WalkCCC | C++, Python, Java | |||||||||
| leetcode.ca | C++, Go, Java, Python, Rust, TypeScript | |||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||
| Progiez | C++, Java, Python | |||||||||
| AdelDaniel | Dart | |||||||||
| BigEggStudy | C# | |||||||||
| black-shadows | C++, C++ | |||||||||
| charles-wangkai | Java | |||||||||
| everthis | JavaScript | |||||||||
| FelixFan1122 | C# | |||||||||
| fsq | C++ | |||||||||
| gouthampradhan | Java | |||||||||
| halfrost | Go | |||||||||
| haoel | Python | |||||||||
| JoshCrozier | JavaScript | |||||||||
| keineahnung2345 | C++ | |||||||||
| linouk23 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| ruoru | Rust | |||||||||
| shreymehul | C# | |||||||||
| suxrobGM | C# | |||||||||
| trung-hn | Python | |||||||||
| varunu28 | Java | |||||||||
| wisdompeak | C++ | |||||||||
| YuriSpiridonov | Python | |||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 530: Minimum Absolute Difference in BST
- problem 2040: Kth Smallest Product of Two Sorted Arrays
Solved On The Same Day
- problem 2529: Maximum Count of Positive Integer and Negative Integer
- problem 718: Maximum Length of Repeated Subarray
- problem 826: Most Profit Assigning Work
- problem 1237: Find Positive Integer Solution for a Given Equation
- problem 1283: Find the Smallest Divisor Given a Threshold
- problem 1552: Magnetic Force Between Two Balls
- problem 1561: Maximum Number of Coins You Can Get
- problem 1760: Minimum Limit of Balls in a Bag
- problem 1870: Minimum Speed to Arrive on Time
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