Count Pairs With Difference K
Easy About 10 min Free, no account needed
Count the pairs of indices whose values differ by exactly k.
The brief
Given an integer array nums and a positive integer k, count the number of
pairs of indices (i, j) with i < j where |nums[i] - nums[j]| == k.
- Pairs are counted by index, so duplicate values produce multiple pairs.
The obvious approach compares every pair, O(n2). The hidden test uses 200,000 elements, so twenty billion comparisons are far too slow. You need an approach that scales better than checking every pair.
Starter code
using System;
public class Solution
{
// TODO: return the count of index pairs (i < j) whose values differ by exactly k.
public long CountPairsWithDiff(int[] nums, int k)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Hash maps and sets
- Trade memory for constant-time lookups, membership tests and frequency counts.
Related katas
- Contains Duplicate Easy Free Decide whether an array contains any repeated value.
- Count Distinct Letters Easy Free How many different letters appear? A 26-slot array already knows.
- Isomorphic Strings Easy Free Can one string be turned into the other by a consistent character substitution?
- Majority Element Easy Free Find the element that appears more than half the time.