Count Triplets Problem

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.