2503. Maximum Number of Points From Grid Queries


Problem Description

The problem presents us with a two-dimensional grid filled with integers and a list of queries. Each query represents an attempt to accumulate points by moving through the grid starting from the top-left cell. The rule to accumulate points is straightforward: you can only move to an adjacent cell (up, down, left, or right) if the query's value is strictly greater than the current cell's value, earning one point the first time you visit a cell. If it's not greater, you stop moving and can’t earn any points from that cell. The process for each query is independent of the others, and you can visit the same cell multiple times with different queries, potentially earning points each time.

The ultimate goal is to determine, for each query, the maximum number of points one can earn following the above rules.

Flowchart Walkthrough

First, let's analyze the problem using the Flowchart. Here's a step-by-step breakdown:

Is it a graph?

  • Yes: Although not explicitly structured as a traditional graph, the grid in the provided problem can be viewed as a graph where each cell potentially connects to adjacent cells.

Is it a tree?

  • No: The grid doesn't inherently form a single branching structure typical of trees. It potentially involves multiple branching possibilities from each cell.

Is the problem related to directed acyclic graphs (DAGs)?

  • No: The problem discusses maximizing points through grid queries and not processing tasks or dependencies as in DAGs.

Is the problem related to shortest paths?

  • No: The main objective is to maximize points, not to find the shortest path in the grid.

Does the problem involve connectivity?

  • Yes: There is an implicit need to determine the connections between points to ensure optimal movement or picking strategy throughout the grid.

Is the graph weighted?

  • No information on weights is implied in the query of maximizing points from the grid, suggesting an unweighted approach.

Conclusion: The problem aligns well with using BFS according to the characteristics of connectivity in an unweighted graph, as indicated by the flowchart. Thus, BFS should be utilized to explore potential paths or contiguous sections of the grid efficiently to maximize the points collected.

Intuition

Approaching the solution to this problem, we observe that the sequential nature of movements in the grid resembles a breadth-first traversal, where from any given cell, we can move in any of the four cardinal directions as long as the value of the query allows it.

One naive approach would be to start at the top-left cell and perform a breadth-first search for each query independently, but this would be inefficient, particularly when the grid and the number of queries are large. A better approach is needed to optimize the search across multiple queries.

The core intuition for an optimized approach lies in two observations:

  1. As we process the queries in ascending order, we can leverage the work from previous queries. Once a cell becomes reachable (i.e., its value is less than the current query value), it remains reachable for all subsequent queries.
  2. We can maintain a priority queue to track cells in the order of their values. This ensures that we only visit cells that are reachable for the current query value and avoid re-processing the entire grid unnecessarily.

