algoadvance

Leetcode 2923. Find Champion I

Problem Statement

You are given an array of integers nums which represents the scores of various players in a game. A Champion player is defined as a player whose score is the strictly greater than all other players’ scores. Your task is to determine the Champion player’s score. If no such player exists (i.e., no single player has a strictly greater score than the others), return -1.

Clarifying Questions

1. Input Constraints:
   • What is the maximum length of the array nums?
   • Are there any constraints on the values of the elements in nums?
2. Output Clarifications:
   • If there are multiple players with the same highest score, should we return -1 because there’s no single champion?
   • Do we need to consider negative scores, or are all scores non-negative?

Based on typical assumptions in such problems:

• Array nums can have a length anywhere from 0 to 1000.
• The integers in nums can be any 32-bit signed integers.

Strategy

1. Initialize Variables:
   • Maintain two variables, maxScore to keep track of the highest score found, and secondMaxScore for the second highest score.
2. Traverse the Array:
   • Iterate through the array to populate maxScore and secondMaxScore.
   • Update these variables as follows:
     • If the current score is higher than maxScore, update secondMaxScore to be maxScore and then update maxScore to be the current score.
     • Otherwise, if the current score is higher than secondMaxScore but less than maxScore, update secondMaxScore.
3. Determine Result:
   • After the traversal, if maxScore is still greater than secondMaxScore, then maxScore is the champion’s score.
   • Otherwise, return -1.

Code

#include <vector>
#include <algorithm>

using namespace std;

int findChampion(const vector<int>& nums) {
    if (nums.empty()) return -1;
    
    int maxScore = INT_MIN;
    int secondMaxScore = INT_MIN;
    
    for (int score : nums) {
        if (score > maxScore) {
            secondMaxScore = maxScore;
            maxScore = score;
        } else if (score > secondMaxScore && score < maxScore) {
            secondMaxScore = score;
        }
    }
    
    // If secondMaxScore is still INT_MIN, it means there was no second distinct score.
    return maxScore > secondMaxScore ? maxScore : -1;
}

int main() {
    vector<int> nums = {3, 6, 1, 5};
    // Expected output: 6, since 6 is strictly greater than all other scores
    
    int championScore = findChampion(nums);
    if (championScore == -1) {
        cout << "No single champion found." << endl;
    } else {
        cout << "Champion's score: " << championScore << endl;
    }

    return 0;
}

Time Complexity

• Time Complexity: O(n), where n is the number of elements in nums. We only traverse the array once.
• Space Complexity: O(1). We use a fixed amount of extra space regardless of the input size.

This approach ensures that we efficiently and correctly determine the Champion’s score or conclude that no Champion exists.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?