Problem 532

Abstract / Summary

Count pairs of numbers in an array that have exactly k difference between them.

Note

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

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 ])
14 lines | 438 bytes | submitted November 24, 2023 | GitHub   7% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 46% (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 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).

written by openai gpt

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.

written by google gemini

Code Quality

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

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++ 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++
41 links | 27 authors | 9 languages

Videos

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

Similar Problems

2 similar problems

Solved On The Same Day

10 solutions   November 24, 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