Count Number of Teams - Javascript

Question

I'm trying to solve the problem below in JavaScript.

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]). A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n). Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

Example:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). 

My idea is to keep an array of possible combinations, when I reach 3 elements in the combinations, I increment my res variable. My attempt:

var numTeams = function(rating) {
    let res = 0;
    if(!rating || rating.length < 3)  return res;
    
    let combinations = [];
    for(let i=0; i<rating.length; i++) {
        const size = combinations.length;
        for(let j=0; j<size; j++) {
            const temp = combinations[j];
            if(temp.length === 1 && temp[0] !== rating[i]) {
                temp.push(rating[i]);
                combinations.push(temp);
            } else {
                if(temp[0] < temp[1] && temp[1] < rating[i])
                    res++;
                else if(temp[0] > temp[1] && temp[1] > rating[i])
                    res++;
            }
        }
        combinations.push([rating[i]]);
    }
    
    return res;
};

It is returning 2 for the example input, not 3.

Answer 1

For better performance compared to the three for loops provided in answer https://stackoverflow.com/a/64921918/9240674, i also iterate over the rating array only once now. An array variations holds all variations that may become a valid combination. The entries consist of the function which is used to determine whether the variation is a valid combination and the ratings. With each iteration over the rating array, the new rating[i] is checked against all variations if it might complete the currently checked variation to become a valid combination. If so, the ratings of the current variation[k] are stored in combinations array.

var rating = [2,5,3,4,1];
var variations = [];
var combinations = [];

function less_than(a, b) {
  return a < b;
}

function greater_than(a, b) {
  return a > b;
}

for (i = 0; i < rating.length; i = i + 1) {
    var duplications = [];
    for (k = 0; k < variations.length; k = k + 1) {
        if (variations[k].ratings.length < 3) {
            if (variations[k].comparemethod(rating[i],variations[k].ratings[variations[k].ratings.length-1])) {
                // Duplicate current (incomplete) variation
                duplications.push({"comparemethod": variations[k].comparemethod, "ratings": variations[k].ratings.slice()});
                // Add the current rating to the current variation
                variations[k].ratings.push(rating[i]);
            }
            if (variations[k].ratings.length == 3) {
                // we found a valid combination
                combinations.push(variations[k].ratings);
            }
        }
    }
    // add entries which needed to be duplicated to the variations
    variations = variations.concat(duplications);
    // add the current rating to the variations
    variations.push({comparemethod: less_than,    ratings: [rating[i]]});
    variations.push({comparemethod: greater_than, ratings: [rating[i]]});
}


console.log(JSON.stringify(combinations));
console.log(combinations.length);

Output:

[[2,3,4],[5,3,1],[5,4,1]]
3

Answer 2

I suggest to use three encapsulated for loops. By initializing the indexes with the value of the current value of the index of the outer loop, e.g. k = i, the condition (0 <= i < j < k < n) is implicitly fulfilled. Within the innermost loop, you can then check if the conditions to be a combination is true for the current set of soldiers by checking if rating[i] < rating[k] && rating[k] < rating[l] or rating[i] > rating[k] && rating[k] > rating[l] and add the values to the array holding the valid combinations. At the end, the length of the array holding the valid combinations is printed:

var rating = [2,5,3,4,1];
var combinations = [];


for (i = 0; i < rating.length; i = i+1) {
    for (k = i; k < rating.length; k = k+1) {
        for (l = k; l < rating.length; l = l+1) {
            if (rating[i] < rating[k] && rating[k] < rating[l]) {
                combinations.push([rating[i], rating[k], rating[l]]);
            }
            if (rating[i] > rating[k] && rating[k] > rating[l]) {
                combinations.push([rating[i], rating[k], rating[l]]);
            }
        }
    }
}

console.log(combinations);
console.log(combinations.length);

Output:

[ [ 2, 3, 4 ], [ 5, 3, 1 ], [ 5, 4, 1 ] ]
3