Optimize Matrix Path Sum Queries

HardPython00:00

Practice interviewer

Your interviewer

In session

Interviewer

Welcome to the Python screen.

The question is on your right: Optimize Matrix Path Sum Queries. Read through the requirements first.

Run and submit your code as often as you need. You also have five interviewer messages this session - want to talk through your approach, or are you ready to start coding?

You need to log in / sign up to run or submit.

Problem

Given a 2D grid of non-negative integers grid with m rows and n columns, and a list of query cells queries, return the minimum path sum from the top-left cell (0, 0) to each queried cell. A path may move only right or down. The goal is to optimize performance when many queries are asked on the same grid.

Constraints

1 <= m, n <= 500
0 <= grid[r][c] <= 10^4
1 <= queries.length <= 10^5
0 <= queries[i][0] < m
0 <= queries[i][1] < n

Function Signature

def min_path_sum_queries(grid, queries):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output