Count Number of Teams

Problem Statement

In this problem, you are given an array named rating which represents the unique rating values of n soldiers standing in a line. Your task is to identify and count all possible teams of three soldiers that can be formed under specific conditions.

A team of three soldiers indexed as (i, j, k) with the respective ratings (rating[i], rating[j], rating[k]) is considered valid if:

• Their ratings are either strictly increasing: (rating[i] < rating[j] < rating[k]),
• Or their ratings are strictly decreasing: (rating[i] > rating[j] > rating[k]).

Additionally, the selection of these indices must adhere to the order 0 <= i < j < k < n. You are required to return the total number of valid teams that can be formed.

Examples

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.

Approach and Intuition

The objective here is to count all the valid combinations of soldiers forming a team based on specific ordered conditions.

• Firstly, for any position j in the rating array, you can determine how many elements to the left (i < j) are smaller than rating[j] and how many are greater. These counts help in identifying possible increasing and decreasing sequences respectively.

• Similarly, for the same position j, determine how many elements to the right (k > j) are greater and how many are smaller than rating[j].

• For a triplet formation where i < j < k:

  • Increading triplet count: If there are countLeftLess numbers less than rating[j] to the left and countRightMore numbers greater than rating[j] to the right, then the combinations of forming a increasing triplet with j as the middle element is countLeftLess * countRightMore.

  • Decreasing triplet count: If there are countLeftMore numbers greater than rating[j] to the left and countRightLess numbers less than rating[j] to the right, then the combinations for forming a decreasing triplet with j as the middle element is countLeftMore * countRightLess.

By iterating over each element and calculating the above mentioned counts and combinations, you can sum them up to get the total number of valid teams.

This logical approach utilizes a blend of combinatorial mathematics and array manipulation, iterating through potential mid-points and calculating viable triplets, both increasing and decreasing, from their respective bounds.

Solutions

class Solution {
public:
    int countTeams(vector<int>& arr) {
        // Find the highest rating
        int highestRating = 0;
        for (int n : arr) {
            highestRating = max(highestRating, n);
        }
    
        // Initialize BITs for calculation
        vector<int> bitLeft(highestRating + 1, 0);
        vector<int> bitRight(highestRating + 1, 0);
    
        // Fill the right BIT with the initial values
        for (int n : arr) {
            bitUpdate(bitRight, n, 1);
        }
    
        int resultCount = 0;
        for (int r : arr) {
            // Remove the current element from the right BIT
            bitUpdate(bitRight, r, -1);
    
            // Calculate smaller and larger counts on both sides
            int leftLess = queryBIT(bitLeft, r - 1);
            int rightLess = queryBIT(bitRight, r - 1);
            int leftMore = queryBIT(bitLeft, highestRating) - queryBIT(bitLeft, r);
            int rightMore = queryBIT(bitRight, highestRating) - queryBIT(bitRight, r);
    
            // Compute results for valid sequences
            resultCount += (leftLess * rightMore) + (leftMore * rightLess);
    
            // Insert current into the BIT for left side
            bitUpdate(bitLeft, r, 1);
        }
    
        return resultCount;
    }
    
private:
    // Function to update a BIT
    void bitUpdate(vector<int>& bit, int index, int delta) {
        while (index < bit.size()) {
            bit[index] += delta;
            index += index & (-index); // Next index calculation
        }
    }
    
    // Function to compute prefix sum in a BIT
    int queryBIT(vector<int>& bit, int index) {
        int sum = 0;
        while (index > 0) {
            sum += bit[index];
            index -= index & (-index); // Move to the parent
        }
        return sum;
    }
};