K-diff Pairs in an Array - Practice Coding Problems

K-diff Pairs in an Array - Problem

Given an array of integers nums and an integer k, return the number of unique k-diff pairs in the array.

A k-diff pair is an integer pair (nums[i], nums[j]) where the following are true:

0 <= i, j < nums.length
i != j
|nums[i] - nums[j]| == k

Notice that |val| denotes the absolute value of val.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: There are two 2-diff pairs: (1,3) and (3,5). Note that we only count unique pairs, so (1,3) from different positions counts as one pair.

Example 2 — No Valid Pairs

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

› Output: 4

💡 Note: Valid pairs are (1,2), (2,3), (3,4), and (4,5). Each consecutive pair has difference 1.

Example 3 — Duplicate Elements

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

› Output: 1

💡 Note: For k=0, we need identical pairs. Only the number 1 appears more than once, giving us one unique pair (1,1).

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁷ ≤ nums[i] ≤ 10⁷
0 ≤ k ≤ 10⁷

Visualization

Tap to expand

Understanding the Visualization

Input

Array of integers and target difference k

Process

Find all pairs where |a - b| = k

Output

Count of unique k-diff pairs

Key Takeaway

🎯 Key Insight: Use hash map or sorting to avoid O(n²) brute force comparison

Asked in

a Amazon 25 G Google 18 M Microsoft 12 f Facebook 8

The key insight is to avoid checking all pairs by using a hash map or sorted two-pointer approach. Hash map approach provides O(n) time by checking if each number's complement (num+k) exists. Best approach is hash map with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Pairs	O(n²)	O(n)	Check every possible pair and count unique k-diff pairs
Hash Map - O(n) Lookup	O(n)	O(n)	Use hash map to find complement values in O(1) time
Two Pointers After Sorting	O(n log n)	O(1)	Sort array and use two pointers to find k-diff pairs efficiently

Brute Force - Check All Pairs — Algorithm Steps

For each element i, check all elements j where i ≠ j
If |nums[i] - nums[j]| == k, add the sorted pair to a set
Return the size of the set

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare All Pairs

Check each element against every other element

Find Valid Pairs

Identify pairs where |a - b| = k

Count Unique

Store unique pairs to avoid duplicates

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int k) {
    char uniquePairs[10000][20];
    int pairCount = 0;
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < numsSize; j++) {
            if (i != j && abs(nums[i] - nums[j]) == k) {
                int a = nums[i], b = nums[j];
                if (a > b) { int temp = a; a = b; b = temp; }
                
                char pairStr[20];
                sprintf(pairStr, "%d,%d", a, b);
                
                int found = 0;
                for (int p = 0; p < pairCount; p++) {
                    if (strcmp(uniquePairs[p], pairStr) == 0) {
                        found = 1;
                        break;
                    }
                }
                
                if (!found) {
                    strcpy(uniquePairs[pairCount], pairStr);
                    pairCount++;
                }
            }
        }
    }
    
    return pairCount;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* ptr = line + 1;
    char* token = strtok(ptr, ",]");
    while (token) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops check all n×n pairs

⚠ Quadratic Growth

Space Complexity

O(n)

Set stores up to n unique pairs

⚡ Linearithmic Space

67.0K Views

Medium Frequency

~25 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler