Day 24 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#1395. Count Number of Teams(Medium/JavaScript)

Intro: I am a former accountant turned software engineer graduated from coding bootcamp. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.

Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. Here is my approach:

• Pick a leetcode problem randomly or Online Assessment from targeted companies.
• Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
• Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
• Code out the solution in LeetCode without looking at the solutions
• Combat the forgetting curve: Re-do the question for the next three days. And come back regularly to revisit the problem.

---

1395. Count Number of Teams
Difficulty: Medium Language: 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 1:

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).

Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:

Input: rating = [1,2,3,4]
Output: 4

Constraints:

• n == rating.length
• 3 <= n <= 1000
• 1 <= rating[i] <= 105
• All the integers in rating are unique.

---

Solution:
Key to this solution is the number of teams that meets the condition can be calculated by finding the middle rating of the team. Multiply the count of ratings smaller than the middle rating by the count of ratings greater than middle rating will give us all posible combination that meets the condition. For example, given rating [1,2,3,4], there are 4 outputs that meet the conditon: [1,2,3],[1,2,4],[1,3,4],[2,3,4]. If we pick '2' as the middle rating, there are two numbers ('3' & '4') that are greater AND one number ('1') smaller than the middle rating. Therefore, total eligible combinations is two * one = 2. Based on this calculation, if we pick '3' as the middle rating; there are also two combinations. Total combinations is 2 + 2 = 4. Since 0 <= i < j < k < n, the middle rating can only be '2' or '3'. This problem allows the combinations to be ascending and descending order; so we will consider these two situation when we write code.

var numTeams = function(rating) {

    let solution = 0;

//initialize solution as 0

    for (let i = 1; i < rating.length - 1; i++){

//Loop (ntoe 1) through 'rating' array and keep count of numbers
//that are greater or smaller than raiting[i]. Because we are
//locating the middle ratings, the iteration will start at 1 and
//end at the second last number (rating.length-1)(ntoe 2) in the
//array.

    let ascSmaller = 0,
        ascGreater = 0,
        descSmaller = 0,
        descGreater = 0;

//Declare variables and set initial value as 0, these counts are
//used to calculate the solution 

        for (let j = i+1; j < rating.length; j++){
            if (rating[j] > rating[i]) ascGreater++
            if (rating[j] < rating[i]) descSmaller++
        }

//starting from the number next to middle number and end at last
//element of the array. If the numbers are greater than middle
//number increase (note 4) count for 'ascGreater' and
//'descSmaller' respectively.

        for (let j = i-1; j >= 0; j--){
            if (rating[j] > rating[i]) descGreater++
            if (rating[j] < rating[i]) ascSmaller++
        }

//starting from the number prior to middle number and end at first
//element of the array. If the numbers are smaller than middle
//number increase (note 4) count for 'descGreater' and
//'ascSmaller' respectively.

       solution += ascSmaller*ascGreater + descSmaller*descGreater

//as mentioned in the explanation above, this problem allows the
//combination to be ascending and descending order. Hence, we
//combine (note 3) the total output for each order together.

    }

    return solution
};

Time and Space Complexity

• Time: O(n^2)
• Space: ?

---

References:
LeetCode Problem Link
Note 1: For Loop
Note 2: Array.length
Note 3: Addition assignment (+=)
Note 4: Increment (++)
Blog Cover Image Credit