K difference Pairs in an Array LeetCode

Given an array, find the pair of entries that have difference k.

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
• |nums[i] - nums[j]| == k

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

 Example 1:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

Input: nums = [1,2,3,4,5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

Input: nums = [1,3,1,5,4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Example 4:

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

Example 5:

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

Constraints:

• 1 <= nums.length <= 104
• -107 <= nums[i] <= 107
• 0 <= k <= 107

This is an interesting problem that is also discussed in Page1, LeetCode and several other forums such as Page2, Page3 A collection of hundreds of interview questions and solutions are available in our blog at Interview Question

Solution

	import java.io.*;
	import java.util.*;
	import java.text.*;
	import java.math.*;
	import java.util.regex.*;
	public class Solution {
	static int pairs(int[] a,int k) {
	//two pointer technique
	for(int i = 0;i<a.length; i++){
	int start = i, end = a.length-1;
	while(start<end && (a[start] +k <a[end])){
	end--;
	}
	if(a[start] + k ==a[end]){
	pairsCount++;
	}
	}
	//System.out.println(Arrays.toString(a));
	return pairsCount;
	}
	public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	int res;
	String n = in.nextLine();
	String[] n_split = n.split(" ");
	int _a_size = Integer.parseInt(n_split[0]);
	int _k = Integer.parseInt(n_split[1]);
	int[] _a = new int[_a_size];
	int _a_item;
	String next = in.nextLine();
	String[] next_split = next.split(" ");
	for(int _a_i = 0; _a_i < _a_size; _a_i++) {
	_a_item = Integer.parseInt(next_split[_a_i]);
	_a[_a_i] = _a_item;
	}
	res = pairs(_a,_k);
	System.out.println(res);
	}
	}

view raw ArrayDifference.java hosted with ❤ by GitHub