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

Find Champion I

Number: 3188

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given a tournament of n teams (numbered 0 to n - 1) and a 0-indexed 2D boolean matrix grid where for every pair of teams (i, j) with i ≠ j, grid[i][j] == 1 indicates that team i is stronger than team j, determine the champion. A team is declared the champion if there is no other team that is stronger than it.

Key Insights

  • Each team is compared against every other team based on the grid values.
  • A team qualifies as champion if no other team has a winning result over it.
  • The problem guarantees that if team a is stronger than team b and team b is stronger than team c, then team a is stronger than team c (transitivity).
  • A brute force check for each team across all other teams solves the problem efficiently within the given constraints.

Space and Time Complexity

Time Complexity: O(n^2) due to the nested loops checking each team against all others. Space Complexity: O(1) as the solution does not require extra space proportional to input size.

Solution

The solution involves iterating through each team and treating it as a potential champion. For each team, we check if there is any opponent such that grid[opponent][candidate] == 1, which would mean that the opponent is stronger than the candidate. If no such opponent is found, the candidate is the champion. The transitivity of the relationships guarantees that the identified champion is indeed the overall champion.

Code Solutions

# Python solution with line-by-line comments

def findChampion(grid):
    n = len(grid)  # Number of teams in the tournament
    # Iterate through each team assumed as potential champion
    for candidate in range(n):
        isChampion = True  # Assume candidate is champion initially
        # Check against every other team
        for opponent in range(n):
            if candidate != opponent:
                # If any opponent is stronger than the candidate
                if grid[opponent][candidate] == 1:
                    isChampion = False  # Disqualify candidate
                    break  # No need to check further
        if isChampion:
            return candidate  # Return candidate if no stronger opponent found
    return -1  # This should never be reached as per problem guarantees

# Example usage:
grid = [[0, 1], [0, 0]]
print(findChampion(grid))
← Back to All Questions