Problem of The Day: Maximum Number of Points From Grid Queries

9 min read 1860 words

Problem Statement

leetcode problem link

• notes: hard problem, need to review

Solution [TLE]

class Solution:
    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
        ROWS = len(grid)
        COLS = len(grid[0])
        directions = [(0,1),(1,0),(0,-1),(-1,0)]

        def bfs(target):
            if grid[0][0] >= target:
                return 0
            queue = deque()
            queue.append([0, 0])
            ans = 0
            seen = set()
            while queue:
                row, col = queue.popleft()
                seen.add((row, col))
                for x, y in directions:
                    r, c = row + x, col + y
                    if 0 <= r < ROWS and 0 <= c < COLS and (r, c) not in seen and grid[r][c] < target:
                        queue.append([r, c])

            return len(seen)


        res = []
        for x in queries:
            res.append(bfs(x))
        return res

• time: O(kMN)
• space; O(M*N)

Editorial

Brute Force Approach [TLE]

class Solution:
    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
        row_count, col_count = len(grid), len(grid[0])
        result = [0] * len(queries)
        # Directions for moving in 4 directions (right, down, left, up)
        DIRECTIONS = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        # Iterate through each query value
        for queryIndex, queryValue in enumerate(queries):
            bfs_queue = deque([(0, 0)])
            visited = [[0] * col_count for _ in range(row_count)]
            # Mark the starting cell as visited
            visited[0][0] = 1
            points = 0

            # BFS traversal
            while bfs_queue:
                queue_size = len(bfs_queue)
                for _ in range(queue_size):
                    current_row, current_col = bfs_queue.popleft()

                    # If the current cell's value is greater than or equal to
                    # queryValue, stop expanding from here
                    if grid[current_row][current_col] >= queryValue:
                        continue

                    # Count the valid cell
                    points += 1

                    # Explore all four possible directions
                    for row_offset, col_offset in DIRECTIONS:
                        new_row = current_row + row_offset
                        new_col = current_col + col_offset

                        # Ensure the new position is within bounds and has not
                        # been visited
                        if (
                            0 <= new_row < row_count
                            and 0 <= new_col < col_count
                            and not visited[new_row][new_col]
                            and grid[new_row][new_col] < queryValue
                        ):
                            bfs_queue.append((new_row, new_col))
                            # Mark the new cell as visited
                            visited[new_row][new_col] = 1
                # Store the result for the current query
                result[queryIndex] = points
        return result

Approach 2: Sorting Queries + Min-Heap Expansion

from queue import PriorityQueue


class Solution:
    def maxPoints(self, grid: List[List[int]], queries: List[int]) -> List[int]:
        row_count, col_count = len(grid), len(grid[0])
        result = [0] * len(queries)
        # Directions for movement (right, down, left, up)
        DIRECTIONS = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        # Store queries along with their original indices to restore order
        # later
        sorted_queries = sorted([(val, idx) for idx, val in enumerate(queries)])

        # Min-heap (priority queue) to process cells in increasing order of
        # value
        min_heap = PriorityQueue()
        visited = [[False] * col_count for _ in range(row_count)]
        # Keeps track of the number of cells processed
        total_points = 0
        # Start from the top-left cell
        min_heap.put((grid[0][0], 0, 0))
        visited[0][0] = True

        # Process queries in sorted order
        for query_value, query_index in sorted_queries:
            # Expand the cells that are smaller than the current query value
            while not min_heap.empty() and min_heap.queue[0][0] < query_value:
                cellValue, current_row, current_col = min_heap.get()

                # Increment count of valid cells
                total_points += 1

                # Explore all four possible directions
                for row_offset, col_offset in DIRECTIONS:
                    new_row, new_col = (
                        current_row + row_offset,
                        current_col + col_offset,
                    )

                    # Check if the new cell is within bounds and not visited
                    if (
                        new_row >= 0
                        and new_col >= 0
                        and new_row < row_count
                        and new_col < col_count
                        and not visited[new_row][new_col]
                    ):
                        min_heap.put((grid[new_row][new_col], new_row, new_col))
                        # Mark as visited
                        visited[new_row][new_col] = True
            # Store the result for this query
            result[query_index] = total_points

        return result

public class Solution {
    public int[] MaxPoints(int[][] grid, int[] queries) {
        int rows = grid.Length, cols = grid[0].Length;
        int[][] directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];

        int[] result = new int[queries.Length];
        var sortedQueries = queries
            .Select((val, idx) => new Tuple<int, int>(val, idx))
            .OrderBy(q => q.Item1)
            .ToList();

        var minHeap = new SortedSet<(int val, int row, int col)>(Comparer<(int, int, int)>.Create((a, b) => a.Item1 == b.Item1 ? (a.Item2 == b.Item2 ? a.Item3 - b.Item3 : a.Item2 - b.Item2) : a.Item1 - b.Item1));
        bool[,] visited = new bool[rows, cols];

        minHeap.Add((grid[0][0], 0, 0));
        visited[0, 0] = true;
        int points = 0;

        foreach (var (queryVal, queryIdx) in sortedQueries) {
            while (minHeap.Count > 0 && minHeap.Min.val < queryVal) {
                var (val, row, col) = minHeap.Min;
                minHeap.Remove(minHeap.Min);
                points++;

                foreach (var dir in directions) {
                    int nr = row + dir[0], nc = col + dir[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr, nc]) {
                        minHeap.Add((grid[nr][nc], nr, nc));
                        visited[nr, nc] = true;
                    }
                }
            }
            result[queryIdx] = points;
        }

        return result;
    }
}