k_diff challenge in Java

Question

Puzzle Description

Given \$N\$ numbers, \$N <= 10^5\,ドル count the total pairs of numbers \$(N_i, N_j)\$ that have a difference of \$K = N_i - N_j\$ where \0ドル < K < 10^9\$.

Input Format:

• 1st line contains \$N\$ and \$K\$ (integers).

• 2nd line contains \$N\$ numbers of the set. All the \$N\$ numbers are assured to be distinct.

Output Format:

• One integer saying the number of pairs of numbers that have a difference \$K\$.

Time limit is 5 seconds.

Sample Input : 5 2 
 1 5 3 4 2
Sample Output: 3

First I've tried using ArrayLists and later tried using arrays. The code is bad and does not at all follow normal conventions of Java. But I'm not looking at that because execution time doesn't depend on it, right?

But to achieve the puzzle description I couldn't see any better logic than this:

import java.util.Scanner;
public class k_diff {
 public int process() {
 Scanner scanner = new Scanner(System.in);
 int total_nums = scanner.nextInt();
 int diff = scanner.nextInt();
 int ary_nums[] = new int[total_nums];
 for (int i = 0; i < total_nums; i++) {
 ary_nums[i] = scanner.nextInt();
 }
 int len = ary_nums.length;
 int count = 0;
 for (int j = 0; j < len - 1; j++) {
 for (int k = j + 1; k < len; k++) {
 if (Math.abs(ary_nums[j] - ary_nums[k]) == diff) {
 count++;
 }
 }
 }
 return count;
 }
 public static void main(String args[]) {
 k_diff kdiff = new k_diff();
 System.out.println(kdiff.process());
 }
}

• Michael K: What is N and K in your sample?
• cypronmaya: First two nums - 5(N) 2(K)

Answer 1

Some things which just jump into my eyes (even if not asked, I'll tell you anyway):

• Whitespaces: Use whitespaces were appropriate, f.e. for(int i=0;i<nums;i++) is harder to rad then for(int i = 0; i < nums; i++).
• Meaningful names: Name your variables after what they are, not what type they are. This especially includes simple for loops. It might be taught or standard to use i, but I consider it bad practice because you never know what exactly i is at first glance. Give your variables meaningful names, please, they deserve love too! Same goes for your classes.
• Split up where appropriate: if you've got only one function (main) you're most likely doing something wrong. Split it into Input, Processing and Output.

Answer 2

Other than comparing the numbers as they are given (in order), sorting them and comparing would take fewer cycles and run much faster.

So the above code can be optimized to this:

Arrays.sort(ary_nums);
for (int i = total_nums - 1; i > 0; i--) {
 for (int j = i - 1; j >= 0; j--) {
 if (ary_nums[i] - ary_nums[j] == diff) {
 count++;
 j = 0;
 }
 }
}

• David G.: This is still an \$O(n^2)\$ loop. The optimized form needs a single loop decreasing either i or j as appropriate.