_1395. Count Number of Teams.md

1395. Count Number of Teams

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 29, 2024

Last updated : July 29, 2024

---

Related Topics : Array, Dynamic Programming, Binary Indexed Tree, Segment Tree

Acceptance Rate : 70.13 %

---

Notes

Since we know that there are $\binom{n}{3}$ possible teams, I initially tried to brute force it but was shown to be unsuccessful with $O(n^3)$ solutions such as with using itertools.combinations(index, 3) and with iterating with a triple nested for loop.

Apparently it used to be an ACed solution but they increased the test case parameters so that it wouldn't pass anymore.

Version 1 ACed Solution

Looking at potential solutions, we realize that the number of "teams" where the middle person is from any given index $i$ is the number of soldiers left that are greater times the number of soldiers right that are smaller (or vise versa since as long as it's EITHER strictly increasing or strictkly decreasing, it's a permitted team).

Thus, I used heaps to keep track of how many were greater and smaller, writing that to a list and iterated once more through the indices to yield my calculation.

Final solution is $O(n^2)$

Version 2 Solution - Improved Bottoms Up

This was a much more optimized version that skipped the heap-based identification from before. In verison 1, we iterated based off of the middle index, resulting in a lengthy process and multiple passes.

Instead, with this solution, we simply keep track of two DP arrays for the two possible team conditions ($a<b<c$ and $a>b>c$), using the outer loop as the "rightmost" value, and the inner loop as the "middle value." This allowed us to essentially do a bottoms up DP approach.

Note

Both versions are in theory bottoms up tabulation but one is just much more optimized and straight forwards.

---

Solutions

• m1395 v1.py
• m1395 v2 Tabulation.py

Python

m1395 v1.py

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        # No need for "equal" case since all rating values are UNIQUE
        countValsSmaller = []
        countValsGreater = []

        # NOTE: Calculating how many values are less than, on the left
        # O(n^2)
        # Stores negatives for MAXHEAP
        valsSmaller = []
        # Stores positives for MINHEAP
        otherVals = []
        for i, r in enumerate(rating) :
            while valsSmaller and -valsSmaller[0] >= r :
                heapq.heappush(otherVals, -heapq.heappop(valsSmaller))
            while otherVals and otherVals[0] < r :
                heapq.heappush(valsSmaller, -heapq.heappop(otherVals))

            countValsSmaller.append(len(valsSmaller))
            heapq.heappush(otherVals, r)

        del valsSmaller
        del otherVals

        # NOTE: Calculating how many values are greater than, on the right
        # O(n^2)
        # Stores positives for MINHEAP
        valsGreater = []
        # Stores negatives for MAXHEAP
        otherVals = []
        for i, r in enumerate(reversed(rating)) :
            while valsGreater and valsGreater[0] <= r :
                heapq.heappush(otherVals, -heapq.heappop(valsGreater))
            while otherVals and -otherVals[0] > r :
                heapq.heappush(valsGreater, -heapq.heappop(otherVals))

            countValsGreater.append(len(valsGreater))
            heapq.heappush(otherVals, -r)

        countValsGreater.reverse()

        del valsGreater
        del otherVals

        # Iterating through the indices to calculate the final total
        # O(n)
        counter = 0
        for i in range(1, len(rating) - 1) :
            # Internal calculation to find the missing 2 values
            # since if they're unique, then #total - #smaller = #greater
            # Done here instead of above to save on space usage by half.
            smallerLeft = countValsSmaller[i]
            smallerRight = len(rating) - 1 - i - countValsGreater[i]
            greaterLeft = i - countValsSmaller[i]
            greaterRight = countValsGreater[i]

            counter += smallerLeft * greaterRight + smallerRight * greaterLeft

        return counter

m1395 v2 Tabulation.py

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        valsLessThan = [0] * len(rating)
        valsGreaterThan = valsLessThan.copy()
        count = 0

        for right in range(len(rating)) :
            for mid in range(right) :
                # a < b < c case
                if rating[mid] < rating[right] :
                    count += valsLessThan[mid]
                    valsLessThan[right] += 1
                # a > b > c case since UNIQUE ratings only
                else :
                    count += valsGreaterThan[mid]
                    valsGreaterThan[right] += 1
        return count