Problem Statement in English


Approach


Step 1: Calculate if a k allows Koko to eat piles within h hours

  • Step 1.1: Calculate hours taken to eat piles[i] for a given k


Solution in Python


class Solution:
    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
        ROWS = len(grid)
        COLS = len(grid[0])

        minheap = [(grid[0][0], 0, 0)]

        db = {}
        seen = set([(0, 0)])

        moves = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        total = 0

        for query in sorted(queries):
            while minheap:
                v, x, y = minheap[0]

                if v >= query:
                    break

                heappop(minheap)
                total += 1

                for dx, dy in moves:
                    nx, ny = x + dx, y + dy
                    t = (nx, ny)

                    if 0 <= nx < ROWS and 0 <= ny < COLS and t not in seen:
                        heappush(minheap, (grid[nx][ny], nx,ny))
                        seen.add(t)

            db[query] = total

        res = []

        for query in queries:
            res.append(db[query])

        return res

Complexity

  • Time: $O()$

  • Space: $O()$


Mistakes I Made


And we are done.