Therefore, the steps we follow to arrive at the solution are:

  • First, sort the queries alongside their original indices. This allows us to process them in ascending order and maintain the ability to return answers in the order they were originally asked.
  • Use a priority queue (min-heap) to hold grid cells prioritized by their value along with their coordinates. We start by adding only the top-left cell to this queue.
  • Initialize a counter to track the number of distinct cells visited during the process.
  • For each query, processed in order, we:
    • Keep extracting cells from the priority queue as long as their value is less than the current query value. Visiting a cell for the first time under a specific query earns a point (as long as the cell's value is less than the query value).
    • For each cell visited, we check its adjacent cells and if any of them are unvisited and reachable, we add them to the priority queue.
  • The counter value after processing a specific query corresponds to the maximum points for that query. We store this in the corresponding index in the answer array.
  • Return the answer array after processing all queries. The use of a priority queue and the early termination condition for cells values that do not meet the threshold optimize this approach.

With this approach, the solution scales better with the size of the grid and the number of queries, providing an efficient way to calculate the maximum number of points for each query.

Learn more about Breadth-First Search, Union Find, Two Pointers, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The provided code uses a few classic data structures and algorithms to implement an efficient solution to the problem:

  • Priority Queue (Min-Heap): The heapq module in Python (used as heappop and heappush in the code) provides an implementation of the priority queue data structure. The priority queue is essential to manage the cells in the order of their grid values, ensuring that we always process the smallest-valued cell that qualifies for the current query.

  • Breadth-First Search (BFS): This search pattern is used because we explore the grid from the top-left working outwards, considering cells one step away (adjacent cells) from any given cell. Whenever a cell's value is less than the current query value, we can move to its neighbors.

  • List Comprehension and Tuple Packing: The code uses list comprehension to create lists (like vis and ans) and tuple packing to store the multiple pieces of data together for each cell (such as grid value, x-coordinate, and y-coordinate).

  • Boolean Matrix for Visited Cells: A matrix vis of the same dimensions as the grid is initialized to False and used to mark whether or not a cell has been visited during the traversal for the present query value. Once a cell is visited, it is marked True.

  • Sorting the Queries: The queries are sorted to ensure that we process them in ascending order. This is beneficial as once a cell becomes reachable for a certain query value, it remains reachable for all subsequent queries.

  • Counter: A variable cnt is used to keep track of how many points we can get for the current query. Every time we pop a cell from the priority queue that satisfies the query condition, we increment cnt.

In the code, we translate these concepts into implementation steps as follows:

  1. Initialize the dimensions m and n for the grid, sort the queries with their original index, and create an answer list ans initialized with zeros to hold the result.
  2. Prepare the priority queue q by pushing the top-left cell onto it.
  3. Initialize the cnt counter to 0 and a vis matrix to False indicating all cells are initially unvisited.
  4. Start iterating over the sorted queries. For each (v, k) pair (value and index from the sorted queries):
    • While the priority queue is not empty and the top cell value is less than v:
      • Pop the cell from the priority queue, increment cnt, and check its adjacent cells.
      • For each adjacent cell (x, y) that is within the grid boundaries and unvisited, push it onto the priority queue and mark it as visited.
    • After all reachable cells for this query value have been visited and added, update the answer array at the index k with the current counter value cnt.
  5. Once all queries have been processed, return the ans array.

The algorithm effectively uses the earlier processes and stored state (priority queue and visited matrix) to reduce redundant computations as it progresses through each query, making the overall approach efficient for this type of grid traversal and accumulation problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach described above. Imagine we have a grid and a list of queries as follows:

Grid:

4 3 2
5 3 1

Queries: [3, 4, 6]

Now let's walk through this example following the solution steps:

  1. Initialize the grid dimensions (m = 2, n = 3), sort the queries alongside their original indices, and prepare an answer list ans to hold the results. After sorting, the queries and their indices are: [(3, 0), (4, 1), (6, 2)].

  2. Initialize the priority queue q with the top-left cell (4, 0, 0) where 4 is the value and (0, 0) are its coordinates.

  3. Initialize the counter (cnt) to 0 and the visited matrix (vis) with all values as False.

  4. Start iterating through the sorted queries. For the first query (3, 0):

    • The top of the priority queue has a cell value 4, which is not less than the query value 3, so we don't extract any cell from the queue for this query. Thus, the counter stays at 0, and ans[0] is set to 0.
  5. For the second query (4, 1):

    • Now, the top of the priority queue is (4, 0, 0), which is equal to the query value 4, so again, we do not visit new cells, leaving counter 0. Hence, ans[1] stays 0.
  6. For the last query (6, 2):

    • The top of the priority queue is (4, 0, 0) and 4 is now less than the query value 6. We pop this cell from the queue, increment cnt to 1, and mark it as visited.
    • We explore adjacent cells [5, 3] and [3, 3]. Both are less than 6, so they get pushed to the queue, and cnt increases to 3.
    • Continue to pop cells from the priority queue as long as their value is less than 6, but all remaining cells have already been visited, so we stop.
    • Therefore, ans[2] is set to 3.
  7. The final ans array after processing all queries is [0, 0, 3].

This walkthrough demonstrates the application of the provided solution approach on a simplified version of the given problem, showcasing how sorting queries and using a priority queue can efficiently determine the maximum points earned for each query.

Solution Implementation

1from heapq import heappop, heappush
2from itertools import pairwise
3
4class Solution:
5    def maxPoints(self, points_grid: List[List[int]], queries: List[int]) -> List[int]]:
6        # Get the dimensions of the grid
7        rows, cols = len(points_grid), len(points_grid[0])
8      
9        # Sort the queries along with their indices for efficient access
10        sorted_queries = sorted((value, index) for index, value in enumerate(queries))
11      
12        # Initialize the answer list to have the same size as queries with default 0 values
13        results = [0] * len(sorted_queries)
14      
15        # Initialize the priority queue with the starting point (0,0)
16        priority_queue = [(points_grid[0][0], 0, 0)]
17      
18        # Counter to keep track of how many points have been visited
19        points_count = 0
20      
21        # Initialize the visited matrix to track visited cells in the grid
22        visited = [[False] * cols for _ in range(rows)]
23        visited[0][0] = True
24      
25        # Iterate over the sorted queries
26        for value, index in sorted_queries:
27            # Process cells from the priority queue until the cell’s value is less than the query value
28            while priority_queue and priority_queue[0][0] < value:
29                # Pop the smallest value cell from the priority queue
30                _, current_row, current_col = heappop(priority_queue)
31              
32                # Increment the visited points counter
33                points_count += 1
34              
35                # Use the pairwise utility to iterate over the adjacent cells
36                for delta_row, delta_col in pairwise((-1, 0, 1, 0, -1)):
37                    # Calculate the adjacent cell's row and column
38                    adjacent_row, adjacent_col = current_row + delta_row, current_col + delta_col
39                  
40                    # Check if the adjacent cell is inside the grid and not visited
41                    if 0 <= adjacent_row < rows and 0 <= adjacent_col < cols and not visited[adjacent_row][adjacent_col]:
42                        # Push the adjacent cell into the priority queue
43                        heappush(priority_queue, (points_grid[adjacent_row][adjacent_col], adjacent_row, adjacent_col))
44                      
45                        # Mark the adjacent cell as visited
46                        visited[adjacent_row][adjacent_col] = True
47          
48            # After processing the priority queue, assign the number of points visited to the results
49            results[index] = points_count
50      
51        # Return the results list with the number of points visited for each query
52        return results
53
1import java.util.Arrays;
2import java.util.PriorityQueue;
3
4class Solution {
5
6    public int[] maxPoints(int[][] grid, int[] queries) {
7        int queryLength = queries.length;
8        // Array to store value and index of each query
9        int[][] sortedQueries = new int[queryLength][2];
10        // Fill the array with queries and their original indexes
11        for (int i = 0; i < queryLength; ++i) {
12            sortedQueries[i] = new int[] { queries[i], i };
13        }
14        // Sort queries based on their values
15        Arrays.sort(sortedQueries, (a, b) -> a[0] - b[0]);
16      
17        // Initialize the answer array to store results for each query
18        int[] answers = new int[queryLength];
19        // Get the dimensions of the grid
20        int rows = grid.length;
21        int columns = grid[0].length;
22        // Keep track of visited cells
23        boolean[][] visited = new boolean[rows][columns];
24        // Mark the start cell as visited
25        visited[0][0] = true;
26      
27        // Priority queue to store cell values with coordinates, sorted by value
28        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
29        // Offer the first cell to the priority queue
30        queue.offer(new int[] { grid[0][0], 0, 0 });
31      
32        // Array to help navigate through neighbors of a cell
33        int[] directions = new int[] { -1, 0, 1, 0, -1 };
34        // Counter to keep the count of cells processed
35        int count = 0;
36      
37        // Process each sorted query
38        for (int[] query : sortedQueries) {
39            int queryValue = query[0];
40            int queryIndex = query[1];
41          
42            // Poll cells with value less than the current query value
43            while (!queue.isEmpty() && queue.peek()[0] < queryValue) {
44                int[] cell = queue.poll();
45                // Increment the count whenever a cell is polled
46                ++count;
47              
48                // Navigate to neighboring cells
49                for (int i = 0; i < 4; ++i) {
50                    int newRow = cell[1] + directions[i];
51                    int newColumn = cell[2] + directions[i + 1];
52                  
53                    // If the neighbor is within bounds and not visited yet
54                    if (newRow >= 0 && newRow < rows 
55                        && newColumn >= 0 && newColumn < columns 
56                        && !visited[newRow][newColumn]) {
57                        // Mark as visited
58                        visited[newRow][newColumn] = true;
59                        // Add to queue with values
60                        queue.offer(new int[] { grid[newRow][newColumn], newRow, newColumn });
61                    }
62                }
63            }
64            // Save counter value in the answer array corresponding to the original query index
65            answers[queryIndex] = count;
66        }
67        // Return the answer array with counts for each query
68        return answers;
69    }
70}
71
1#include <vector>
2#include <queue>
3#include <algorithm>
4#include <cstring>
5using namespace std;
6
7class Solution {
8public:
9    // Directions array for moving up, right, down, left in a grid
10    const int directions[5] = {-1, 0, 1, 0, -1};
11
12    // This function will return the max points from the top-left corner to the cells
13    // value greater than or equal to the given queries on a grid
14    vector<int> maxPoints(vector<vector<int>>& grid, vector<int>& queries) {
15        int querySize = queries.size();
16        vector<pair<int, int>> sortedQueries(querySize);
17      
18        // Attach each query value to its original index
19        for (int i = 0; i < querySize; ++i) {
20            sortedQueries[i] = {queries[i], i};
21        }
22        // Sort the queries in ascending order
23        sort(sortedQueries.begin(), sortedQueries.end());
24
25        // Initialize the answer vector to store results for the original queries order
26        vector<int> answer(querySize);
27        int rows = grid.size(), cols = grid[0].size();
28        bool visited[rows][cols];
29        // Set visited status of all cells to false
30        memset(visited, 0, sizeof visited);
31
32        // Start from the top-left corner
33        visited[0][0] = true;
34        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> minHeap;
35        minHeap.push({grid[0][0], 0, 0});
36      
37        int exploredCount = 0; // Number of cells explored that satisfy a given query
38      
39        for (auto& queryPair : sortedQueries) {
40            int requiredValue = queryPair.first; // The minimum required value for this query
41            int originalIndex = queryPair.second; // The original index of this query
42
43            // Explore cells until we meet the condition of the current query
44            while (!minHeap.empty() && get<0>(minHeap.top()) < requiredValue) {
45                auto [value, row, col] = minHeap.top();
46                minHeap.pop();
47                exploredCount++; // Increment the count of explored cells
48              
49                // Explore adjacent cells
50                for (int i = 0; i < 4; ++i) {
51                    int newRow = row + directions[i], newCol = col + directions[i + 1];
52                    // Check for valid and unvisited adjacent cells
53                    if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && !visited[newRow][newCol]) {
54                        visited[newRow][newCol] = true;
55                        minHeap.push({grid[newRow][newCol], newRow, newCol});
56                    }
57                }
58            }
59            // Record the number of cells explored that satisfy the query's condition
60            answer[originalIndex] = exploredCount;
61        }
62      
63        // Return the result in the order of the original queries
64        return answer;
65    }
66};
67
1type Grid = number[][];
2type Query = number[];
3type HeapElement = [number, number, number]; // Typing for clarity: [value, row, col]
4
5// Directions array for moving up, right, down, and left in a grid
6const directions: number[] = [-1, 0, 1, 0, -1];
7
8// Function that returns the max points from the top-left corner to the cells
9// with a value greater than or equal to the given queries on a grid
10function maxPoints(grid: Grid, queries: Query): number[] {
11    const querySize: number = queries.length;
12    let sortedQueries: Array<[number, number]> = new Array(querySize);
13
14    // Attach each query value to its original index
15    for (let i = 0; i < querySize; ++i) {
16        sortedQueries[i] = [queries[i], i];
17    }
18
19    // Sort the queries in ascending order
20    sortedQueries.sort((a, b) => a[0] - b[0]);
21
22    // Initialize the answer array to store results for the original queries order
23    let answers: number[] = new Array(querySize).fill(0);
24    const rows: number = grid.length,
25          cols: number = grid[0].length;
26
27    // Array to check if a cell has been visited
28    let visited: boolean[][] = Array.from({ length: rows }, () => Array(cols).fill(false));
29
30    // Start from the top-left corner and mark it as visited
31    visited[0][0] = true;
32
33    // Priority queue (using a min-heap) for BFS
34    let minHeap: HeapElement[] = [];
35    minHeap.push([grid[0][0], 0, 0]);
36
37    // Function to insert elements into the min-heap, maintaining sorted order
38    function pushToMinHeap(element: HeapElement) {
39        minHeap.push(element);
40        minHeap.sort(([valueA], [valueB]) => valueB - valueA); // sort to keep the smallest element at the end
41    }
42
43    let exploredCount: number = 0; // Number of cells explored that satisfy a given query
44
45    // Function to extract the smallest element from the min-heap
46    function popFromMinHeap(): HeapElement {
47        return <HeapElement>minHeap.pop(); // Explicit type assertion for clarity
48    }
49
50    for (let [requiredValue, originalIndex] of sortedQueries) {
51        // Explore cells until we meet the condition of the current query
52        while (minHeap.length > 0 && minHeap[minHeap.length - 1][0] < requiredValue) {
53            let [value, row, col] = popFromMinHeap();
54            exploredCount++; // Increment the count of explored cells
55
56            // Explore adjacent cells
57            for (let i = 0; i < 4; ++i) {
58                let newRow = row + directions[i],
59                    newCol = col + directions[i + 1];
60
61                // Check for valid and unvisited adjacent cells
62                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && !visited[newRow][newCol]) {
63                    visited[newRow][newCol] = true;
64                    pushToMinHeap([grid[newRow][newCol], newRow, newCol]);
65                }
66            }
67        }
68
69        // Record the number of cells explored that satisfy the query's condition
70        answers[originalIndex] = exploredCount;
71    }
72
73    // Return the result in the order of the original queries
74    return answers;
75}
76

Time and Space Complexity

Time Complexity

The time complexity of the provided code depends on several factors:

  • Sorting the queries: The sort operation has a complexity of O(Q log Q), where Q is the number of queries.
  • Priority queue operations: The main loop iterates potentially over all cells in the grid, performing heappush and heappop operations. Insertion and removal from a heap have complexity O(log K), where K is the number of elements in the heap.
  • Checking neighboring cells: For each cell, it checks at most 4 neighbors, adding a constant factor.

Assuming that in the worst case each cell is visited and added to the priority queue, the complexity becomes O(MN log(MN)). Therefore, combining this with the sort, we get a time complexity of O(Q log Q + MN log(MN)), where M and N are the dimensions of the grid.

Space Complexity

The space complexity is determined by:

  • The heap/priority queue: In the worst case, it can hold all cells in the grid, resulting in O(MN).
  • The visited grid: An M x N boolean grid for visited cells also results in O(MN).
  • The answer list: Storing the result for each query gives O(Q).

Therefore, the total space complexity is O(MN + Q), with MN for the visited matrix and the priority queue, and Q being the size of the answer list.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

In a binary min heap, the maximum element can be found in:


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!


Load More