java - pairs of numbers that have a difference of K -

java - pairs of numbers that have a difference of K -

this online interview question, , submitted answer. however, compilation terminated due time submitted. feedback you? in advance.

problem:

given n numbers , [n<=10^5] need count total pairs of numbers have difference of k

input format:

1st line contains n & k (integers). 2nd line contains n numbers of set. n numbers assured distinct.

output format:

one integer saying no of pairs of numbers have diff k.

sample input #00:

5 2 1 5 3 4 2

sample output #00:

3

my code:

import java.io.* import java.util.*; public class diffnumbers { public static void main(string[] args) throws exception { bufferedreader in = new bufferedreader(new inputstreamreader(system.in)); string line1 = in.readline(); string line2 = in.readline(); int n = integer.parseint(line1.split(" ")[0]); int diff = integer.parseint(line1.split(" ")[1]); hashtable table = new hashtable(); int[] arr = new int[n]; for(in i=0; i<n; i++) { arr[i] = integer.parseint(line2.split(" ")[i]); table.put(integer.parseint(line2.split(" ")[i])); } int count = 0; for(in i=0; i<n; i++) { if(table.containskey(arr[i]+diff) { count++; } } system.out.println(count); } }

using hashmap/table needs space. if want avoid can way

1) sort array

2) initialize outputcount 0

3) allow there 2 pointers. "first" start 0 , "other" pointer start 1.

4)

while(arr[other]-arr[first] <requireddifference) other ++; if(arr[other]-arr[first] == requireddifference) outputcount++; else // no match arr[first] first++;

5)

return outputcount;

explanation :- when difference more requireddifference stop moving ahead "other" poiner. there no match arr[first]. move ahead first counter. same logic new arr[first]. time go on checking current position of "other" array sorted; lower number not have required match.

java hashmap hashtable