Problem Description

You are given an integer array nums and an integer k. Your task is to count how many pairs of indices (i, j) exist where i < j and the absolute difference between the elements at these indices equals k.

In other words, you need to find all pairs where:

• The first index i comes before the second index j (i.e., i < j)
• The absolute difference |nums[i] - nums[j]| equals exactly k

The absolute value |x| is defined as:

• x if x >= 0
• -x if x < 0

For example, if nums = [1, 2, 2, 1] and k = 1, the valid pairs would be:

• (0, 1) because |1 - 2| = 1
• (0, 2) because |1 - 2| = 1
• (2, 3) because |2 - 1| = 1
• (1, 3) because |2 - 1| = 1

So the answer would be 4.

The solution uses a brute force approach by checking every possible pair (i, j) where i < j, calculating the absolute difference, and counting those pairs where the difference equals k. This is feasible because the array length is limited to at most 200 elements.

Intuition

Since we need to find pairs (i, j) where i < j and |nums[i] - nums[j]| == k, the most straightforward approach is to check every possible pair.

The key observation is that the array size is constrained to be relatively small (at most 200 elements). This means we can afford to check all possible pairs without worrying about time complexity. With n elements, there are n * (n-1) / 2 possible pairs to check, which for n = 200 gives us at most 19,900 comparisons - a manageable number for modern computers.

For each pair (i, j) where i < j, we simply:

1. Calculate the absolute difference between nums[i] and nums[j]
2. Check if this difference equals k
3. If yes, increment our counter

The nested loop structure naturally ensures we only consider pairs where i < j - the outer loop picks the first index i, and the inner loop starts from i + 1 to pick the second index j. This avoids counting the same pair twice and ensures we maintain the ordering constraint.

The solution leverages Python's generator expression with sum() to concisely count all valid pairs. The expression abs(nums[i] - nums[j]) == k evaluates to True (counted as 1) or False (counted as 0), and summing these boolean values gives us the total count of valid pairs.

Solution Approach

The solution implements a brute force enumeration approach to count all valid pairs.

Algorithm Steps:

1. Get the array length: Store n = len(nums) to know the bounds for our iteration.

2. Enumerate all pairs: Use two nested loops to generate all possible pairs (i, j) where i < j:

   • Outer loop: i ranges from 0 to n-1
   • Inner loop: j ranges from i+1 to n

3. Check each pair: For each pair (i, j), calculate abs(nums[i] - nums[j]) and check if it equals k.

4. Count valid pairs: Use Python's sum() function with a generator expression to count how many pairs satisfy the condition.

Implementation Details:

The code uses a compact one-liner with nested comprehensions:

sum(abs(nums[i] - nums[j]) == k for i in range(n) for j in range(i + 1, n))

This generator expression:

• Iterates through all i from 0 to n-1
• For each i, iterates through all j from i+1 to n-1
• Evaluates abs(nums[i] - nums[j]) == k which returns True (1) or False (0)
• Sums all the boolean values to get the total count

Time Complexity: O(n²) where n is the length of the array, as we check every pair exactly once.

Space Complexity: O(1) as we only use a constant amount of extra space for the counter and loop variables.

The beauty of this solution lies in its simplicity - since the problem constraints allow for a quadratic solution (small array size), we can avoid more complex approaches like hash maps or sorting, and directly count the pairs that satisfy our condition.

Example Walkthrough

Let's walk through the solution with nums = [3, 1, 4, 1, 5] and k = 2.

Step 1: Initialize

• Array length n = 5
• We need to find pairs where |nums[i] - nums[j]| == 2

Step 2: Enumerate all pairs where i < j

Let's check each pair systematically:

• i = 0 (nums[0] = 3):

  • j = 1: |3 - 1| = 2 ✓ (equals k, count it!)
  • j = 2: |3 - 4| = 1 ✗
  • j = 3: |3 - 1| = 2 ✓ (equals k, count it!)
  • j = 4: |3 - 5| = 2 ✓ (equals k, count it!)

• i = 1 (nums[1] = 1):

  • j = 2: |1 - 4| = 3 ✗
  • j = 3: |1 - 1| = 0 ✗
  • j = 4: |1 - 5| = 4 ✗

• i = 2 (nums[2] = 4):

  • j = 3: |4 - 1| = 3 ✗
  • j = 4: |4 - 5| = 1 ✗

• i = 3 (nums[3] = 1):

  • j = 4: |1 - 5| = 4 ✗

Step 3: Count valid pairs We found 3 valid pairs:

• (0, 1): |3 - 1| = 2
• (0, 3): |3 - 1| = 2
• (0, 4): |3 - 5| = 2

Result: 3

The solution code sum(abs(nums[i] - nums[j]) == k for i in range(n) for j in range(i + 1, n)) performs exactly this process - it generates each pair once, checks if the absolute difference equals k, and counts how many times this condition is true.

Solution Implementation

Time and Space Complexity

The time complexity is O(n^2), where n is the length of the array nums. This is because the code uses two nested loops - the outer loop runs from i = 0 to n-1, and for each i, the inner loop runs from j = i+1 to n-1. The total number of pairs checked is n*(n-1)/2, which simplifies to O(n^2).

The space complexity is O(1). The code only uses a constant amount of extra space for the loop variables i and j, and the generator expression is evaluated lazily without creating an intermediate list. The sum() function accumulates the result using constant space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Counting Pairs Twice by Not Enforcing i < j

The Pitfall: A frequent mistake is to use two nested loops that both iterate from 0 to n, leading to counting each pair twice and also comparing an element with itself:

# INCORRECT - counts pairs twice and includes i == j
count = 0
for i in range(n):
    for j in range(n):  # Wrong! Should start from i+1
        if abs(nums[i] - nums[j]) == k:
            count += 1

This would count the pair (i, j) and also (j, i) as separate pairs, and when i == j, it compares an element with itself.

The Solution: Always ensure the inner loop starts from i + 1 to maintain the constraint i < j:

# CORRECT - each pair counted exactly once
count = 0
for i in range(n):
    for j in range(i + 1, n):  # Correct! Starts from i+1
        if abs(nums[i] - nums[j]) == k:
            count += 1

2. Misunderstanding Absolute Difference

The Pitfall: Some might incorrectly check only one direction of the difference:

# INCORRECT - only checks nums[i] - nums[j], not the absolute value
if nums[i] - nums[j] == k:
    count += 1

This misses valid pairs where nums[j] > nums[i].

The Solution: Always use abs() or check both conditions:

# CORRECT - Option 1: Using abs()
if abs(nums[i] - nums[j]) == k:
    count += 1

# CORRECT - Option 2: Checking both directions explicitly
if nums[i] - nums[j] == k or nums[j] - nums[i] == k:
    count += 1

3. Off-by-One Error in Loop Boundaries

The Pitfall: Using incorrect loop boundaries that either miss pairs or cause index out of bounds:

# INCORRECT - misses the last element
for i in range(n - 1):
    for j in range(i + 1, n - 1):  # Wrong! Should go to n
        ...

# INCORRECT - potential index out of bounds
for i in range(n):
    for j in range(i + 1, n + 1):  # Wrong! Goes beyond array bounds
        ...

The Solution: Use the correct boundaries:

# CORRECT
for i in range(n):  # or range(n - 1) since last element has no pairs
    for j in range(i + 1, n):  # Goes up to n-1 (inclusive)
        ...