Skip to content

Latest commit

 

History

History
101 lines (83 loc) · 3.13 KB

_3212. Count Submatrices With Equal Frequency of X and Y.md

File metadata and controls

101 lines (83 loc) · 3.13 KB

3212. Count Submatrices With Equal Frequency of X and Y

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Completed during Weekly Contest 405 (q3)

Back to top

First completed : July 07, 2024

Last updated : July 07, 2024

Related Topics : Array, Matrix, Prefix Sum

Acceptance Rate : 51.31 %

Preface: During the contest, I ran out of time. I later did the question after the contest completed, revising my approach and successfully earning the AC.

Notes from during the contest

    - contains origin val
    - Cannot have 1x1 submatrix cause at least one X and equal XY

    Start on X spots and expand?
    Match X with nearest Y above, below, left, right?

    Weird prefix sum x2? Count by row and col, then also do a cumulative one to 
    get the instantaneous difference?

    Wait si this a area based prefix sum where you take a corner's full sum, add 
    the other corner, and remove the sides due to the overlap?

     add||   subtract
    ====||======================||
        ||                      ||
     s  ||                      ||
     u  ||         add          ||
     b  ||                      ||
    ====||======================||add?

Notes from after

    I'm dumb lol. I interpretted the "contains grid[0][0]" as inside the box from (x1, y1) 
    to (x2, y2) inclusive, there must be at least one value equal to the value found at 
    grid[0][0]. 

    I realized after that it meant that each submatrix MUST START at (0, 0), simplifying 
    the question HEAVILY.

Solutions

Python

m3212 q3 POST CONTEST.py

class Solution:
    def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
        xes = [[0] * len(grid[0]) for _ in range(len(grid))]
        yes = [[0] * len(grid[0]) for _ in range(len(grid))]

        for r in range(len(grid)) :
            for c in range(len(grid[0])) :
                if r > 0 :
                    xes[r][c] += xes[r - 1][c]
                    yes[r][c] += yes[r - 1][c]
                if c > 0 :
                    xes[r][c] += xes[r][c - 1]
                    yes[r][c] += yes[r][c - 1]
                if r > 0 and c > 0 :
                    xes[r][c] -= xes[r - 1][c - 1]
                    yes[r][c] -= yes[r - 1][c - 1]

                match grid[r][c] :
                    case 'X' :
                        xes[r][c] += 1
                    case 'Y' :
                        yes[r][c] += 1

        output = 0
        for x in range(len(grid)) :
            for y in range(len(grid[0])) :
                if xes[x][y] == yes[x][y] and xes[x][y] :
                    output += 1

        return output