Count Number of Teams

Count Number of Teams

What is this problem about?

In the "Count Number of Teams" problem, you are given an array of unique integers representing the skill levels of soldiers. You need to form teams of 3 soldiers $(rating[i], rating[j], rating[k])$ such that their ratings are either strictly increasing or strictly decreasing ($i < j < k$). The task is to return the total number of such teams.

Why is this asked in interviews?

Companies like Uber, Goldman Sachs, and Amazon ask this to evaluate a candidate's ability to optimize a combinatorial search. While an $O(n^3)$ brute force is easy to write, it's not efficient enough. The problem tests whether you can use a "middle-out" approach or advanced data structures like Binary Indexed Trees (BIT) to achieve $O(n \log n)$ or $O(n^2)$ time complexity.

Algorithmic pattern used

The most intuitive efficient pattern is the "Fix the Middle" approach. For each soldier $j$ in the middle:

1. Count soldiers $i < j$ with $rating[i] < rating[j]$ (left_smaller) and $rating[i] > rating[j]$ (left_larger).
2. Count soldiers $k > j$ with $rating[k] < rating[j]$ (right_smaller) and $rating[k] > rating[j]$ (right_larger).
3. The number of increasing teams with $j$ in the middle is left_smaller * right_larger.
4. The number of decreasing teams with $j$ in the middle is left_larger * right_smaller. Summing these for all $j$ gives the result.

Example explanation

Ratings: [2, 5, 3, 4, 1]

• Fix middle at 3 (index 2):
  • Left: [2, 5]. 2 < 3 (smaller=1), 5 > 3 (larger=1).
  • Right: [4, 1]. 4 > 3 (larger=1), 1 < 3 (smaller=1).
  • Teams: Increasing (1 * 1 = 1: [2, 3, 4]), Decreasing (1 * 1 = 1: [5, 3, 1]).
• Fix middle at 4 (index 3):
  • Left: [2, 5, 3]. 2 < 4, 3 < 4 (smaller=2), 5 > 4 (larger=1).
  • Right: [1]. 1 < 4 (smaller=1), larger=0.
  • Teams: Increasing (2 * 0 = 0), Decreasing (1 * 1 = 1: [5, 4, 1]). Total teams: 2 + 1 + ... (continue for all indices).

Common mistakes candidates make

The most common mistake is implementation of the triple loop, which is $O(n^3)$. Another mistake is not correctly accounting for the "strictly" increasing/decreasing requirement (though ratings are unique here). Some candidates also struggle with integrating BIT or Segment trees, which are needed if $n$ is very large and $O(n^2)$ is still too slow.

Interview preparation tip

Whenever a problem involves triplets $(i, j, k)$ with a relationship centered on $j$, try "fixing the middle element." It often reduces the complexity by one factor of $n$ because the conditions on $i$ and $k$ become independent once $j$ is fixed.