Count Triplets

  • + 0 comments

    Simple Typescript solution with partitioning

    function countTriplets(arr, r) {
        const valuesAfterCurrent = new Map()
        arr.forEach((v) => {
            const count = valuesAfterCurrent.get(v) ? valuesAfterCurrent.get(v) + 1 : 1
            valuesAfterCurrent.set(v, count)
        }) //all here initially
        
        const valuesBeforeCurrent = new Map() //empty initially
        
        const res = arr.reduce((tripletsFound, currentValue) => {
            valuesAfterCurrent.set(currentValue, valuesAfterCurrent.get(currentValue) - 1)
            
            const frequencyOfFirstsOfTriple = valuesBeforeCurrent.get(currentValue / r) ?? 0
            const frequencyOfThirdsOfTriple = valuesAfterCurrent.get(currentValue * r) ?? 0
             
            const count = valuesBeforeCurrent.get(currentValue) ? valuesBeforeCurrent.get(currentValue) + 1 : 1
            valuesBeforeCurrent.set(currentValue, count)
            
            return tripletsFound + (frequencyOfFirstsOfTriple * frequencyOfThirdsOfTriple) //if any of the freq is zero it will not increase the current triplets found value
        }, 0) 
        
        return res
    }