Optimize the code · Medium

Speed Up Pairs With Difference K

Medium Make it fast Seen at Amazon, Atlassian

countPairs(nums, k) returns the number of unique value pairs (a, b) from nums with b - a == k (where k >= 1). Pairs are counted by value, so duplicates in nums do not create extra pairs.

The nested-loop version below is correct but too slow for 60,000 values. Make it O(n) without changing the results.

Example 1

Input: nums = [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: The pairs are (1, 3) and (3, 5).

Example 2

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

Constraints

1 <= k

The slow code

Every case must finish within 300 ms (budgets are per language in the editor).

function countPairs(nums, k) {
  const pairs = new Set();
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (Math.abs(nums[i] - nums[j]) === k) {
        pairs.add(Math.min(nums[i], nums[j]) + ":" + Math.max(nums[i], nums[j]));
      }
    }
  }
  return pairs.size;
}

function countPairs(nums: number[], k: number): number {
  const pairs = new Set<string>();
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (Math.abs(nums[i] - nums[j]) === k) {
        pairs.add(Math.min(nums[i], nums[j]) + ":" + Math.max(nums[i], nums[j]));
      }
    }
  }
  return pairs.size;
}

def count_pairs(nums: list[int], k: int) -> int:
    pairs = set()
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if abs(nums[i] - nums[j]) == k:
                pairs.add((min(nums[i], nums[j]), max(nums[i], nums[j])))
    return len(pairs)

<?php

function countPairs(array $nums, int $k): int
{
    $pairs = [];
    $n = count($nums);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            if (abs($nums[$i] - $nums[$j]) === $k) {
                $pairs[min($nums[$i], $nums[$j]) . ':' . max($nums[$i], $nums[$j])] = true;
            }
        }
    }
    return count($pairs);
}

class Solution {
    public int countPairs(int[] nums, int k) {
        Set<String> pairs = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (Math.abs(nums[i] - nums[j]) == k) {
                    pairs.add(Math.min(nums[i], nums[j]) + ":" + Math.max(nums[i], nums[j]));
                }
            }
        }
        return pairs.size();
    }
}

Hints

Hint 1

For a value a, its only possible partner is a + k.

Hint 2

Put the distinct values in a set and test a + k for each.

Make it faster

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(n)

Why it is slow: comparing every pair is n(n-1)/2 checks, 1.8 billion for 60,000 values, plus building a string key for every match.

The fix: with k >= 1, a value a can only pair with a + k. Put the distinct values in a set and count the values a for which a + k is also in the set. Each pair is counted exactly once, from its smaller value. O(n).

Optimized solution

function countPairs(nums, k) {
  const values = new Set(nums);
  let count = 0;
  for (const a of values) if (values.has(a + k)) count++; // each pair counted from its smaller value
  return count;
}

function countPairs(nums: number[], k: number): number {
  const values = new Set(nums);
  let count = 0;
  for (const a of values) if (values.has(a + k)) count++; // each pair counted from its smaller value
  return count;
}

def count_pairs(nums: list[int], k: int) -> int:
    values = set(nums)
    return sum(1 for a in values if a + k in values)  # each pair counted from its smaller value

<?php

function countPairs(array $nums, int $k): int
{
    $values = array_flip($nums);
    $count = 0;
    foreach ($values as $a => $_) {
        if (isset($values[$a + $k])) {
            $count++; // each pair counted from its smaller value
        }
    }
    return $count;
}

class Solution {
    public int countPairs(int[] nums, int k) {
        Set<Integer> values = new HashSet<>();
        for (int x : nums) values.add(x);
        int count = 0;
        for (int a : values) if (values.contains(a + k)) count++; // each pair counted from its smaller value
        return count;
    }
}

Common mistakes

Counting duplicates twice: iterate over the distinct values.
Checking both a + k and a - k, which counts every pair twice.

Follow-up questions

What changes when k can be 0? (count values that appear at least twice)
Sorted input with O(1) extra space: two pointers.

Speed Up Contains Duplicate · Easy
Speed Up Two Sum · Easy
Speed Up Recursive Fibonacci · Easy
Speed Up the Most Frequent Word · Easy
Speed Up the Active-Customer Join · Easy
Speed Up Range Sum Queries · Medium