Day 24 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#1395. Count Number of Teams(Medium/JavaScript)
Tags: javascript, algorithms, webdev, programming
Published: 2022-03-06 00:54:47

**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` 

<!--Goldman Sachs Interview-->

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](https://leetcode.com/problems/count-number-of-teams/)
[Note 1: For Loop](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Loops_and_iteration)
[Note 2: Array.length](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/length)
[Note 3: Addition assignment (+=)](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Addition_assignment)
[Note 4: Increment (++)](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Increment)
[Blog Cover Image Credit](https://www.istockphoto.com/portfolio/monsitj?mediatype=photography)