Problem statement

https://binarysearch.com/problems/Win-After-Last-Round/

Solution

Not correct statement, if we have [0, 0], then whenever swimmer do, result will be [1, 2], and we have only one winner, however expected answer is 2. Probably it means that in the last round some person can have equal number of points. Or in case [1, 1, 3] answer is also 3.

Let us sort all swimmers and give 1 to the best, 2 to the next and so on. Then maximum among all these values will be the minimum number of points winner can have. Then we traverse swimmers once again and check if we can make them winning.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums):
        if not nums: return 0
        nums = sorted(nums)
        n = len(nums)
        val = max(x + n - i for i, x in enumerate(nums))
        ans = 0
        for x in nums:
            if 0 < val - x <= n: ans += 1
        
        return ans