We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Points From Grid Queries

Number: 2588

Difficulty: Hard

Paid? No

Companies: Meta, J.P. Morgan

Problem Description

Given an m x n integer matrix grid and an array queries, for each query value you start from the top left cell. During each query, if the query value is strictly greater than the value in the current cell, you score a point (if this is the first time visiting that cell) and move to adjacent cells (up, down, left, right). The process stops when you reach a cell with a value not strictly less than the query. You want to maximize the number of points collected. Return an array answer where answer[i] is the maximum points for queries[i].

Key Insights

  • The process can be reformulated as a region expansion (flood fill) that depends on the threshold defined by the query.
  • Instead of doing a BFS for each query independently, sort the queries and perform a single multi-source expansion (using a min-heap) from the top-left cell.
  • As the query value increases, the reachable region becomes larger.
  • Use a visited array to ensure each cell's point is counted only once.
  • Sorting the queries allows processing in an increasing order, so that cells reached for a smaller threshold remain valid for larger queries.

Space and Time Complexity

Time Complexity: O(m * n * log(m * n) + k * log k) where m * n is the number of cells and k is the number of queries. Space Complexity: O(m * n) for the visited structure and heap storage.

Solution

The idea is to process the queries in sorted order. For a given query threshold, we use a min-heap (priority queue) starting from the top-left cell, expanding to its neighbors using BFS. For each cell popped from the heap, if its value is less than the current query threshold, the cell is counted as reachable and its neighbors added to the heap if they haven't been visited. We maintain a cumulative count of reachable cells. Since queries are processed in increasing order, we continue expanding and only perform extra work when necessary. Finally, the result for each query is assigned based on the cumulative count at the time that query is processed.

Data structures used:

  • A min-heap to ensure we always process the smallest grid value first.
  • A visited matrix (or set) to avoid revisiting cells.
  • Sorting of queries along with their original indices to restore the output order.

Code Solutions

import heapq

def maxPoints(grid, queries):
    m, n = len(grid), len(grid[0])
    # Prepare result array for queries after sorting each query with its original index.
    sortedQueries = sorted([(q, i) for i, q in enumerate(queries)])
    result = [0] * len(queries)
    
    # Directions for movement: up, down, left, right.
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    # Min-heap for BFS expansion, starting with top-left cell.
    heap = [(grid[0][0], 0, 0)]
    visited = [[False] * n for _ in range(m)]
    visited[0][0] = True
    count = 0
    
    # Process each query in order of increasing threshold.
    for q, idx in sortedQueries:
        # Expand region as long as the smallest grid value in heap is less than current query threshold.
        while heap and heap[0][0] < q:
            value, x, y = heapq.heappop(heap)
            count += 1  # Increase reachable cells count.
            # Check all 4 neighbors.
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                    visited[nx][ny] = True
                    heapq.heappush(heap, (grid[nx][ny], nx, ny))
        # Assign the current count as the answer for this query.
        result[idx] = count
    return result

# Example usage:
grid = [[1,2,3],[2,5,7],[3,5,1]]
queries = [5,6,2]
print(maxPoints(grid, queries))  # Output should be: [5,8,1]
← Back to All Questions