Problem of The Day: Kth Largest Element in an Array

Problem Statement

leetcode problem link

My Solution [TLE]

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)
        N = len(piles)
        def check(target):
            arr = piles[:]
            hours = 0
            while arr:
                arr[-1] -= target
                if arr[-1] <= 0:
                    arr.pop()
                hours += 1
                if hours > h:
                    return False


            return True

        ans = r
        while l <= r:
            mid = l + (r - l) // 2
            if check(mid):
                ans = mid
                r = mid - 1
            else:
                l = mid + 1

        return ans

Improve Algorithm [Accepted]

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)
        N = len(piles)
        def check(k):
            hours = 0
            for pile in piles:
                hours += (pile + k - 1) // k  # ceil(pile / k)
                if hours > h:
                    return False
            return True

        ans = r
        while l <= r:
            mid = l + (r - l) // 2
            if check(mid):
                ans = mid
                r = mid - 1
            else:
                l = mid + 1

        return ans

Time: O(N log m)

Editorial

Approach 2: Binary Search

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # Initalize the left and right boundaries
        left = 1
        right = max(piles)

        while left < right:
            # Get the middle index between left and right boundary indexes.
            # hour_spent stands for the total hour Koko spends.
            middle = (left + right) // 2
            hour_spent = 0

            # Iterate over the piles and calculate hour_spent.
            # We increase the hour_spent by ceil(pile / middle)
            for pile in piles:
                hour_spent += math.ceil(pile / middle)

            # Check if middle is a workable speed, and cut the search space by half.
            if hour_spent <= h:
                right = middle
            else:
                left = middle + 1

        # Once the left and right boundaries coincide, we find the target value,
        # that is, the minimum workable eating speed.
        return right