2
\$\begingroup\$

Problem

Adapted from this HackerRank Problem.

Given N integers, count the number of pairs of integers whose difference is K.

Approach

  1. Given the initial int array, sort it.
  2. Now iterate through the indices in the array using a lower index (starting at 0) and an upper index (starting at 1)`.
  3. Calculate the difference between the value at the upper index value and the value at the lower index.
    1. If the difference is equal to the target difference, increment the count and increment the upper index.
    2. If the difference is less than the target difference, increment the upper index. A difference less than the target difference implies that the value at the upper index is not large enough.
    3. If the difference is greater than the target difference, increment the lower index. A difference greater than the target implies that the value at the lower index is not large enough.
  4. Return the count

Implementation

public class PairDifferenceCounter {
    public static int countPairsWithDifference(int[] values, int difference) {
        Arrays.sort(values);

        int count = 0;
        int lowerIndex = 0;
        int upperIndex = 1;

        while (upperIndex < values.length) {
            int pairDifference = values[upperIndex] - values[lowerIndex];

            if (pairDifference == difference) {
                count++;
                upperIndex++;
            } else if (pairDifference > difference) {
                lowerIndex++;
            } else {
                upperIndex++;
            }
        }

        return count;
    }
}
\$\endgroup\$
  • \$\begingroup\$ When you get a match I think you can increment both unless you have duplicates. \$\endgroup\$ – paparazzo Aug 21 '17 at 15:54
  • 1
    \$\begingroup\$ What if you call countPairsWithDifference({ 0, 1, 2, 3 }, -1111111)? Won't the program crash with an out of bounds error? \$\endgroup\$ – mdfst13 Aug 21 '17 at 16:16
  • \$\begingroup\$ @mdfst13 right you are! I think the simplest way to avoid this error is to change the while loop like so while (upperIndex < values.length && lowerIndex < upperIndex) \$\endgroup\$ – Jae Bradley Aug 21 '17 at 16:21
  • \$\begingroup\$ Should the numbers in a found pair be used up? For example: countPairsWithDifference({1, 3, 3, 3}, 2) is this 1 pair? or should it count as 3 pairs? \$\endgroup\$ – Imus Aug 21 '17 at 18:20
  • \$\begingroup\$ @Imus I'm interpreting that this should be 3 pairs. \$\endgroup\$ – Jae Bradley Aug 22 '17 at 12:59
1
\$\begingroup\$

Your solution looks good already. I can only really give 2 small pointers.

The first is based on mdfst13's comment. You don't do any checks on the input parameters. Since it's for a programming challenge for which we can safely assume correct inputs this is somewhat fine. Although it would probably be better to at least add a comment block on top of the method stating those limitations.

Alternatively you could also check for unwanted inputs at the start of the method and throw a relevant exception. (For example IllegalArgumentException). You can still add a method comment on top to mention those.

Another way is to first sanitise the input parameters with the most logical correction. For example:

if(values == null) {
    values = new int[0];
}
if(difference < 0){
    differences *= -1;
}

That way, even if someone calls the method with invalid input parameters, the program will not crash. This kind of solution is great if you want to have a process running automatically for a long time without looking at it anymore, and don't care if some cases are handled "wrong"(/perfectly right?). The biggest disadvantage is that you don't know if an input is "corrected", so if it should have been handled differently it would be really hard to detect afterwards.


The second small pointer is that your class and method name remind me of this picture: the world seen by an object-oriented programmer

Since your class just has 1 method, naming it is obviously going to be tricky. I would just keep the Solution as classname like they usually do in hackerrank.

If you do keep the class name, I would at least change the method name. Now you repeat yourself if you call it: PairDifferenceCounter.countPairsWithDifference(someList, difference);

It reads a bit easier if you used something like this: PairDifferenceCounter.count(someList, differene).

Perhaps rename both into something like this: ExtendedListUtils.countPairs(someList, difference); Which isn't perfect either since it might not be immediatly obvious that it counts the number of pairs with a given distance if you don't call it with a variable named "difference".


I want to stress out once more that these are only minor issues with the code. Well done!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.