HackerRank

Every so often, I grab a HackerRank problem in an attempt to learn something new. I recently tried the Count Triplets challenge. As is normal for me with HackerRank problems, the biggest issue was figuring out what the author was after.

Here was my initial code:

function countTriplets(arr, r) {
    let numbers = new Map();

    for(let i=0; i<arr.length; i++) {
        addToHash(numbers, arr, i);  
    }

    let triplets = 0;
    for(let i=0; i<arr.length; i++) {
        let number = arr[i];
        let secondNumber = (number * r);
        let thirdNumber = (number * r * r);

        let secondNumberLocations = numbers.get(secondNumber);
        let thirdNumberLocations = numbers.get(thirdNumber);

        if(secondNumberLocations && thirdNumberLocations) {
            triplets += secondNumberLocations.length * thirdNumberLocations.length;
        }
    }

    return triplets;
}

function addToHash(numbers, arr, index) {
    let locations = numbers.get(arr[index])
        if(!locations) {
            numbers.set(arr[index], [index]);
        } else {
            locations.push(index);
            numbers.set(arr[index], locations);
        }
}

It did exactly what I wanted it to, and returned the number of unique trios of indices that when up by a multiple of ‘r’. Unfortunately, it only passed 8/13 test cases.

As it turned out, they only wanted a match when the numbers in the indices were in order from smallest to largest.

This was my next attempt, which worked, but was too slow to complete one of the tests in the allotted time:

function countTriplets(arr, r) {
    let numbers = new Map();

    let triplets = 0;

    for(let i=0; i<arr.length; i++) {
        const number = arr[i];
        let numberArray = numbers.get(number.toString()); //Number in Map already?

        //Need to get all of the next smallest in sequence already in the Map
        //Lets us count matches and update Map with correct info for number
        let numberFraction = number / r; /*Next smallest in sequence*/
        let numberFractionArray = numbers.get(numberFraction.toString());

        //Do the counting
        if(numberFractionArray) { //potential exists for triplet
            for(let j=0; j<numberFractionArray.length; j++) {
                triplets += numberFractionArray[j].fractionCount;
            }
        }

        //Generate a numberArray object for addition to Map
        let numberArrayObject;
        if(numberFractionArray) {
            numberArrayObject = {
                index: i,
                fractionCount: numberFractionArray.length
            }
        } else {
            numberArrayObject = {
                index: i,
                fractionCount: 0
            }
        }

        //Add current number info to Map so that it can be used by a higher multiple
        if(!numberArray) { //Add for first time
            numbers.set(number.toString(), [numberArrayObject]);
        } else { //Add the new item to the existing array
            numberArray.push(numberArrayObject)
            numbers.set(number.toString(), numberArray);
        }
    }

    return triplets;
}

The above, second version only goes through the initial array one time, but when it finds a number that works as the largest or middle value in the triplet, the execution has to go through the entire array stored on the next number down in the sequence.

This was more or less instinctive for me. I have a tendency to grab hold of any data that comes through under the theory that I’ll probably need it later, but strictly speaking, I don’t need it to comply with the requirements of this particular exercise.

My third version of the code doesn’t try to story any kind of detailed data, instead grabbing summary totals and putting them into the map at each step.

function countTriplets(arr, r) {
    let numbers = new Map();

    let triplets = 0;

    for(let i=0; i<arr.length; i++) {
        const number = arr[i];
        let numberObject = numbers.get(number.toString()); //Number in Map already?

        /* {
            count: x,
            subcount: y
        } */

        //Need to get the value of the next smallest in sequence already in the Map
        //Lets us count matches and update Map with correct info for number
        let numberFraction = number / r; /*Next smallest in sequence*/
        let numberFractionObject = numbers.get(numberFraction.toString());

        //Subcount semi problematic. Need to increment numberObject
        //But only if numberFractionObject exsits
        let additionalSubcount = 0; //Assume 0. Change if numberFractionObject exists

        //Increase Triplets where appropriate
        if(numberFractionObject) {
            triplets += numberFractionObject.subcount;
            additionalSubcount = numberFractionObject.count;
        }

        //Add current number info to Map so that it can be used by a higher multiple
        if(!numberObject) { //Add for first time
            numbers.set(number.toString(), {
                count: 1,
                subcount: additionalSubcount
            });
        } else { //Add the new item to the existing array
            numberObject.count++;
            numberObject.subcount+= additionalSubcount
            numbers.set(number.toString(), numberObject);
        }
    }

    return triplets;
}

