Amount Of New Area Painted Each Day - Leetcode Solution

Problem Statement: Given a 2D grid of size m x n and an integer k. You have to paint a rectangular area of size k x k with a color marker. The color marker can only paint contiguous squares of size k x k completely, and it cannot paint beneath already painted squares. The marker can only be painted in one row at a time i.e., after finishing painting the first row of the k x k area, you can move to the next row and start painting there. No two tiles of the same color can share a common edge, and the color marker is a perfect rectangle of size k x k. Return an array of m x n in which each element represents the number of new squares painted blue each day by using the marker.

Example:

Input: m = 3, n = 3, k = 2, queries = [[0,0],[1,1],[2,2]] Output: [4,4,0] Explanation: Day 1: Paint the rectangular area with a color marker [0,0] -> [1,1] [0,1] -> [1,2]. The blue square is 4. Day 2: Paint the rectangular area with a color marker [1,0] -> [2,1] [1,1] -> [2,2]. The blue square is 4. Day 3: Paint the rectangular area [2,0] -> [3,1] [2,1] -> [3,2]. No new square is painted blue today.

Solution: To solve this problem, we need to keep track of the already painted squares and the squares that will be painted in the current day. Then, we update the total painted squares for each day.

We can start by initializing an m x n grid with all values set to zero. The painted grid will be used to store which squares have been painted so far. We will also initialize a variable called painted_counter, which will be used to keep track of the total number of painted squares.

Next, we need to iterate over the queries array. For each query, we will paint the k x k rectangle on the grid if it doesn't overlap with any previously painted squares. If it does overlap, we will not paint any new squares. To check if the rectangle overlaps with any previously painted squares, we will check if any of the squares in the rectangle have a value of 1 in the painted grid.

If we paint any new squares, we will update the painted grid and increase the painted_counter by the number of new squares painted. We will append the painted_counter to an array called daily_counters, which will store the total painted squares for each day.

At the end, we will return the daily_counters array.

Time Complexity: The time complexity of the algorithm is O(mnk^2), where m is the number of rows in the grid, n is the number of columns in the grid, and k is the size of the color marker. We can have at most m * n / (k * k) painting operations, and each operation will require iterating over the k * k rectangle of squares.

Space Complexity: The space complexity of the algorithm is O(m*n), which is the size of the painted grid.

Implementation:

class Solution: def paintingPlan(self, m: int, n: int, k: int, queries: List[List[int]]) -> List[int]: painted = [[0] * n for _ in range(m)] painted_counter = 0 daily_counters = []

    for r, c in queries:
        new_squares = set()
        
        # Paint the k x k rectangle
        for i in range(k):
            for j in range(k):
                if r + i < m and c + j < n and painted[r + i][c + j] == 0:
                    new_squares.add((r + i, c + j))
                else:
                    new_squares.clear()
                    break
        
        # Check if any of the squares in the rectangle have already been painted
        overlap = False
        for i, j in new_squares:
            if painted[i][j] == 1:
                overlap = True
                break
                
        # Paint the new squares
        if not overlap and len(new_squares) > 0:
            painted_counter += len(new_squares)
            daily_counters.append(painted_counter)
            for i, j in new_squares:
                painted[i][j] = 1
        else:
            daily_counters.append(painted_counter)
    
    return daily_counters

1