1395. Count Number of Teams

UnknownView on LeetCode

Array Math Dynamic Programming

Time: O(n²)

Space: O(1)

Intuition

Count valid teams of three soldiers (i<j<k) with ratings[i]<ratings[j]<ratings[k] or ratings[i]>ratings[j]>ratings[k].

Algorithm

1For each middle element j: count elements to its left that are smaller/larger, and elements to its right that are smaller/larger.
2Teams = left_smaller * right_larger + left_larger * right_smaller.

Common Pitfalls

•O(n^2) with nested loops is sufficient for n<=200. For each j, scan left and right.

1395.cs

// Approach: For each middle element count smaller/larger elements to its left and right; multiply and sum for both ascending and descending triples.
// Time: O(n²) Space: O(1)

public class Solution
{
    public int NumTeams(int[] rating)
    {
        int ans = 0;

        for (int i = 1; i < rating.Length - 1; i++)
        {
            int smaller_left = 0, bigger_left = 0;

            for (int j = 0; j < i; j++)
            {
                if (rating[j] < rating[i])
                    smaller_left++;
                else if (rating[j] > rating[i])
                    bigger_left++;
            }

            int smaller_right = 0, bigger_right = 0;
            for (int j = i + 1; j < rating.Length; j++)
            {
                if (rating[j] < rating[i])
                    smaller_right++;
                else if (rating[j] > rating[i])
                    bigger_right++;
            }

            ans += smaller_left * bigger_right + bigger_left * smaller_right;
        }

        return ans;
    }
}

Was this solution helpful?