Maximum Number of Points from Grid Queries
Asked at Uber
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.
Asked At
| 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.
Visual walkthrough for grid [[1,3],[2,4]] and queries [2, 3, 5]:
Sort queries: [2, 3, 5].
Query 2: start with (0,0) val=1 < 2, count=1. Push neighbors (0,1) val=3 and (1,0) val=2. Heap top is 2 >= 2. Stop. Count=1.
Query 3: continue. Pop (1,0) val=2 < 3, count=2. Push (1,1) val=4. Pop (0,1) val=3 >= 3. Stop. Count=2.
Query 5: pop (0,1) val=3 < 5, count=3. Pop (1,1) val=4 < 5, count=4. Heap empty. Count=4.
Result: [1, 2, 4].
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.
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
import 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.