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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Points From Grid Queries

Difficulty: Hard

Problem Description

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.

Key Insights

  • The problem involves traversing a grid starting from the top-left corner based on certain query values.
  • Points can be earned by visiting cells with values less than the query value.
  • The traversal can be visualized as a breadth-first search (BFS) where cells are visited based on the query condition.
  • The queries can be processed efficiently by sorting them and performing the BFS for each unique query in order.
  • The maximum number of points for each query is determined by the number of valid cells visited.

Space and Time Complexity

Time Complexity: O(m * n + k log k), where m * n is the size of the grid, and k log k accounts for sorting the queries. Space Complexity: O(m * n), for the BFS queue and visited cells storage.

Solution

The solution uses a breadth-first search (BFS) approach to explore the grid starting from the top-left cell. For each query, we check if the value of the top-left cell is less than the query. If it is, we initialize a BFS that allows movement to adjacent cells if their values are also less than the query. We maintain a count of unique cells visited to compute the score for each query.

Code Solutions

from collections import deque

def maxPoints(grid, queries):
    m, n = len(grid), len(grid[0])
    k = len(queries)
    answers = [0] * k
    indexed_queries = sorted((val, idx) for idx, val in enumerate(queries))
    visited = [[False] * n for _ in range(m)]
    
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    for query_value, original_index in indexed_queries:
        if grid[0][0] >= query_value:
            continue
        
        queue = deque([(0, 0)])
        visited[0][0] = True
        count = 1
        
        while queue:
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] < query_value:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
                    count += 1
        
        answers[original_index] = count
    
    return answers
← Back to All Questions