Beats 100 % O(n log n) | Binary Index Tree | Java | Python | C++ | JavaScript/TypeScript | Go | Rust
Problem Overview:\n\nThe problem presents a scenario involving a line of soldiers, each with a unique rating. The task is to form teams under specific condition
# Problem Overview:\n\nThe problem presents a scenario involving a line of soldiers, each with a unique rating. The task is to form teams under specific conditions:\n\n1. **Team Composition:**\n   - Each team must consist of exactly 3 soldiers.\n\n2. **Selection Criteria:**\n   - The soldiers in a team must be chosen from left to right in the line.\n   - This means if we select soldiers at positions i, j, and k, then i < j < k must be true.\n\n3. **Rating Requirements:**\n   - The ratings of the selected soldiers must follow one of two patterns:\n     a) Strictly increasing: rating[i] < rating[j] < rating[k]\n     b) Strictly decreasing: rating[i] > rating[j] > rating[k]\n\n4. **Multiple Team Participation:**\n   - A soldier can be part of multiple teams.\n\n5. **Goal:**\n   - Count the total number of valid teams that can be formed following these rules.\n\n**Key Considerations:**\n- The order of soldiers in the line is crucial and cannot be changed.\n- The uniqueness of ratings ensures no two soldiers have the same rating.\n- We need to consider both ascending and descending rating patterns.\n- The same trio of soldiers should not be counted twice (once for ascending and once for descending).\n\n**Constraints:**\n- The number of soldiers (n) is between 3 and 1000.\n- Each rating is a positive integer not exceeding 10^5.\n- All ratings are unique.\n\nThe challenge lies in efficiently counting all valid teams without explicitly forming each team, especially for larger inputs where a brute-force approach would be time-consuming.\n\n---\n# Binary Index Tree\n### Intuition\n\nThe problem asks us to count the number of valid teams of three soldiers that can be formed from a line of soldiers, where each soldier has a unique rating. A valid team must satisfy either an ascending or descending order of ratings, and the soldiers must be in the correct order in the line.\n\nThe key insight is that for each soldier, we need to count how many valid pairs of soldiers we can form with this soldier as the middle element. This means we need to find:\n1. For ascending order: How many soldiers to the left have a lower rating, and how many to the right have a higher rating.\n2. For descending order: How many soldiers to the left have a higher rating, and how many to the right have a lower rating.\n\nThe product of these two counts will give us the number of valid teams for each soldier as the middle element. Summing this for all soldiers will give us the total number of valid teams.\n\n### Approach\n\n\n1. **Preprocessing**:\n   - Create a list of Soldier objects, each containing the rating and original index.\n   - Sort this list based on the ratings.\n   - Create an index map that maps each soldier\'s original index to their position in the sorted list.\n\n2. **Counting Teams**:\n   - Use a Binary Indexed Tree (BIT) or Fenwick Tree to efficiently count the number of soldiers with ratings less than or greater than a given rating.\n   - Iterate through the soldiers in their original order.\n   - For each soldier, count the number of valid teams they can form as the middle element, both for ascending and descending order.\n\n3. **Binary Indexed Tree (BIT)**:\n   - Use a BIT to perform efficient range sum queries and updates.\n   - This allows us to count the number of soldiers with ratings less than or greater than a given rating in logarithmic time.\n\n**Pseudo-code** for the approach:\n\n```\nfunction numTeams(rating):\n    n = length of rating\n    if n < 3:\n        return 0\n\n    // Create and sort list of soldiers\n    soldiers = empty list\n    for i from 0 to n-1:\n        add Soldier(rating[i], i) to soldiers\n    sort soldiers by rating\n\n    // Create index map\n    indexMap = array of size n\n    for i from 0 to n-1:\n        indexMap[soldiers[i].index] = i\n\n    teams = 0\n    \n    // Count ascending teams\n    teams += countTeams(indexMap, n, ascending=true)\n    \n    // Count descending teams\n    teams += countTeams(indexMap, n, ascending=false)\n    \n    return teams\n\nfunction countTeams(indexMap, n, ascending):\n    bit = array of size n+1 initialized with zeros\n    teams = 0\n\n    for i from 0 to n-1:\n        rank = indexMap[i] + 1\n        \n        if ascending:\n            left = getSum(bit, rank - 1)\n            right = n - rank - (getSum(bit, n) - getSum(bit, rank))\n        else:\n            left = getSum(bit, n) - getSum(bit, rank)\n            right = rank - 1 - getSum(bit, rank - 1)\n        \n        teams += left * right\n        update(bit, rank, 1)\n    \n    return teams\n\nfunction update(bit, index, val):\n    while index < length of bit:\n        bit[index] += val\n        index += index & (-index)\n\nfunction getSum(bit, index):\n    sum = 0\n    while index > 0:\n        sum += bit[index]\n        index -= index & (-index)\n    return sum\n\nclass Soldier:\n    rating: integer\n    index: integer\n\n    constructor(rating, index):\n        this.rating = rating\n        this.index = index\n\n    compareTo(other):\n        return this.rating - other.rating\n```\n\nLet\'s go through the main steps in more detail:\n\n1. **Preprocessing**:\n   - We create a list of Soldier objects, each containing the rating and the original index of a soldier.\n   - We sort this list based on the ratings. This gives us the relative order of soldiers by their ratings.\n   - We create an index map that, for each soldier\'s original index, stores their position in the sorted list. This allows us to quickly find out how many soldiers have a lower or higher rating than a given soldier.\n\n2. **Counting Teams**:\n   - We use a function `countTeams` to count the number of valid teams for both ascending and descending order.\n   - For each soldier (in their original order):\n     - We find their rank (position in the sorted list) using the index map.\n     - We count how many soldiers to their left have a lower rating (for ascending) or higher rating (for descending).\n     - We count how many soldiers to their right have a higher rating (for ascending) or lower rating (for descending).\n     - The product of these two counts gives us the number of valid teams with this soldier as the middle element.\n     - We add this to our total count of teams.\n\n3. **Binary Indexed Tree (BIT)**:\n   - We use a BIT to efficiently perform range sum queries and updates.\n   - The BIT is used to keep track of how many soldiers we\'ve seen so far with each rating.\n   - The `update` function adds a soldier to the BIT.\n   - The `getSum` function counts how many soldiers we\'ve seen so far with a rating less than or equal to a given rating.\n\nThe key to the efficiency of this algorithm is the use of the Binary Indexed Tree. It allows us to perform both updates and queries in O(log n) time, which is crucial for the overall time complexity of the algorithm.\n\n### Dry Run\n\nLet\'s use the example: rating = [2, 5, 3, 4, 1]\n\n1. **Create and sort Soldier objects:**\n\n   | Original Index | 0 | 1 | 2 | 3 | 4 |\n   |----------------|---|---|---|---|---|\n   | Rating         | 2 | 5 | 3 | 4 | 1 |\n   | Sorted Order   | 1 | 5 | 2 | 3 | 4 |\n   | Sorted Index   | 0 | 4 | 1 | 2 | 3 |\n\n2. **Create indexMap:**\n\n   | Original Index | 0 | 1 | 2 | 3 | 4 |\n   |----------------|---|---|---|---|---|\n   | indexMap value | 1 | 4 | 2 | 3 | 0 |\n\n3. **Count ascending teams:**\n   We process soldiers in their original order, using the BIT to count smaller elements to the left.\n\n   | Step | Index | Rating | Smaller Left | Larger Right | Teams | BIT Update |\n   |------|-------|--------|--------------|--------------|-------|------------|\n   | 1    | 0     | 2      | 0            | 3            | 0     | [0,1,0,0,0,0] |\n   | 2    | 1     | 5      | 1            | 0            | 0     | [0,1,0,0,0,1] |\n   | 3    | 2     | 3      | 1            | 1            | 1     | [0,1,0,1,0,1] |\n   | 4    | 3     | 4      | 2            | 0            | 0     | [0,1,0,1,1,1] |\n   | 5    | 4     | 1      | 0            | 4            | 0     | [1,1,0,1,1,1] |\n\n   Total ascending teams: 1\n\n4. **Count descending teams:**\n   We process soldiers in reverse order, using the BIT to count larger elements to the left.\n\n   | Step | Index | Rating | Larger Left | Smaller Right | Teams | BIT Update |\n   |------|-------|--------|-------------|---------------|-------|------------|\n   | 1    | 4     | 1      | 0           | 0             | 0     | [0,1,0,0,0,0] |\n   | 2    | 3     | 4      | 1           | 1             | 1     | [0,1,0,0,1,0] |\n   | 3    | 2     | 3      | 1           | 1             | 1     | [0,1,0,1,1,0] |\n   | 4    | 1     | 5      | 3           | 0             | 0     | [0,1,0,1,1,1] |\n   | 5    | 0     | 2      | 1           | 1             | 1     | [0,1,1,1,1,1] |\n\n   Total descending teams: 3\n\n5. **Final result:**\n   Total teams = Ascending teams + Descending teams = 1 + 3 = 4\n\nThis is how we process each soldier, using the BIT to efficiently count the number of valid teams they can form as the middle member. The BIT allows us to quickly query the count of elements to the left that satisfy our condition (smaller for ascending, larger for descending) and update these counts.\n\nThe final answer of 4 represents all valid teams: (2,3,4), (5,3,1), (5,4,1), and (5,3,2).\n\n### Complexity\n\n- **Time complexity: O(n log n)**\n  - Sorting the soldiers takes O(n log n) time.\n  - We iterate through all soldiers once, and for each soldier, we perform constant number of BIT operations, each taking O(log n) time.\n  - Therefore, the overall time complexity is O(n log n).\n\n- **Space complexity: O(n)**\n  - We use additional space for the list of soldiers, the index map, and the BIT, each of size O(n).\n  - Therefore, the overall space complexity is O(n).\n\n---\n\n### Code\n```Java []\nimport java.util.*;\n\nclass Solution {\n    public int numTeams(int[] rating) {\n        int n = rating.length;\n        if (n < 3) return 0;\n        \n        // Create a list of soldiers with their ratings and indices\n        List<Soldier> soldiers = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            soldiers.add(new Soldier(rating[i], i));\n        }\n        \n        // Sort soldiers by rating\n        Collections.sort(soldiers);\n        \n        int[] indexMap = new int[n];\n        for (int i = 0; i < n; i++) {\n            indexMap[soldiers.get(i).index] = i;\n        }\n        \n        int teams = 0;\n        \n        // Count ascending teams\n        teams += countTeams(indexMap, n, true);\n        \n        // Count descending teams\n        teams += countTeams(indexMap, n, false);\n        \n        return teams;\n    }\n    \n    private int countTeams(int[] indexMap, int n, boolean ascending) {\n        int[] bit = new int[n + 1];\n        int teams = 0;\n        \n        for (int i = 0; i < n; i++) {\n            int rank = indexMap[i] + 1;\n            int left = ascending ? getSum(bit, rank - 1) : getSum(bit, n) - getSum(bit, rank);\n            int right = ascending ? n - rank - (getSum(bit, n) - getSum(bit, rank)) : rank - 1 - getSum(bit, rank - 1);\n            teams += left * right;\n            update(bit, rank, 1);\n        }\n        \n        return teams;\n    }\n    \n    private void update(int[] bit, int index, int val) {\n        while (index < bit.length) {\n            bit[index] += val;\n            index += index & (-index);\n        }\n    }\n    \n    private int getSum(int[] bit, int index) {\n        int sum = 0;\n        while (index > 0) {\n            sum += bit[index];\n            index -= index & (-index);\n        }\n        return sum;\n    }\n    \n    private class Soldier implements Comparable<Soldier> {\n        int rating;\n        int index;\n        \n        Soldier(int rating, int index) {\n            this.rating = rating;\n            this.index = index;\n        }\n        \n        @Override\n        public int compareTo(Soldier other) {\n            return Integer.compare(this.rating, other.rating);\n        }\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int numTeams(vector<int>& rating) {\n        int n = rating.size();\n        if (n < 3) return 0;\n        \n        vector<pair<int, int>> soldiers;\n        for (int i = 0; i < n; i++) {\n            soldiers.push_back({rating[i], i});\n        }\n        sort(soldiers.begin(), soldiers.end());\n        \n        vector<int> indexMap(n);\n        for (int i = 0; i < n; i++) {\n            indexMap[soldiers[i].second] = i;\n        }\n        \n        return countTeams(indexMap, n, true) + countTeams(indexMap, n, false);\n    }\n    \nprivate:\n    int countTeams(const vector<int>& indexMap, int n, bool ascending) {\n        vector<int> bit(n + 1, 0);\n        int teams = 0;\n        \n        for (int i = 0; i < n; i++) {\n            int rank = indexMap[i] + 1;\n            int left = ascending ? getSum(bit, rank - 1) : getSum(bit, n) - getSum(bit, rank);\n            int right = ascending ? n - rank - (getSum(bit, n) - getSum(bit, rank)) : rank - 1 - getSum(bit, rank - 1);\n            teams += left * right;\n            update(bit, rank, 1);\n        }\n        \n        return teams;\n    }\n    \n    void update(vector<int>& bit, int index, int val) {\n        while (index < bit.size()) {\n            bit[index] += val;\n            index += index & (-index);\n        }\n    }\n    \n    int getSum(const vector<int>& bit, int index) {\n        int sum = 0;\n        while (index > 0) {\n            sum += bit[index];\n            index -= index & (-index);\n        }\n        return sum;\n    }\n};\n```\n```Python []\nclass Solution:\n    def numTeams(self, rating: List[int]) -> int:\n        n = len(rating)\n        if n < 3:\n            return 0\n        \n        soldiers = sorted([(r, i) for i, r in enumerate(rating)])\n        index_map = [0] * n\n        for i, (_, idx) in enumerate(soldiers):\n            index_map[idx] = i\n        \n        def count_teams(ascending: bool) -> int:\n            bit = [0] * (n + 1)\n            teams = 0\n            \n            for i in range(n):\n                rank = index_map[i] + 1\n                left = self.get_sum(bit, rank - 1) if ascending else self.get_sum(bit, n) - self.get_sum(bit, rank)\n                right = n - rank - (self.get_sum(bit, n) - self.get_sum(bit, rank)) if ascending else rank - 1 - self.get_sum(bit, rank - 1)\n                teams += left * right\n                self.update(bit, rank, 1)\n            \n            return teams\n        \n        return count_teams(True) + count_teams(False)\n    \n    def update(self, bit: List[int], index: int, val: int) -> None:\n        while index < len(bit):\n            bit[index] += val\n            index += index & (-index)\n    \n    def get_sum(self, bit: List[int], index: int) -> int:\n        total = 0\n        while index > 0:\n            total += bit[index]\n            index -= index & (-index)\n        return total\n```\n```Go []\nfunc numTeams(rating []int) int {\n    n := len(rating)\n    if n < 3 {\n        return 0\n    }\n    \n    type soldier struct {\n        rating, index int\n    }\n    \n    soldiers := make([]soldier, n)\n    for i, r := range rating {\n        soldiers[i] = soldier{r, i}\n    }\n    sort.Slice(soldiers, func(i, j int) bool {\n        return soldiers[i].rating < soldiers[j].rating\n    })\n    \n    indexMap := make([]int, n)\n    for i, s := range soldiers {\n        indexMap[s.index] = i\n    }\n    \n    countTeams := func(ascending bool) int {\n        bit := make([]int, n+1)\n        teams := 0\n        \n        for i := 0; i < n; i++ {\n            rank := indexMap[i] + 1\n            var left, right int\n            if ascending {\n                left = getSum(bit, rank-1)\n                right = n - rank - (getSum(bit, n) - getSum(bit, rank))\n            } else {\n                left = getSum(bit, n) - getSum(bit, rank)\n                right = rank - 1 - getSum(bit, rank-1)\n            }\n            teams += left * right\n            update(bit, rank, 1)\n        }\n        \n        return teams\n    }\n    \n    return countTeams(true) + countTeams(false)\n}\n\nfunc update(bit []int, index, val int) {\n    for index < len(bit) {\n        bit[index] += val\n        index += index & (-index)\n    }\n}\n\nfunc getSum(bit []int, index int) int {\n    sum := 0\n    for index > 0 {\n        sum += bit[index]\n        index -= index & (-index)\n    }\n    return sum\n}\n```\n```Rust []\nimpl Solution {\n    pub fn num_teams(rating: Vec<i32>) -> i32 {\n        let n = rating.len();\n        if n < 3 {\n            return 0;\n        }\n        \n        let mut soldiers: Vec<(i32, usize)> = rating.iter().enumerate().map(|(i, &r)| (r, i)).collect();\n        soldiers.sort_unstable_by_key(|&(r, _)| r);\n        \n        let mut index_map = vec![0; n];\n        for (i, &(_, idx)) in soldiers.iter().enumerate() {\n            index_map[idx] = i;\n        }\n        \n        let count_teams = |ascending: bool| -> i32 {\n            let mut bit = vec![0; n + 1];\n            let mut teams = 0;\n            \n            for i in 0..n {\n                let rank = index_map[i] + 1;\n                let left = if ascending {\n                    Self::get_sum(&bit, rank - 1)\n                } else {\n                    Self::get_sum(&bit, n) - Self::get_sum(&bit, rank)\n                };\n                let right = if ascending {\n                    n - rank - (Self::get_sum(&bit, n) - Self::get_sum(&bit, rank))\n                } else {\n                    rank - 1 - Self::get_sum(&bit, rank - 1)\n                };\n                teams += left * right;\n                Self::update(&mut bit, rank, 1);\n            }\n            \n            teams as i32\n        };\n        \n        count_teams(true) + count_teams(false)\n    }\n    \n    fn update(bit: &mut Vec<usize>, mut index: usize, val: usize) {\n        while index < bit.len() {\n            bit[index] += val;\n            index += index & (!index + 1);\n        }\n    }\n    \n    fn get_sum(bit: &Vec<usize>, mut index: usize) -> usize {\n        let mut sum = 0;\n        while index > 0 {\n            sum += bit[index];\n            index -= index & (!index + 1);\n        }\n        sum\n    }\n}\n```\n```JavaScript []\n/**\n * @param {number[]} rating\n * @return {number}\n */\nvar numTeams = function(rating) {\n    const n = rating.length;\n    if (n < 3) return 0;\n    \n    const soldiers = rating.map((r, i) => [r, i]).sort((a, b) => a[0] - b[0]);\n    const indexMap = new Array(n).fill(0);\n    for (let i = 0; i < n; i++) {\n        indexMap[soldiers[i][1]] = i;\n    }\n    \n    const countTeams = (ascending) => {\n        const bit = new Array(n + 1).fill(0);\n        let teams = 0;\n        \n        for (let i = 0; i < n; i++) {\n            const rank = indexMap[i] + 1;\n            const left = ascending ? getSum(bit, rank - 1) : getSum(bit, n) - getSum(bit, rank);\n            const right = ascending ? n - rank - (getSum(bit, n) - getSum(bit, rank)) : rank - 1 - getSum(bit, rank - 1);\n            teams += left * right;\n            update(bit, rank, 1);\n        }\n        \n        return teams;\n    };\n    \n    const update = (bit, index, val) => {\n        while (index < bit.length) {\n            bit[index] += val;\n            index += index & (-index);\n        }\n    };\n    \n    const getSum = (bit, index) => {\n        let sum = 0;\n        while (index > 0) {\n            sum += bit[index];\n            index -= index & (-index);\n        }\n        return sum;\n    };\n    \n    return countTeams(true) + countTeams(false);\n};\n```\n```TypeScript []\nfunction numTeams(rating: number[]): number {\n    const n: number = rating.length;\n    if (n < 3) return 0;\n    \n    const soldiers: [number, number][] = rating.map((r, i): [number, number] => [r, i]).sort((a, b) => a[0] - b[0]);\n    const indexMap: number[] = new Array(n).fill(0);\n    for (let i = 0; i < n; i++) {\n        indexMap[soldiers[i][1]] = i;\n    }\n    \n    const countTeams = (ascending: boolean): number => {\n        const bit: number[] = new Array(n + 1).fill(0);\n        let teams: number = 0;\n        \n        for (let i = 0; i < n; i++) {\n            const rank: number = indexMap[i] + 1;\n            const left: number = ascending ? getSum(bit, rank - 1) : getSum(bit, n) - getSum(bit, rank);\n            const right: number = ascending ? n - rank - (getSum(bit, n) - getSum(bit, rank)) : rank - 1 - getSum(bit, rank - 1);\n            teams += left * right;\n            update(bit, rank, 1);\n        }\n        \n        return teams;\n    };\n    \n    const update = (bit: number[], index: number, val: number): void => {\n        while (index < bit.length) {\n            bit[index] += val;\n            index += index & (-index);\n        }\n    };\n    \n    const getSum = (bit: number[], index: number): number => {\n        let sum: number = 0;\n        while (index > 0) {\n            sum += bit[index];\n            index -= index & (-index);\n        }\n        return sum;\n    };\n    \n    return countTeams(true) + countTeams(false);\n}\n\n```\n---\n\n# Approach 2\n\n### Intuition\n\nThis approach for the problem is based on the observation that for each soldier, we can count the number of valid teams they can be a part of by considering them as the middle element of a team. \n\nThe key insights are:\n1. For each soldier, we need to count how many soldiers to their left have lower and higher ratings.\n2. Similarly, we need to count how many soldiers to their right have lower and higher ratings.\n3. The number of ascending teams with this soldier as the middle element is the product of lower ratings to the left and higher ratings to the right.\n4. The number of descending teams with this soldier as the middle element is the product of higher ratings to the left and lower ratings to the right.\n5. By summing these counts for all soldiers, we get the total number of valid teams.\n\nThis approach doesn\'t use traditional dynamic programming with memoization, but it does use the principle of breaking down the problem into smaller subproblems and combining their results.\n\n### Approach\n\n1. **Iterate through all soldiers:**\n   - For each soldier, consider them as the potential middle element of a team.\n\n2. **Count smaller and larger elements:**\n   - For each soldier, count the number of soldiers with smaller and larger ratings to their left and right.\n\n3. **Calculate teams:**\n   - For ascending teams: multiply the count of smaller ratings to the left with larger ratings to the right.\n   - For descending teams: multiply the count of larger ratings to the left with smaller ratings to the right.\n\n4. **Sum up all teams:**\n   - Add the number of ascending and descending teams for each soldier to get the total count.\n\n# Pseudo-code\n\n```\nfunction numTeams(rating):\n    totalTeams = 0\n    soldierCount = length of rating\n\n    for currentSoldier from 0 to soldierCount - 1:\n        totalTeams += countTeams(rating, currentSoldier, soldierCount)\n\n    return totalTeams\n\nfunction countTeams(rating, currentSoldier, soldierCount):\n    leftCounts = countSmallerAndLarger(rating, 0, currentSoldier, rating[currentSoldier])\n    rightCounts = countSmallerAndLarger(rating, currentSoldier + 1, soldierCount, rating[currentSoldier])\n\n    ascendingTeams = leftCounts[0] * rightCounts[1]\n    descendingTeams = leftCounts[1] * rightCounts[0]\n\n    return ascendingTeams + descendingTeams\n\nfunction countSmallerAndLarger(rating, start, end, reference):\n    smaller = 0\n    larger = 0\n\n    for i from start to end - 1:\n        if rating[i] < reference:\n            smaller++\n        else if rating[i] > reference:\n            larger++\n\n    return [smaller, larger]\n```\n\n### Dry Run\n\nLet\'s use the example: rating = [2, 5, 3, 4, 1]\n\nWe\'ll go through the process for each soldier:\n\n1. **Soldier with rating 2 (index 0):**\n   - Left counts: [] -> [0, 0]\n   - Right counts: [5, 3, 4, 1] -> [1, 3]\n   - Ascending teams: 0 * 3 = 0\n   - Descending teams: 0 * 1 = 0\n   - Total teams: 0\n\n2. **Soldier with rating 5 (index 1):**\n   - Left counts: [2] -> [1, 0]\n   - Right counts: [3, 4, 1] -> [3, 0]\n   - Ascending teams: 1 * 0 = 0\n   - Descending teams: 0 * 3 = 0\n   - Total teams: 0\n\n3. **Soldier with rating 3 (index 2):**\n   - Left counts: [2, 5] -> [1, 1]\n   - Right counts: [4, 1] -> [1, 1]\n   - Ascending teams: 1 * 1 = 1\n   - Descending teams: 1 * 1 = 1\n   - Total teams: 2\n\n4. **Soldier with rating 4 (index 3):**\n   - Left counts: [2, 5, 3] -> [2, 1]\n   - Right counts: [1] -> [1, 0]\n   - Ascending teams: 2 * 0 = 0\n   - Descending teams: 1 * 1 = 1\n   - Total teams: 1\n\n5. **Soldier with rating 1 (index 4):**\n   - Left counts: [2, 5, 3, 4] -> [0, 4]\n   - Right counts: [] -> [0, 0]\n   - Ascending teams: 0 * 0 = 0\n   - Descending teams: 4 * 0 = 0\n   - Total teams: 0\n\nTotal teams = 0 + 0 + 2 + 1 + 0 = 3\n\nThe final answer of 3 represents all valid teams: (2,3,4), (5,3,1), and (5,4,1).\n\n### Complexity\n\n- **Time complexity: O(n^2)**\n  - We iterate through all n soldiers.\n  - For each soldier, we count smaller and larger elements to their left and right, which takes O(n) time.\n  - Therefore, the overall time complexity is O(n^2).\n\n- **Space complexity: O(1)**\n  - We only use a constant amount of extra space for variables and small arrays.\n  - The space complexity is independent of the input size.\n\nThis approach trades time complexity for space complexity compared to the Binary Indexed Tree approach. It\'s simpler to implement and uses less space, but it\'s less efficient for larger inputs due to its quadratic time complexity.\n\n---\n### Code\n\n```Java []\nclass Solution {\n    public int numTeams(int[] rating) {\n        int totalTeams = 0;\n        int soldierCount = rating.length;\n\n        for (int currentSoldier = 0; currentSoldier < soldierCount; currentSoldier++) {\n            totalTeams += countTeams(rating, currentSoldier, soldierCount);\n        }\n\n        return totalTeams;\n    }\n\n    private int countTeams(int[] rating, int currentSoldier, int soldierCount) {\n        int[] leftCounts = countSmallerAndLarger(rating, 0, currentSoldier, rating[currentSoldier]);\n        int[] rightCounts = countSmallerAndLarger(rating, currentSoldier + 1, soldierCount, rating[currentSoldier]);\n\n        int ascendingTeams = leftCounts[0] * rightCounts[1];\n        int descendingTeams = leftCounts[1] * rightCounts[0];\n\n        return ascendingTeams + descendingTeams;\n    }\n\n    private int[] countSmallerAndLarger(int[] rating, int start, int end, int reference) {\n        int smaller = 0, larger = 0;\n\n        for (int i = start; i < end; i++) {\n            if (rating[i] < reference) {\n                smaller++;\n            } else if (rating[i] > reference) {\n                larger++;\n            }\n        }\n\n        return new int[]{smaller, larger};\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int numTeams(vector<int>& rating) {\n        int totalTeams = 0;\n        int soldierCount = rating.size();\n\n        for (int currentSoldier = 0; currentSoldier < soldierCount; currentSoldier++) {\n            totalTeams += countTeams(rating, currentSoldier, soldierCount);\n        }\n\n        return totalTeams;\n    }\n\nprivate:\n    int countTeams(const vector<int>& rating, int currentSoldier, int soldierCount) {\n        auto leftCounts = countSmallerAndLarger(rating, 0, currentSoldier, rating[currentSoldier]);\n        auto rightCounts = countSmallerAndLarger(rating, currentSoldier + 1, soldierCount, rating[currentSoldier]);\n\n        int ascendingTeams = leftCounts.first * rightCounts.second;\n        int descendingTeams = leftCounts.second * rightCounts.first;\n\n        return ascendingTeams + descendingTeams;\n    }\n\n    pair<int, int> countSmallerAndLarger(const vector<int>& rating, int start, int end, int reference) {\n        int smaller = 0, larger = 0;\n\n        for (int i = start; i < end; i++) {\n            if (rating[i] < reference) {\n                smaller++;\n            } else if (rating[i] > reference) {\n                larger++;\n            }\n        }\n\n        return {smaller, larger};\n    }\n};\n```\n```Python []\nclass Solution:\n    def numTeams(self, rating: List[int]) -> int:\n        total_teams = 0\n        soldier_count = len(rating)\n\n        for current_soldier in range(soldier_count):\n            total_teams += self.count_teams(rating, current_soldier, soldier_count)\n\n        return total_teams\n\n    def count_teams(self, rating: List[int], current_soldier: int, soldier_count: int) -> int:\n        left_counts = self.count_smaller_and_larger(rating, 0, current_soldier, rating[current_soldier])\n        right_counts = self.count_smaller_and_larger(rating, current_soldier + 1, soldier_count, rating[current_soldier])\n\n        ascending_teams = left_counts[0] * right_counts[1]\n        descending_teams = left_counts[1] * right_counts[0]\n\n        return ascending_teams + descending_teams\n\n    def count_smaller_and_larger(self, rating: List[int], start: int, end: int, reference: int) -> Tuple[int, int]:\n        smaller, larger = 0, 0\n\n        for i in range(start, end):\n            if rating[i] < reference:\n                smaller += 1\n            elif rating[i] > reference:\n                larger += 1\n\n        return smaller, larger\n```\n```Go []\nfunc numTeams(rating []int) int {\n    totalTeams := 0\n    soldierCount := len(rating)\n\n    for currentSoldier := 0; currentSoldier < soldierCount; currentSoldier++ {\n        totalTeams += countTeams(rating, currentSoldier, soldierCount)\n    }\n\n    return totalTeams\n}\n\nfunc countTeams(rating []int, currentSoldier, soldierCount int) int {\n    leftCounts := countSmallerAndLarger(rating, 0, currentSoldier, rating[currentSoldier])\n    rightCounts := countSmallerAndLarger(rating, currentSoldier+1, soldierCount, rating[currentSoldier])\n\n    ascendingTeams := leftCounts[0] * rightCounts[1]\n    descendingTeams := leftCounts[1] * rightCounts[0]\n\n    return ascendingTeams + descendingTeams\n}\n\nfunc countSmallerAndLarger(rating []int, start, end, reference int) [2]int {\n    smaller, larger := 0, 0\n\n    for i := start; i < end; i++ {\n        if rating[i] < reference {\n            smaller++\n        } else if rating[i] > reference {\n            larger++\n        }\n    }\n\n    return [2]int{smaller, larger}\n}\n```\n```Rust []\nimpl Solution {\n    pub fn num_teams(rating: Vec<i32>) -> i32 {\n        let mut total_teams = 0;\n        let soldier_count = rating.len();\n\n        for current_soldier in 0..soldier_count {\n            total_teams += Self::count_teams(&rating, current_soldier, soldier_count);\n        }\n\n        total_teams\n    }\n\n    fn count_teams(rating: &[i32], current_soldier: usize, soldier_count: usize) -> i32 {\n        let left_counts = Self::count_smaller_and_larger(rating, 0, current_soldier, rating[current_soldier]);\n        let right_counts = Self::count_smaller_and_larger(rating, current_soldier + 1, soldier_count, rating[current_soldier]);\n\n        let ascending_teams = left_counts.0 * right_counts.1;\n        let descending_teams = left_counts.1 * right_counts.0;\n\n        ascending_teams + descending_teams\n    }\n\n    fn count_smaller_and_larger(rating: &[i32], start: usize, end: usize, reference: i32) -> (i32, i32) {\n        let mut smaller = 0;\n        let mut larger = 0;\n\n        for i in start..end {\n            if rating[i] < reference {\n                smaller += 1;\n            } else if rating[i] > reference {\n                larger += 1;\n            }\n        }\n\n        (smaller, larger)\n    }\n}\n```\n```JavaScript []\n/**\n * @param {number[]} rating\n * @return {number}\n */\nvar numTeams = function(rating) {\n    let totalTeams = 0;\n    const soldierCount = rating.length;\n\n    for (let currentSoldier = 0; currentSoldier < soldierCount; currentSoldier++) {\n        totalTeams += countTeams(rating, currentSoldier, soldierCount);\n    }\n\n    return totalTeams;\n};\n\nfunction countTeams(rating, currentSoldier, soldierCount) {\n    const leftCounts = countSmallerAndLarger(rating, 0, currentSoldier, rating[currentSoldier]);\n    const rightCounts = countSmallerAndLarger(rating, currentSoldier + 1, soldierCount, rating[currentSoldier]);\n\n    const ascendingTeams = leftCounts[0] * rightCounts[1];\n    const descendingTeams = leftCounts[1] * rightCounts[0];\n\n    return ascendingTeams + descendingTeams;\n}\n\nfunction countSmallerAndLarger(rating, start, end, reference) {\n    let smaller = 0, larger = 0;\n\n    for (let i = start; i < end; i++) {\n        if (rating[i] < reference) {\n            smaller++;\n        } else if (rating[i] > reference) {\n            larger++;\n        }\n    }\n\n    return [smaller, larger];\n}\n```\n```TypeScript []\nfunction numTeams(rating: number[]): number {\n    let totalTeams = 0;\n    const soldierCount = rating.length;\n\n    for (let currentSoldier = 0; currentSoldier < soldierCount; currentSoldier++) {\n        totalTeams += countTeams(rating, currentSoldier, soldierCount);\n    }\n\n    return totalTeams;\n}\n\nfunction countTeams(rating: number[], currentSoldier: number, soldierCount: number): number {\n    const leftCounts = countSmallerAndLarger(rating, 0, currentSoldier, rating[currentSoldier]);\n    const rightCounts = countSmallerAndLarger(rating, currentSoldier + 1, soldierCount, rating[currentSoldier]);\n\n    const ascendingTeams = leftCounts[0] * rightCounts[1];\n    const descendingTeams = leftCounts[1] * rightCounts[0];\n\n    return ascendingTeams + descendingTeams;\n}\n\nfunction countSmallerAndLarger(rating: number[], start: number, end: number, reference: number): [number, number] {\n    let smaller = 0, larger = 0;\n\n    for (let i = start; i < end; i++) {\n        if (rating[i] < reference) {\n            smaller++;\n        } else if (rating[i] > reference) {\n            larger++;\n        }\n    }\n\n    return [smaller, larger];\n}\n```
['Array', 'Dynamic Programming', 'Binary Indexed Tree', 'C++', 'Java', 'Go', 'TypeScript', 'Python3', 'Rust', 'JavaScript']