k-diff pairs Editorial

Practice Problem Link: k-diff pairs

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a sorted array and a number k, return the number of unique pairs which have a difference of k.

|arr[i] - arr[j]| = k where i < j

Naive Approach

The naive approach is to iterate over all pairs of the array and check if the current pair has the required difference. Count number of such pairs.

Analysis

• Time Complexity: O(n²)
• Space Complexity: O(1)

Implementation

C++

int kDiffPairs(vector<int> A, int k) {
	int n = A.size();
	int result = 0;
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
			if(abs(A[i] - A[j]) == k) {
				result++;
			}
		}
	}
	return result;
}

Java

class Solution {
	int kDiffPairs (int[] A, int k) {
		int n = A.length;
		int result = 0;
		for(int i = 0; i < n; i++) {
			for(int j = i + 1; j < n; j++) {
				if(Math.abs(A[i] - A[j]) == k) {
					result++;
				}
			}
		}
		return result;
	}
}

Improved Solution

An improved solution is to use the technique of hashing. We will hash the elements till the current element, and check if the valid pair is found or not using our hash array. We will use another array to mark our used pairs to keep unique pairs only.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Implementation

C++

int kDiffPairs(vector<int> A, int k) {
	int n = A.size();
	int result = 0;
	unordered_map<int, int> hash;
	unordered_map<int, int> done;
	for(int i = 0; i < n; i++) {
		if(hash[A[i] - k] != 0 && hash[A[i]] == 0) {
			result += 1;
		}
		else if(k == 0) {
			if(hash[A[i]] == 1 && !done[A[i]]) {
				result += 1;
				done[A[i]] = 1;
			}
		}
		hash[A[i]]++;
	}
	return result;
}

Java

class Solution {
	int kDiffPairs (int[] A, int k) {
		int n = A.length;
		int result = 0, maxElement = Integer.MIN_VALUE;
		for(int i = 0; i < n; i++) {
			maxElement = Math.max(maxElement, A[i]);
		}
		int[] hash = new int[maxElement + 1];
		int[] done = new int[maxElement + 1];
		for(int i = 0; i < n; i++) {
			if(A[i] - k >= 0 && hash[A[i] - k] != 0 && hash[A[i]] == 0) {
				result += 1;
			}
			else if(k == 0) {
				if(hash[A[i]] == 1 && done[A[i]] == 0) {
					result += 1;
					done[A[i]] = 1;
				}
			}
			hash[A[i]]++;
		}
		return result;
	}
}

Optimal Solution

The optimal solution for this problem is to use the concept of 2 pointers. Note that the arrays is sorted. We keep two pointers i and j starting from the 0th index and the 1st index respectively. We find out the difference between the elements at the two indexes.

There could be three cases here:

• The difference is k: Consider the pair and increment both the indexes as none of them will create an unique pair with any other element.
• The difference is less than k: Increment j => This would increase the difference next time.
• The difference is greater than k: Increment i => This would decrease the difference next time.

To avoid duplicates, we can skip all j indexes where A[j] == A[j + 1] which basically means that we consider only the last element in a series of duplicates.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

int kDiffPairs(vector<int> &A, int k) {
    // add your logic here
    int n = A.size();
    int i = 0, j = 1;
    int count = 0;
    while (j < n) {
        while (j < (n - 1) && A[j] == A[j + 1]) {
            j++;
        }
        int diff = A[j] - A[i];
        if (diff == k) {
            count++;
            i++;
            j++;
        } else if (diff < k) {
            j++;
        } else {
            i++;
        }
		if (i == j) {
			j++;
		}
    }

    return count;
}

Java

class Solution {
    int kDiffPairs (int[] A, int k) {
        // add your logic here
        int n = A.length;
        int i = 0, j = 1;
        int count = 0;
        while (j < n) {
            while (j < (n - 1) && A[j] == A[j + 1]) {
                j++;
            }
            int diff = A[j] - A[i];
            if (diff == k) {
                count++;
                i++;
                j++;
            } else if (diff < k) {
                j++;
            } else {
                i++;
            }
			if (i == j) {
				j++;
			}
        }

        return count;
    }
}