We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Number of Teams

Number: 1511

Difficulty: Medium

Paid? No

Companies: Goldman Sachs, IBM, Amazon

Problem Description

Given an array of unique soldier ratings, count the number of teams of 3 soldiers that can be formed such that their ratings are either strictly increasing or strictly decreasing. The team should be chosen such that for indices i, j, k (with i < j < k), either rating[i] < rating[j] < rating[k] or rating[i] > rating[j] > rating[k].

Key Insights

  • For each middle soldier at index j, count the number of valid soldiers to the left and right.
  • Two valid scenarios:
    • Increasing order: Count soldiers to left with rating less than rating[j] and soldiers to right with rating greater than rating[j].
    • Decreasing order: Count soldiers to left with rating greater than rating[j] and soldiers to right with rating less than rating[j].
  • The total team count is the sum over all j of (left_smaller * right_larger) + (left_larger * right_smaller).

Space and Time Complexity

Time Complexity: O(n^2) – For each soldier as the middle element, we traverse the left and right subarrays. Space Complexity: O(1) – Only a constant number of variables are used apart from the input array.

Solution

We iterate over each soldier and consider it as the middle soldier of the team. For each middle soldier at index j, we traverse all soldiers to its left to count how many have a smaller rating (left_smaller) and how many have a larger rating (left_larger). Similarly, we traverse all soldiers to the right of j to count soldiers with a larger rating (right_larger) and with a smaller rating (right_smaller). The number of valid increasing teams with j in the middle is given by left_smaller * right_larger, and the number of valid decreasing teams is left_larger * right_smaller. Adding these two gives the count for j. Finally, sum over all j to obtain the total count.

Code Solutions

# Function to count number of valid teams
def numTeams(rating):
    n = len(rating)  # number of soldiers
    count = 0       # initialize count of valid teams
    # Iterate through each soldier considering it as the middle soldier
    for j in range(1, n - 1):
        left_smaller = 0  # count of soldiers to the left with smaller rating
        left_larger = 0   # count of soldiers to the left with larger rating
        right_larger = 0  # count of soldiers to the right with larger rating
        right_smaller = 0 # count of soldiers to the right with smaller rating
        
        # Count for left side (indices 0 to j-1)
        for i in range(j):
            if rating[i] < rating[j]:
                left_smaller += 1
            elif rating[i] > rating[j]:
                left_larger += 1
        
        # Count for right side (indices j+1 to n-1)
        for k in range(j+1, n):
            if rating[k] > rating[j]:
                right_larger += 1
            elif rating[k] < rating[j]:
                right_smaller += 1
        
        # count valid teams with j as middle soldier
        count += (left_smaller * right_larger) + (left_larger * right_smaller)
    
    return count

# Example usage:
print(numTeams([2,5,3,4,1]))  # Expected output: 3
← Back to All Questions