Count Number of Teams - Practice Coding Problems

Count Number of Teams - Problem

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

Input & Output

Example 1 — Basic Case

$ Input: rating = [2,5,3,4,1]

› Output: 3

💡 Note: We can form teams: [2,3,4] (ascending), [5,4,1] (descending), [5,3,1] (descending). Total = 3 teams.

Example 2 — Minimum Size

$ Input: rating = [2,1,3]

› Output: 0

💡 Note: No valid teams can be formed. [2,1,3] is neither ascending (2>1) nor descending (1<3).

Example 3 — All Ascending

$ Input: rating = [1,2,3,4,5]

› Output: 10

💡 Note: All possible triplets form ascending teams: (1,2,3), (1,2,4), (1,2,5), (1,3,4), (1,3,5), (1,4,5), (2,3,4), (2,3,5), (2,4,5), (3,4,5).

Constraints

3 ≤ rating.length ≤ 1000
1 ≤ rating[i] ≤ 10⁵
All the integers in rating are unique.

Visualization

Tap to expand

Understanding the Visualization

Input

Array of soldier ratings: [2,5,3,4,1]

Find Teams

Look for ascending (i<j<k) or descending (i>j>k) patterns

Output

Count of valid 3-soldier teams: 3

Key Takeaway

🎯 Key Insight: Fix the middle soldier and multiply the count of valid left partners with valid right partners

Asked in

A Amazon 45 M Microsoft 32 G Google 28 F Facebook 21

The key insight is to fix the middle soldier and count valid combinations on both sides. For each middle element, count smaller/larger elements to the left and right, then multiply appropriate counts. Best approach uses Binary Indexed Tree for O(n log n) time complexity with O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Triple Loop	O(n³)	O(1)	Check all possible triplets (i, j, k) where i < j < k
Dynamic Programming - Fix Middle Element	O(n²)	O(1)	For each middle soldier, count valid left and right partners
Binary Indexed Tree (Fenwick Tree)	O(n log n)	O(n)	Use BIT to count smaller/larger elements efficiently

Brute Force Triple Loop — Algorithm Steps

Iterate through all i from 0 to n-3
For each i, iterate j from i+1 to n-2
For each j, iterate k from j+1 to n-1
Check if rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k]

Visualization

Tap to expand

Step-by-Step Walkthrough

Triple Loop

Iterate through all i < j < k combinations

Check Pattern

Verify if ratings form ascending or descending order

Count Teams

Increment counter for each valid team found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* rating, int n) {
    int count = 0;
    
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                if ((rating[i] < rating[j] && rating[j] < rating[k]) ||
                    (rating[i] > rating[j] && rating[j] > rating[k])) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int rating[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        rating[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(rating, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops iterate through all possible triplets

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

38.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Triple Loop — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler