1395. Count Number of Teams

Best solution

T: O(n^2)
S: O(1)

class Solution {
    public int numTeams(int[] rating) {
        int n = rating.length;
        int result = 0;
        for (int middle = 0; middle < n-1; middle++) {
            int leftSmaller = 0;
            int rightLarger = 0;
            // asc part
            for (int left = 0; left < middle; left++) {
                if (rating[left] < rating[middle]) {
                    leftSmaller++;
                }
            }
            for (int right = middle+1; right < n; right++) {
                if (rating[middle] < rating[right]) {
                    rightLarger++;
                }
            }
            result += leftSmaller*rightLarger;
            // desc part
            int leftLarger = middle - leftSmaller;
            int rightSmaller = n - middle - 1 - rightLarger;
            result += leftLarger*rightSmaller;
        }
        return result;
    }
}

/**
T: O(n^2)
S: O(1)
use greedy & dp solution
because it said "3 soliders"

asc or
x i x j x k x
desc
x i x j x k x

if we use middle one... then find left side smaller, and right side larger

ex:
[1, 2,5,3,4,1, 6]
now mid  is 3 -> so left side smaller = [1,2], right side larger = [4, 6]
so for mid is 3, there is 2*2 = 4 ways to have asc teams

vice versa, for desc
for mid is 3 -> so left side "larger" = [5], right side "smaller" = [1]
so there is 1*1 way to have desc team
so for 3 there is 4+1 ways

so we can use a loop to fix middle, then use another loop to find left part, right part larger and smaller
sum up them, it is the ans
 */

DFS + memo

T: O(n^2)
S: O(n^2)

class Solution {
    public int numTeams(int[] rating) {
        int result = 0;
        Map<String, Integer> memo = new HashMap<>();
        for (int i = 0; i < rating.length; i++) {
            result += dfs(rating, i, 1, true, memo);
            result += dfs(rating, i, 1, false, memo);
        }
        return result;
    }
    private int dfs(int[] rating, int i, int count, boolean isAsc, Map<String, Integer> memo) {
        String key = i + "," + count + "," + isAsc;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        if (count == 3) {
            return 1;
        }
        if (i == rating.length) {
            return 0;
        }
        int result = 0;
        for (int j = i+1; j < rating.length; j++) {
            if (isAsc && rating[j] > rating[i]) {
                result += dfs(rating, j, count+1, isAsc, memo);
            }
            if (!isAsc && rating[j] < rating[i]) {
                result += dfs(rating, j, count+1, isAsc, memo);
            }
        }
        memo.put(key, result);
        return memo.get(key);
    }
}

/**
For asc
for i
then for j = i+1 to n
if (num[j] > i)
dfs(j, count+1, asc_boolean)


 */