Maximum Number of Points From Grid Queries

Maximum Number of Points From Grid Queries - Problem

Array Two Pointers Breadth-First Search Union Find Sorting Heap (Priority Queue) Matrix Hard

You are given an m x n integer matrix grid and an array queries of size k.

Find an array answer of size k such that for each integer queries[i] you start in the top left cell of the matrix and repeat the following process:

If queries[i] is strictly greater than the value of the current cell that you are in, then you get one point if it is your first time visiting this cell, and you can move to any adjacent cell in all 4 directions: up, down, left, and right.
Otherwise, you do not get any points, and you end this process.

After the process, answer[i] is the maximum number of points you can get. Note that for each query you are allowed to visit the same cell multiple times.

Return the resulting array answer.

Input & Output

Example 1 — Basic Grid Exploration

$ Input: grid = [[1,2,3],[4,5,6]], queries = [3,4,2]

› Output: [2,3,1]

💡 Note: Query 3: Can visit cells with value < 3, which are (0,0)=1 and (1,0)=4? No, (1,0)=4. Only (0,0)=1 and (0,1)=2 are reachable → 2 points. Query 4: Can reach (0,0)=1, (0,1)=2, (1,0)=4? No, can't reach (1,0) from (0,1). Wait, let me recalculate. From (0,0) with query=3: visit (0,0)=1, then (0,1)=2. Can't go to (1,0)=4 since 4≥3. Answer is 2. Query 4: visit (0,0)=1, (0,1)=2, can't reach others. Answer is 2. Query 2: visit only (0,0)=1. Answer is 1.

Example 2 — Single Cell Grid

$ Input: grid = [[5]], queries = [3,6]

› Output: [0,1]

💡 Note: Query 3: Cannot start since grid[0][0]=5 ≥ 3, so 0 points. Query 6: Can visit grid[0][0]=5 since 5 < 6, so 1 point.

Example 3 — All Cells Accessible

$ Input: grid = [[1,1],[1,1]], queries = [2]

› Output: [4]

💡 Note: Query 2: All cells have value 1 < 2, so all 4 cells are reachable from (0,0), giving 4 points total.

Constraints

m == grid.length
n == grid[i].length
2 ≤ m, n ≤ 1000
4 ≤ m × n ≤ 10⁵
k == queries.length
1 ≤ k ≤ 10⁴
1 ≤ grid[i][j], queries[i] ≤ 10⁶

Visualization

Tap to expand

Key Insight: BFS exploration limited by value threshold determines reachable region size

Understanding the Visualization

Input Grid

Matrix with cell values and query thresholds

BFS Exploration

For each query, explore cells with value < threshold

Point Collection

Count unique reachable cells for each query

Key Takeaway

🎯 Key Insight: Process queries efficiently by sorting and using Union-Find to avoid redundant traversals

Asked in

G Google 12 f Meta 8

The key insight is to avoid redundant BFS by sorting both cells and queries, then processing queries incrementally. The Union-Find approach builds connectivity as cell thresholds increase. Time: O((m×n + k) × log(m×n)), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force BFS	O(k × m × n)	O(m × n)	Run BFS from (0,0) for each query independently
Union-Find with Sorting	O((m×n + k) × log(m×n))	O(m × n)	Sort cells and queries, process incrementally with Union-Find

Brute Force BFS — Algorithm Steps

For each query, initialize BFS queue with (0,0)
Explore neighbors with value < query threshold
Count all reachable unique cells

Visualization

Tap to expand

Step-by-Step Walkthrough

Query Processing

Process each query with independent BFS

BFS Exploration

Visit cells with value < query threshold

Count Results

Return count of reachable cells for each query

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int* solution(int** grid, int gridSize, int* gridColSize, int* queries, int queriesSize, int* returnSize) {
    int m = gridSize, n = gridColSize[0];
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int* answer = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int q = 0; q < queriesSize; q++) {
        if (grid[0][0] >= queries[q]) {
            answer[q] = 0;
            continue;
        }
        
        bool** visited = (bool**)malloc(m * sizeof(bool*));
        for (int i = 0; i < m; i++) {
            visited[i] = (bool*)calloc(n, sizeof(bool));
        }
        
        int queue[m * n][2];
        int front = 0, rear = 0;
        queue[rear][0] = 0;
        queue[rear][1] = 0;
        rear++;
        visited[0][0] = true;
        int count = 0;
        
        while (front < rear) {
            int row = queue[front][0];
            int col = queue[front][1];
            front++;
            count++;
            
            for (int d = 0; d < 4; d++) {
                int nr = row + directions[d][0];
                int nc = col + directions[d][1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] < queries[q]) {
                    visited[nr][nc] = true;
                    queue[rear][0] = nr;
                    queue[rear][1] = nc;
                    rear++;
                }
            }
        }
        
        answer[q] = count;
        
        for (int i = 0; i < m; i++) {
            free(visited[i]);
        }
        free(visited);
    }
    
    return answer;
}

int main() {
    // Simplified parsing for demonstration
    int grid[2][3] = {{1, 2, 3}, {4, 5, 6}};
    int* gridPtr[2] = {grid[0], grid[1]};
    int gridColSize[2] = {3, 3};
    int queries[] = {2, 5};
    int returnSize;
    
    int* result = solution(gridPtr, 2, gridColSize, queries, 2, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × m × n)

k queries × BFS traversal of m×n grid for each query

✓ Linear Growth

Space Complexity

O(m × n)

Visited array and BFS queue can store up to m×n cells

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force BFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler