Knowee
Questions
Features
Study Tools

Given a 2D character matrix grid, where grid[i][j] is either 'X', 'Y', or '.', return the number of submatrices that contains:grid[0][0]an equal frequency of 'X' and 'Y'.at least one 'X'. Example 1:Input: grid = [["X","Y","."],["Y",".","."]]Output: 3Explanation:Example 2:Input: grid = [["X","X"],["X","Y"]]Output: 0Explanation:No submatrix has an equal frequency of 'X' and 'Y'.Example 3:Input: grid = [[".","."],[".","."]]Output: 0Explanation:No submatrix has at least one 'X'. Constraints:1 <= grid.length, grid[i].length <= 1000grid[i][j] is either 'X', 'Y', or '.'.

Question

Given a 2D character matrix grid, where grid[i][j] is either 'X', 'Y', or '.', return the number of submatrices that contains:grid[0][0]an equal frequency of 'X' and 'Y'.at least one 'X'. Example 1:Input: grid = [["X","Y","."],["Y",".","."]]Output: 3Explanation:Example 2:Input: grid = [["X","X"],["X","Y"]]Output: 0Explanation:No submatrix has an equal frequency of 'X' and 'Y'.Example 3:Input: grid = [[".","."],[".","."]]Output: 0Explanation:No submatrix has at least one 'X'. Constraints:1 <= grid.length, grid[i].length <= 1000grid[i][j] is either 'X', 'Y', or '.'.

...expand
🧐 Not the exact question you are looking for?Go ask a question

Solution

This problem can be solved using dynamic programming. Here are the steps:

  1. Initialize a 3D array count of size n x n x 3 where n is the size of the grid. count[i][j][k] will store the frequency of character k in the submatrix from (0,0) to (i,j).

  2. Iterate over the grid from top to bottom, left to right. For each cell (i,j), update count[i][j] based on the value of grid[i][j] and count[i-1][j], count[i][j-1], and count[i-1][j-1].

  3. Initialize a counter result to 0. This will store the final result.

  4. Iterate over all possible submatrices of the grid. For each submatrix from (x1,y1) to (x2,y2), calculate the frequency of 'X' and 'Y' using count[x2][y2], count[x1-1][y2], count[x2][y1-1], and count[x1-1][y1-1]. If the frequency of 'X' is equal to the frequency of 'Y' and at least one 'X' is present, increment result.

  5. Return result.

This algorithm runs in O(n^4) time, where n is the size of the grid. It can be optimized to O(n^3) using prefix sums.

This problem has been solved

Similar Questions

You are given a matrix and an array. For each row of the given matrix, for each element of that row, check if it is present in the given array. Print the count of elements present for every row.Input FormatThe first line of input contains N, M - the size of the matrix. It is followed by N lines each containing M integers - elements of the matrix. The next line of the input contains the A - the size of the array. The next line of the input contains the array elements.Output FormatFor each row, print the count of the number of elements present, separated by a new line.Constraints1 <= N, M, A <= 100-100 <= mat[i][j], ar[i] <= 100ExampleInput3 45 9 -2 2-3 4 1 92 -2 1 -255 1 -2 2 6Output314ExplanationThe first row of the matrix is (5 9 -2 2), out of this, 3 elements (5 -2 2), except 9, are present in the given array (5 1 -2 2 6)The second row of the matrix is (-3 4 1 9), out of this, only 1 is present in the given array (5 1 -2 2 6)The third row of the matrix is (2 -2 1 -2), all the 4 elements are present in the given array (5 1 -2 2 6)

You are given a 2D matrix grid of size m x n. You need to check if each cell grid[i][j] is:Equal to the cell below it, i.e. grid[i][j] == grid[i + 1][j] (if it exists).Different from the cell to its right, i.e. grid[i][j] != grid[i][j + 1] (if it exists).Return true if all the cells satisfy these conditions, otherwise, return false. Example 1:Input: grid = [[1,0,2],[1,0,2]]Output: trueExplanation:All the cells in the grid satisfy the conditions.Example 2:Input: grid = [[1,1,1],[0,0,0]]Output: falseExplanation:All cells in the first row are equal.Example 3:Input: grid = [[1],[2],[3]]Output: falseExplanation:Cells in the first column have different values. Constraints:1 <= n, m <= 100 <= grid[i][j] <= 9

You've been provided with a matrix mat comprising lowercase English letters, arranged in n rows and m columns. Your objective is to determine whether it's feasible to choose four distinct columns from left to right such that the first column contains 'p', the second contains 'l', the third contains 'a', and the fourth contains 'y'. If all these conditions can be met, the function should return 1; otherwise, it should return 0.Example 1:Input:n = 1m = 4mat = [ ['p', 'l', 'a', 'y'] ]Output:1Explanation:Choose the columns numbered 1,2,3,4 and they satisfy the required condition as they have the characters 'p' in column 1, 'l' in column 2, 'a' in column 3, 'y' in column 4.

Write a Java program to print the unique elements along with their frequency in thegiven (4 x 4) integer and character matrices.Ex:Output:Element Frequency0 11 32 28 110 2

n = len(grid) x = sum(max(grid[i][j] for i in range(n)) for j in range(n)) y = sum(max(grid[j][i] for i in range(n)) for j in range(n)) z = sum(grid[i][j] > 0 for i in range(n) for j in range(n)) return sum([x,y,z])

1/1

Upgrade your grade with Knowee

Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.