Optimizing this C# algorithm (K Difference)

Question

This is the problem I'm solving (it's a sample problem, not a real problem):

Given N numbers , [N<=10^5] we need to count the total pairs of numbers that have a difference of K. [K>0 and K<1e9]

Input Format: 1st line contains N & 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 no of pairs of numbers that have a diff K.

Sample Input #00:
5 2
1 5 3 4 2
Sample Output #00:
3
Sample Input #01:
10 1
363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793 
Sample Output #01:
0

I already have a solution (and I haven't been able to optimize it as well as I had hoped). Currently my solution gets a score of 12/15 when it is run, and I'm wondering why I can't get 15/15 (my solution to another problem wasn't nearly as efficient, but got all of the points). Apparently, the code is run using "Mono 2.10.1, C# 4".

So can anyone think of a better way to optimize this further? The VS profiler says to avoid calling String.Split and Int32.Parse. The calls to Int32.Parse can't be avoided, although I guess I could optimize tokenizing the array.

My current solution:

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace KDifference
{
   class Solution
   {
      static void Main(string[] args)
      {
         char[] space = { ' ' };

         string[] NK = Console.ReadLine().Split(space);
         int N = Int32.Parse(NK[0]), K = Int32.Parse(NK[1]);

         int[] nums = Console.ReadLine().Split(space, N).Select(x => Int32.Parse(x)).OrderBy(x => x).ToArray();

         int KHits = 0;

         for (int i = nums.Length - 1, j, k; i >= 1; i--)
         {
            for (j = 0; j < i; j++)
            {
               k = nums[i] - nums[j];

               if (k == K)
               {
                  KHits++;
               }
               else if (k < K)
               {
                  break;
               }
            }
         }

         Console.Write(KHits);
      }
   }
}

Answer 1

Your algorithm is still O(n^2), even with the sorting and the early-out. And even if you eliminated the O(n^2) bit, the sort is still O(n lg n). You can use an O(n) algorithm to solve this problem. Here's one way to do it:

Suppose the set you have is S1 = { 1, 7, 4, 6, 3 } and the difference is 2.

Construct the set S2 = { 1 + 2, 7 + 2, 4 + 2, 6 + 2, 3 + 2 } = { 3, 9, 6, 8, 5 }.

The answer you seek is the cardinality of the intersection of S1 and S2. The intersection is {6, 3}, which has two elements, so the answer is 2.

You can implement this solution in a single line of code, provided that you have sequence of integers sequence, and integer difference:

int result = sequence.Intersect(from item in sequence select item + difference).Count();

The Intersect method will build an efficient hash table for you that is O(n) to determine the intersection.