2503. Maximum Number of Points from Grid Queries
Asked at Uber
Difficulty
Hard
Time
O(m*n*log(m*n) + k*log(k))
Space
O(m*n + k)
Pattern
Array
Companies
1
Problem
You are given an m x n grid of positive integers and an array queries. For each query value q, you start at the top-left cell (0, 0) and try to collect points.
You may step from a cell to any of its 4 neighbors (up, down, left, right). You may also revisit cells as many times as you like. The rule is: you can only enter a cell if q is strictly greater than the value stored in that cell. The first time you visit a cell you earn 1 point; revisiting it earns nothing. The moment you stand on a cell whose value is >= q, the process stops.
For each query, return the maximum number of points you can collect. The answer array must match the original order of queries.
Reach cells smaller than the query
Constraints
- ●
m == grid.length - ●
n == grid[i].length - ●
2 <= m, n <= 1000 - ●
4 <= m * n <= 10^5 - ●
k == queries.length - ●
1 <= k <= 10^4 - ●
1 <= grid[i][j], queries[i] <= 10^6
Examples
grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2][5,8,1]grid = [[5,2,1],[1,1,2]], queries = [3][0]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Uber | Hard | View all Uber questions → |
How to Think About It
Brute force: for each query, run a BFS/DFS from (0,0) counting cells with value < query. Time: O(q * m * n) where q is number of queries. Too slow for large grids.
Key insight: sort queries in ascending order and process them incrementally. As the query threshold increases, more cells become accessible. Use a min-heap to always expand the cheapest cell first.
The BFS + heap approach: start with (0,0) in a min-heap. Pop the smallest value cell. If its value < current query, add it to the count and push its unvisited neighbors. Repeat until the heap top is >= query.
Union-Find alternative: sort all cells by value and queries by value. Use union-find to connect cells as they become "active." For each query, activate all cells with value < query and union with active neighbors. Count the size of the component containing (0,0).
Why sort queries: processing queries in ascending order lets you reuse work. Cells activated for query k are still active for query k+1. You never deactivate cells, only add more.
Optimal Approach
Step 1: Create a sorted copy of queries with their original indices.
Step 2: Initialize a min-heap with (grid[0][0], 0, 0) and a visited set.
Step 3: Process queries in ascending order. For each query:
- While the heap is not empty and the top value < query:
- Pop the cell, increment count
- Push unvisited neighbors (up, down, left, right) with value < query
- Store the count for this query
Step 4: Return results in the original query order.
Walkthrough for grid [[1,3],[2,4]], queries [2,3,5]:
- Sorted queries: [(2,0), (3,1), (5,2)]
- Heap: [(1,0,0)], visited: {(0,0)}
- Query 2: pop 1<2, count=1. Push (3,0,1) and (2,1,0). Heap: [(2,1,0),(3,0,1)]. Top=2>=2. Result[0]=1.
- Query 3: pop 2<3, count=2. Push (4,1,1). Heap: [(3,0,1),(4,1,1)]. Top=3>=3. Result[1]=2.
- Query 5: pop 3<5, count=3. Pop 4<5, count=4. Heap empty. Result[2]=4.
Time: O(m*n*log(m*n) + q*log(q)) for heap operations and sorting. Space: O(m*n + q) for the heap, visited set, and result array.
Sort queries, grow one heap
What Trips People Up in Real Interviews
Processing queries in the given order instead of sorting. Without sorting, you can't reuse work between queries. Always sort queries and map results back to original order using indices.
Using BFS with a queue instead of a min-heap. A regular queue doesn't guarantee you expand cells in order of increasing value. A min-heap does, which is essential for the incremental activation to work correctly.
Forgetting to mark cells as visited. Without a visited set, you might process the same cell multiple times, leading to incorrect counts and infinite loops in the BFS.
Not handling the edge case where (0,0) itself has a value >= query. In that case, the count is 0 because you can't even start. The BFS/heap should handle this naturally if implemented correctly.
Confusing "strictly less than" with "less than or equal to." The problem says values strictly less than the query. grid[i][j] < query, not <=. This is a subtle but critical distinction.
Solution Code
O(m*n*log(m*n) + k*log(k)) timeimport heapq
def maxPoints(grid, queries):
m, n = len(grid), len(grid[0])
sorted_queries = sorted([(q, i) for i, q in enumerate(queries)])
result = [0] * len(queries)
heap = [(grid[0][0], 0, 0)]
visited = {(0, 0)}
count = 0
for q, orig_idx in sorted_queries:
while heap and heap[0][0] < q:
val, r, c = heapq.heappop(heap)
count += 1
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited:
visited.add((nr, nc))
heapq.heappush(heap, (grid[nr][nc], nr, nc))
result[orig_idx] = count
return resultFrequently Asked Questions
What is the Maximum Number of Points from Grid Queries problem?
Given an m x n grid of positive integers and an array of queries, for each query find how many cells have values strictly less than the query value, starting from the top-left corner and moving to adjacent cells. Return the results for all queries.
How do you solve Maximum Number of Points from Grid Queries?
The optimal approach runs in O(m*n*log(m*n) + k*log(k)) time and O(m*n + k) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Maximum Number of Points from Grid Queries?
Maximum Number of Points from Grid Queries is asked at Uber. It is a hard difficulty problem.
What are common mistakes on Maximum Number of Points from Grid Queries?
- Processing queries in the given order instead of sorting. Without sorting, you can't reuse work between queries. Always sort queries and map results back to original order using indices.
- Using BFS with a queue instead of a `min-heap`. A regular queue doesn't guarantee you expand cells in order of increasing value. A `min-heap` does, which is essential for the incremental activation to work correctly.
- Forgetting to mark cells as visited. Without a visited set, you might process the same cell multiple times, leading to incorrect counts and infinite loops in the BFS.
- Not handling the edge case where (0,0) itself has a value >= query. In that case, the count is 0 because you can't even start. The BFS/heap should handle this naturally if implemented correctly.
- Confusing "strictly less than" with "less than or equal to." The problem says values strictly less than the query. `grid[i][j] < query`, not `<=`. This is a subtle but critical distinction.