#2006

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Number of Pairs With Absolute Difference K

Find how many pairs (i, j) with i < j satisfy |nums[i] - nums[j]| == k using array scanning and hash lookup.

Problem Statement

Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums[i] - nums[j]| == k.

To solve this, we can utilize an array scanning approach alongside a hash table to track previously seen values, avoiding the need to check every possible pair directly.

Examples

Example 1

Input: nums = [1,2,2,1], k = 1

Output: 4

The pairs with an absolute difference of 1 are:

[1,2,2,1]
[1,2,2,1]
[1,2,2,1]
[1,2,2,1]

Example 2

Input: nums = [1,3], k = 3

Output: 0

There are no pairs with an absolute difference of 3.

Example 3

Input: nums = [3,2,1,5,4], k = 2

Output: 3

The pairs with an absolute difference of 2 are:

[3,2,1,5,4]
[3,2,1,5,4]
[3,2,1,5,4]

Constraints

1 <= nums.length <= 200
1 <= nums[i] <= 100
1 <= k <= 99

Solution Approach

Array Scanning with Hash Table

Iterate through the array while maintaining a hash table that tracks the counts of each element seen so far. For each element nums[i], check if nums[i] - k or nums[i] + k exists in the hash table. If it does, increase the count accordingly.

Efficient Pair Counting

The hash table allows for efficient lookup in constant time, making this approach optimal. Instead of checking every possible pair, we check each element and its potential pair in the hash table, ensuring that no unnecessary calculations are done.

Edge Case Handling

Handle cases where the array contains duplicates or where no valid pairs exist. Ensure that you do not double-count pairs and that you correctly handle when no pairs with the required absolute difference are found.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) where n is the length of the array, due to the linear scan and constant-time hash lookups. The space complexity is O(n) because we store each element in the hash table.

What Interviewers Usually Probe

Candidate efficiently uses a hash table for constant-time lookups.
Candidate demonstrates understanding of avoiding brute force pair checking.
Candidate handles edge cases like duplicates and missing pairs effectively.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the problem with nested loops.
Failing to manage hash table updates correctly, leading to double-counting.
Not handling edge cases like empty arrays or arrays without valid pairs.

Follow-up variants

Consider using a set for tracking seen numbers instead of a hash table.
Adapt the solution for cases where negative values are allowed in the array.
Optimize further if the array is guaranteed to be sorted.

FAQ

How does array scanning help in solving this problem?

Array scanning ensures that we only need to pass through the array once, making the solution efficient compared to checking all pairs directly.

Can I solve this without using a hash table?

While it's possible to use brute-force methods, they would be inefficient with time complexity O(n^2). A hash table significantly improves the time complexity to O(n).

How does GhostInterview assist with this problem?

GhostInterview offers a step-by-step breakdown of how to efficiently solve this problem, helping you understand the hash table-based approach and avoid common pitfalls.

What are the edge cases to consider in this problem?

Consider arrays with duplicates, arrays where no pairs meet the condition, and cases with a very small or large array size.

What if there are negative numbers in the array?

If negative numbers are allowed, the solution can be adapted by adjusting the conditions for pair matching to account for negative differences.

terminal

Solution

Solution 1: Brute Force Enumeration

We notice that the length of the array $nums$ does not exceed $200$, so we can enumerate all pairs $(i, j)$, where $i < j$, and check if $|nums[i] - nums[j]|$ equals $k$. If it does, we increment the answer by one.

1

2

3

4

5

6

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        n = len(nums)
        return sum(
            abs(nums[i] - nums[j]) == k for i in range(n) for j in range(i + 1, n)
        )

Solution 2: Hash Table or Array

We can use a hash table or array to record the occurrence count of each number in the array $nums$. Then, we enumerate each number $x$ in the array $nums$, and check if $x + k$ and $x - k$ are in the array $nums$. If they are, we increment the answer by the sum of the occurrence counts of $x + k$ and $x - k$.

1

2

3

4

5

6

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        n = len(nums)
        return sum(
            abs(nums[i] - nums[j]) == k for i in range(n) for j in range(i + 1, n)
        )

Continue Practicing

#2001 number of pairs of interchangeable rectangles #2013 detect squares #1994 the number of good subsets