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 givenk
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.