LeetCode 2503 - Maximum Number of Points From Grid Queries

LeetCode Problem 2503

Difficulty: 🔴 Hard
Topics: Array, Two Pointers, Breadth-First Search, Union-Find, Sorting, Heap (Priority Queue), Matrix

Solution

Problem Understanding

The problem asks us to calculate the maximum number of points that can be collected in a grid for a series of queries. The grid is represented by an m x n matrix of integers, where each cell has a value. For each query value q, we start at the top-left cell (0,0) and attempt to move to adjacent cells (up, down, left, right) under the condition that the current cell’s value is strictly less than q. When visiting a cell for the first time under this condition, we earn a point. If the current cell's value is equal to or greater than the query, we cannot move further along that path.

The inputs are:

• grid: an m x n matrix of integers with values between 1 and 10^6.
• queries: an array of integers between 1 and 10^6 with length up to 10^4.

The output is an array of integers where each element corresponds to the maximum number of points obtainable for the respective query.

Constraints indicate the grid can be large, up to 10^5 cells, and queries are numerous. This makes a naive BFS per query infeasible, as it would yield a time complexity of O(k * m * n) which is too slow.

Important edge cases include:

1. The top-left cell is greater than or equal to the query, yielding zero points.
2. All cells in the grid have the same value.
3. Queries smaller than all grid values or larger than all grid values.

Approaches

The brute-force solution would be to perform a BFS or DFS for each query independently. This approach is correct, as it explores all reachable cells under the query's constraint and counts points. However, with up to 10^4 queries and 10^5 cells, the worst-case complexity becomes O(k * m * n), which is prohibitive.

The key insight for an optimal solution is that the number of points for smaller queries is always a subset of the points for larger queries. This suggests a global traversal order. By sorting cells by value and using a priority queue or Union-Find structure, we can incrementally mark cells as reachable and efficiently answer all queries by processing them in increasing order.

Approach	Time Complexity	Space Complexity	Notes
Brute Force BFS per Query	O(k * m * n)	O(m * n)	BFS or DFS from top-left for each query independently
Optimal Sorted Incremental BFS	O(m * n + k * log k)	O(m * n)	Sort queries and cells, use min-heap to expand reachable cells incrementally

Algorithm Walkthrough

1. Flatten the grid into a list of (value, row, col) tuples and sort them by value.
2. Sort the queries along with their original indices.
3. Initialize a min-heap (priority queue) starting with the top-left cell (0,0) and a visited set to track cells that have been counted.
4. Iterate over queries in ascending order:

a. For each query value q, expand the heap to include all reachable cells with value less than q.

b. Each newly visited cell increments a counter of points.

c. Store the total count in the result array at the query's original index. 5. Return the result array.

Why it works: By processing queries and cells in sorted order, every cell is only visited once in the order of increasing values. This guarantees that for each query, we count all points accessible strictly below the query value, and the incremental approach ensures no redundant computation.

Python Solution

from typing import List
import heapq

class Solution:
    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
        m, n = len(grid), len(grid[0])
        cells = [(grid[i][j], i, j) for i in range(m) for j in range(n)]
        cells.sort()
        
        sorted_queries = sorted((q, i) for i, q in enumerate(queries))
        res = [0] * len(queries)
        
        visited = [[False]*n for _ in range(m)]
        heap = []
        count = 0
        
        if grid[0][0] < sorted_queries[-1][0]:
            heapq.heappush(heap, (grid[0][0], 0, 0))
            visited[0][0] = True
        
        directions = [(1,0), (-1,0), (0,1), (0,-1)]
        idx = 0  # Pointer in cells list
        
        for q, qi in sorted_queries:
            while idx < len(cells) and cells[idx][0] < q:
                val, i, j = cells[idx]
                if not visited[i][j]:
                    heapq.heappush(heap, (val, i, j))
                    visited[i][j] = True
                idx += 1
            
            while heap and heap[0][0] < q:
                val, i, j = heapq.heappop(heap)
                count += 1
                for di, dj in directions:
                    ni, nj = i + di, j + dj
                    if 0 <= ni < m and 0 <= nj < n and not visited[ni][nj]:
                        heapq.heappush(heap, (grid[ni][nj], ni, nj))
                        visited[ni][nj] = True
            res[qi] = count
        
        return res

The Python solution flattens the grid, sorts both cells and queries, and uses a min-heap to expand reachable cells incrementally. This ensures each cell is considered only once and queries are processed efficiently.

Go Solution

package main

import (
    "container/heap"
    "sort"
)

type Cell struct {
    val, r, c int
}

type PQ []Cell

func (pq PQ) Len() int { return len(pq) }
func (pq PQ) Less(i, j int) bool { return pq[i].val < pq[j].val }
func (pq PQ) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PQ) Push(x interface{}) { *pq = append(*pq, x.(Cell)) }
func (pq *PQ) Pop() interface{} {
    old := *pq
    n := len(old)
    x := old[n-1]
    *pq = old[0 : n-1]
    return x
}

func maxPoints(grid [][]int, queries []int) []int {
    m, n := len(grid), len(grid[0])
    cells := make([]Cell, 0, m*n)
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            cells = append(cells, Cell{grid[i][j], i, j})
        }
    }
    sort.Slice(cells, func(i, j int) bool { return cells[i].val < cells[j].val })
    
    type Query struct {
        val, idx int
    }
    sortedQueries := make([]Query, len(queries))
    for i, q := range queries {
        sortedQueries[i] = Query{q, i}
    }
    sort.Slice(sortedQueries, func(i, j int) bool { return sortedQueries[i].val < sortedQueries[j].val })
    
    res := make([]int, len(queries))
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    
    h := &PQ{}
    heap.Init(h)
    if grid[0][0] < sortedQueries[len(sortedQueries)-1].val {
        heap.Push(h, Cell{grid[0][0], 0, 0})
        visited[0][0] = true
    }
    
    directions := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}
    count := 0
    idx := 0
    
    for _, q := range sortedQueries {
        for idx < len(cells) && cells[idx].val < q.val {
            c := cells[idx]
            if !visited[c.r][c.c] {
                heap.Push(h, c)
                visited[c.r][c.c] = true
            }
            idx++
        }
        for h.Len() > 0 && (*h)[0].val < q.val {
            c := heap.Pop(h).(Cell)
            count++
            for _, d := range directions {
                ni, nj := c.r + d[0], c.c + d[1]
                if ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj] {
                    heap.Push(h, Cell{grid[ni][nj], ni, nj})
                    visited[ni][nj] = true
                }
            }
        }
        res[q.idx] = count
    }
    
    return res
}

The Go solution mirrors the Python approach, using a heap interface and struct types. Boolean arrays track visited cells, and care is taken with slice initialization.

Worked Examples

Example 1: grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2]

Sorted cells: `[(1,0,0),(1,2,2),(2,0,1),(2,1,0),(3,