Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1395.html

1395. Count Number of Teams

Level

Medium

Description

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

  • Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
  • A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

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
  • 1 <= n <= 200
  • 1 <= rating[i] <= 10^5

Solution

The object of this problem is to find the number of monotone subsequences that have length 3 of the given array rating. Since the length of rating does not exceed 200, this problem can be solved by brute force. A solution of dynamic programming also exists.

Consider two cases, where each subsequence is monotonically increasing or monotonically decreasing. First consider the monotonically increasing case. Create an array dp of length n, wnere dp[i] represents the number of elements in subarray rating[0..i - 1] that are less than rating[i]. Loop over i from 1 to n - 1. For each i, loop over j from i - 1 to 0. If rating[i] > rating[j], then increase dp[i] by 1, and at the same time, if dp[j] > 0, then there exist several elements before j that are less than rating[j], so add dp[j] to the number of teams. After the loop, the number of teams that are monotically increasing can be obtained.

For the monotonically decrease case, the logic is almost the same except that rating[i] < rating[j] is used instead of rating[i] > rating[j].

Finally, return the number of teams of both cases.

  • class Solution {
    public int numTeams(int[] rating) {
        return numTeams(rating, true) + numTeams(rating, false);
    }

    public int numTeams(int[] rating, boolean increase) {
        int teams = 0;
        int length = rating.length;
        int[] dp = new int[length];
        for (int i = 1; i < length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                boolean flag = increase ? rating[i] > rating[j] : rating[i] < rating[j];
                if (flag) {
                    dp[i]++;
                    if (dp[j] > 0)
                        teams += dp[j];
                }
            }
        }
        return teams;
    }
}

  • class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n, ans = len(rating), 0
        for j in range(1, n - 1):
            ia = ib = ka = kb = 0
            for i in range(j):
                if rating[i] < rating[j]:
                    ia += 1
                elif rating[i] > rating[j]:
                    ib += 1
            for k in range(j + 1, n):
                if rating[j] < rating[k]:
                    ka += 1
                elif rating[j] > rating[k]:
                    kb += 1
            ans += ia * ka + ib * kb
        return ans



  • class Solution {
public:
    int numTeams(vector<int>& rating) {
        int n = rating.size(), ans = 0;
        for (int j = 1; j < n - 1; ++j) {
            int ia = 0, ib = 0, ka = 0, kb = 0;
            for (int i = 0; i < j; ++i) {
                if (rating[i] < rating[j])
                    ++ia;
                else if (rating[i] > rating[j])
                    ++ib;
            }
            for (int k = j + 1; k < n; ++k) {
                if (rating[j] < rating[k])
                    ++ka;
                else if (rating[j] > rating[k])
                    ++kb;
            }
            ans += ia * ka + ib * kb;
        }
        return ans;
    }
};

  • func numTeams(rating []int) int {
	n, ans := len(rating), 0
	for j := 1; j < n-1; j++ {
		ia, ib, ka, kb := 0, 0, 0, 0
		for i := 0; i < j; i++ {
			if rating[i] < rating[j] {
				ia++
			} else if rating[i] > rating[j] {
				ib++
			}
		}
		for k := j + 1; k < n; k++ {
			if rating[j] < rating[k] {
				ka++
			} else if rating[j] > rating[k] {
				kb++
			}
		}
		ans += ia*ka + ib*kb
	}
	return ans
}

  • class BinaryIndexedTree {
    private n: number;
    private c: number[];

    constructor(n: number) {
        this.n = n;
        this.c = new Array(n + 1).fill(0);
    }

    public update(x: number, v: number): void {
        while (x <= this.n) {
            this.c[x] += v;
            x += x & -x;
        }
    }

    public query(x: number): number {
        let s = 0;
        while (x > 0) {
            s += this.c[x];
            x -= x & -x;
        }
        return s;
    }
}

function numTeams(rating: number[]): number {
    let nums = [...rating];
    nums.sort((a, b) => a - b);
    const n = rating.length;
    let m = 0;
    for (let i = 0; i < n; ++i) {
        if (i === 0 || nums[i] !== nums[i - 1]) {
            nums[m++] = nums[i];
        }
    }
    nums = nums.slice(0, m);
    const search = (x: number): number => {
        let l = 0;
        let r = m;
        while (l < r) {
            const mid = (l + r) >> 1;
            if (nums[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l + 1;
    };
    let ans = 0;
    const tree1 = new BinaryIndexedTree(m);
    const tree2 = new BinaryIndexedTree(m);
    for (const x of rating) {
        tree2.update(search(x), 1);
    }
    for (let i = 0; i < n; ++i) {
        const x = search(rating[i]);
        tree1.update(x, 1);
        tree2.update(x, -1);
        const l = tree1.query(x - 1);
        const r = n - i - 1 - tree2.query(x);
        ans += l * r;
        ans += (i - l) * (n - i - 1 - r);
    }
    return ans;
}

All Problems

All Solutions