My solution is O(n), and the space required is likely to come in around 2n. If there are no duplicates, and no triplets, then it would just be a hash table of size n. If there were no duplicates and everything came back as a triplet, then the size would be 3n because you’d store each item and have two additional data points next to it.

If you have a bunch of duplicates that all come down to the same triplet, then you’d need space of 9 (3 triplets with 3 data points each).

In looking at the editorial on HackerRank and the solution there, the solution requires space of 3n, and they are claiming complexity of O(nlogn), but it looks to me like they are going through the list twice, which would in theory mean that it’s O(2n) which would reduce down to O(n), but my algorithm should be roughly twice as fast.

Hacker Rank problems can be fun, and I often find myself learning something interesting. I recently undertook the Divisible Sum Pairs problem.

In short, given an array of integers ar, and an integer k, find how many pairs of integers add up to a multiple of k.

The trivial solution is just a double for-loop that has an O(n^2) run-time.

I often find that by the time I’m done reading through the Hacker Rank problems and go start working through the actual code to solve the problem, that I’ve let a key detail slip. Such was the case this time, and my original solution found the total of the pairs of integers that added up to k rather than a multiple of k.

Because of that, my initial implementation used a hash table, and I decided to try and expand out my initial hash table solution to deal with multiples. Here is my solution:

function divisibleSumPairs(n, k, ar) {
     let myMap = new Map();
     let pairs = 0;
     let biggestValue = ar[0];

     for(let i=0;i<ar.length;i++) {
          let maxLookingFor = ar[i] + biggestValue;
          let iterations = Math.ceil(maxLookingFor/k);
               for(let j=1; j<=iterations;j++) {
                    let lookingFor = k*j-ar[i];
                    const mapValue = myMap.get(lookingFor)
                    if(mapValue) {
                         pairs += mapValue;
                    }
               }

               if(ar[i] > biggestValue) {
                    biggestValue = ar[i];
               }

               const mapValue = myMap.get(ar[i]);

               if(mapValue) {
                    myMap.set(ar[i], mapValue + 1);
               } else {
                    myMap.set(ar[i], 1);
               }
          }

     return pairs;
}

Here is the least efficient:

function divisibleSumPairs(n, k, ar) {
     let pairs = 0;
     for(let i=0;i<ar.length;i++) {
          for(let j=i+1;j<ar.length;j++) {
               let sum = ar[i] + ar[j];
                    if(!(sum%k)) { //!sum%k does !sum then %k's the !sum
                         pairs++;
                    }
          }
     }
     return pairs;
}

Here’s the most efficient solution:

function divisibleSumPairs(n, k, ar) {
     let numbers = [];
     for(let i=0;i<k;i++) {          numbers.push([]);     }
     for(let i=0;i<ar.length;i++) {          let remainder = ar[i]%k;          numbers[remainder].push(ar[i]);     }
     let count;
      //populate the zero row     let zeroQuantity = numbers[0].length;
     count = (zeroQuantity * (zeroQuantity -1)) / 2;
     let j = k -1;
      //populate the remaining rows
     for(let i=1; i<=j;i++) {
          if(i == j) {
               //remainders add to k
               let middleRowQuantity = numbers[i].length;
               count += (middleRowQuantity * (middleRowQuantity - 1)) / 2;
          } else {
               //remainder is exactly half k 
               count += numbers[i].length * numbers[j].length;
          }
          j--;
     }
     return count;
}

As k gets smaller, the range of numbers gets bigger, and the length of the array ar gets smaller, the ‘worst’ alogorithm will tend to do better compared to my solution. As k gets larger, the range of numbers gets smaller, and the size of the array gets larger, then my solution will tend to perform better.

The most efficient solution is obviously better than either of the other two. If we were talking a problem where the range of numbers in the array was very small, or the range was very small until the last step, k was very large, and we needed the pairs returned, then it’s possible that the generation of the pairs at the end of the efficient solution could take longer than my solution, but that’s a pretty extreme, narrow kind of edge case.

If I ever run into a similar problem in the wild, I’ll now know how to approach it thanks to the commenters in the discussion section on Hacker Rank.

Tag: HackerRank

Count Triplets Problem

Divisible Sum Pairs (HackerRank Problem)