Leetcode diary: 1395. Count Number of Teams [DP problem]

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

This one was fucking impossible for me, I encourage you to do it if you are new to DP.

The brute force solution is the easy part, almost too easy. You just use triple nested loop:

var numTeams = function(rating) {
    const teams = [];
    rating.forEach(function(num, index){
        for (let i=index+1; i<rating.length; i++) {
            const iElem = rating[i];

            for (let j=i+1; j<rating.length; j++) {
                const jElem = rating[j];

                if(num > iElem && iElem > jElem) {
                    teams.push([num, iElem, jElem])
                }
                if(num < iElem && iElem < jElem) {
                    teams.push([num, iElem, jElem])
                }

            }
        }
    })

    return teams.length;
};

This is O(N^3) so obviously it did not pass the submission, but it did pass several tests so we know it's at least reasonable.

Then I started a rabbit hole into how to get just SOMETHING memoized. So I started writing a recursive function which did not turn out well cause recursion can only go in one direction (all greater than or all less than). I even added backtracking that I've picked up from previous problem discussion techniques, but to no success:

var numTeams = function(rating) {
    const teams = new Set();
    const length = rating.length;
    rating.forEach(function(_, index){
        recurr(index, []);
    })


    function recurr(index, currentTeam){
        if(currentTeam.length === 3) {
            teams.add(currentTeam.join(''));
            return;
        }

        if(index > length-1) {
            return;
        }        

        if(!currentTeam.length || currentTeam[currentTeam.length-1] > rating[index]) { 
            currentTeam.push(rating[index]); 
            recurr(index+1, currentTeam);
            currentTeam.pop();
        } 

        recurr(index+1, currentTeam);
    }
    return teams.size;
}

I was hard stuck after this point because I was thinking that I needed to do something like:
1.) making the recursion work for both directions //no way
2.) sort something maybe will give me some new additional information //it does, but nothing that would come together nicely
3.) figure something out that could remove at least one loop, so I needed to do something with just a pair number matching //this was it but I couldn't figure out how.
4.) something math something something //NOPE!
5.) Two pointers? left iteration right iteration ? sliding window ?idk...

After spending 2 hours on one stupid fucking question, I gave up and decided to look at the solution. The one solution that I liked the most is this:

const numTeams = rating => {
  let ans = 0;

  // 'i' is the index of Middle
  for (let i = 1; i < rating.length - 1; i++) {
    let descLeft = 0;
    let descRight = 0;
    let ascLeft = 0;
    let ascRight = 0;

    // Check for Left
    for (let j = 0; j < i; j++) {
      if (rating[j] > rating[i]) descLeft++;
      if (rating[j] < rating[i]) ascLeft++;
    }

    // Check for Right
    for (let j = i + 1; j < rating.length; j++) {
      if (rating[j] < rating[i]) descRight++;
      if (rating[j] > rating[i]) ascRight++;
    }

    ans += descLeft * descRight + ascLeft * ascRight;
  }

  return ans;
};

This one is worth discussing. The breakthrough idea was stop thinking the first for loop as the beginning of the iteration, rather at the middle. This was extremely helpful as it allows you to pair match numbers and draw accurate conclusions from it, like I was thinking in number 3.

let's say for i = 10. we iterate to the left of the array, if there is any number bigger than rating[10], then we increment ascLeft. Oppositely if there is anything SMALLER than rating[10], then we increment ascRight. Note that because rating[10] is the middle number, we are when we ascLeft * ascRight, then we get all increasing combinations of different teams based on rating[10]!

You would repeat the exact same process for the descLeft * descRight. Then you add to the aforementioned to get the total possible combination for rating[10].

Finally repeat the process for 0 .. n on each rating to get the final comprehensive count.

This was a great solution and if you couldn't solve this problem, definitely remember the lesson in this problem.

Another different solution is below, it has the same performance but has an even more crazy way to solve it via some insane pattern recognition: link

A summary of the lessons learned in this:
1.) brute force is a GREAT start, don't give up on it almost by principle
2.) if sorting doesn't give obvious advantage after 5 minutes, it's probably not viable (to be debated more)
3.) recursion only walks in one direction (maybe?)

Let me know anything on your mind after reading through this, THANKS!