Leetcode 1395. Count Number of Teams

Problem Explanation:

The given problem presents a situation where soldiers are arranged in a line and each soldier is assigned a unique rating value. Our task is to form groups of three soldiers in such a way that their ratings either form an increasing sequence (rating[i] < rating[j] < rating[k]) or a decreasing sequence (rating[i] > rating[j] > rating[k]). Furthermore, it is important to note that i, j, and k represent the indices of the soldiers in this situation, where 0 <= i < j < k < n.

Let's consider this example,

Example: Input: rating = [2,5,3,4,1] In this case, Using the ratings, we can form three teams as (2,3,4), (5,4,1), and (5,3,1)

Solution Approach:

Here, we are utilizing a simple approach where we iterate through the given rating array with a pointer at the current soldier. We then divide the array into a left and right section. The left section ranges from the start of the array to the soldier at the current index and the right section spans from the soldier at the current index to the end of the array. We then count the number of soldiers with higher and lower ratings in both the left and right side with respect to the soldier at the current index. This allows us to count the team formations in both increasing and decreasing order of ratings.

Illustrative example:

Consider an example with soldiers' ratings as [4,5,6,7]. Now, for the soldier at index i=2 (rating=6), we have:

  • Left section : [4,5] -> 1 soldier with less rating, 0 soldiers with more ratings
  • Right section : [7] -> 0 soldiers with less rating, 1 soldier with more ratings

By moving the index through all other soldiers, we can determine all the possible combinations of teams that can be formed.

Python Solution:

1
2python
3class Solution:
4    def numTeams(self, rating: List[int]) -> int:
5        no_of_teams = 0
6        for i in range(1, len(rating) - 1):
7            # Calculate soldiers on the left with less/greater ratings.
8            left_less = left_greater = 0
9            for j in range(i):
10                if rating[j] < rating[i]:
11                    left_less += 1
12                elif rating[j] > rating[i]:
13                    left_greater += 1
14            right_less = right_greater = 0
15            for j in range(i+1, len(rating)):
16                if rating[j] < rating[i]:
17                    right_less += 1
18                else:
19                    right_greater += 1
20            no_of_teams += (left_less * right_greater) + (left_greater * right_less)
21        return no_of_teams

Note: More optimized solutions could be designed based on binary indexed tree or segment tree but this simple solution is easily understandable and solve the problem within the constraints.

The Python solution takes advantage of list indexing and uses two nested loops to co-operatively create all possible team combinations with the middle soldier in the loop as the current soldier. The number of soldiers with higher and lower ratings on left and right sides of current soldier is calculated and the valid team formations are updated accordingly.

Java Solution:

1
2java
3class Solution {
4    public int numTeams(int[] rating) {
5        int numTeams = 0;
6        for (int i = 1; i < rating.length - 1; ++i) {
7            int leftLess = 0, leftGreater = 0;
8            for (int j = 0; j < i; ++j) {
9                if (rating[j] < rating[i]) {
10                    leftLess++;
11                } else if(rating[j] > rating[i]) {
12                    leftGreater++;
13                }
14            }
15            int rightLess = 0, rightGreater = 0;
16            for (int j = i + 1; j < rating.length; ++j) {
17                if (rating[j] < rating[i]) {
18                    rightLess++;
19                } else if(rating[j] > rating[i]) {
20                    rightGreater++;
21                }
22            }
23            numTeams += leftLess * rightGreater + leftGreater * rightLess;
24        }
25        return numTeams;
26    }
27}

The Java solution similarly makes use of array indexing. Here too, we iterate through each soldier as the middle soldier in a loop, calculate the soldiers with higher and lower ratings for left and right, and update teams accordingly.

Additional Solution:

This problem can be efficiently solved by utilizing a binary indexed tree or a segment tree which reduces the time complexity for searching a segment on both left and right sides from O(n) to O(logN). However, for the current size of input constraints, the brute force approach works without any Time Limit Exceeded error and provides an easier understanding for beginners.## JavaScript Solution:

1
2javascript
3var numTeams = function(rating) {
4    let numTeams = 0;
5    for (let i = 1; i < rating.length - 1; ++i) {
6        let leftLess = 0, leftGreater = 0;
7        for (let j = 0; j < i; ++j) {
8            if (rating[j] < rating[i])
9                leftLess++;
10            else if(rating[j] > rating[i])
11                leftGreater++;
12        }
13        let rightLess = 0, rightGreater = 0;
14        for (let j = i + 1; j < rating.length; ++j) {
15            if (rating[j] < rating[i])
16                rightLess++;
17            else if(rating[j] > rating[i])
18                rightGreater++;
19        }
20        numTeams += leftLess * rightGreater + leftGreater * rightLess;
21    }
22    return numTeams;
23};

Similar to the Python and Java solutions, the JavaScript solution also makes use of array indexing. The code iterates through the soldiers with two nested loops, where the outer loop uses i as the pointer to the currently considered soldier in position i, and the inner loops use j as the pointer for soldiers before and after the current soldier.

The count of soldiers with higher and lower ratings on both sides of the current soldier are calculated, and the number of valid team formations are updated keeping in count the necessary conditions.

With this, we have provided solutions for the given problem in Python, Java, and JavaScript languages, each making use of similar logic and constructs specific to the particular language. Every solution takes into account the given conditions to form the teams of soldiers and provide the total number of such teams. They also handle the constraints, ensuring suitable teams are formed without breaking any rules, thus providing the correct output.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