Given an N * N grid consisting of empty cells (denoted by ‘1’) and obstacles (denoted by ‘0’), the task is to find the number of empty cells in which a mirror can be placed to view the east-side view of grid from the south-side.
Examples:
Input: mat[][] = {
{1, 1, 1},
{1, 1, 0},
{1, 0, 1}}
Output: 2
On clearly observing the image above, it can be seen that the mirror can be placed in only the cell (0, 0) and the cell (2, 2). If any other cell is chosen then the path of light is obstructed by the obstacles.
Input: mat[][] = {
{0, 1, 1},
{0, 1, 1},
{0, 1, 1}}
Output: 6
Naive approach: It is mentioned that the mirror can only be placed in an empty cell if all the cells on its right and below are empty. The naive approach will be to individually check each cell whether it satisfies the condition or not. This approach will take O(n3) time.
Efficient approach: Create two boolean arrays row[][] and col[][] where row[i][j] will store if all the cells in the ith row after the jth column (including it) are 1 else it will store false and col[i][j] will store true if all the cells in the jth column after the ith row (including it) are 1 else it will store false. Now, for every cell mat[i][j] if both row[i][j] and col[i][j] are true then the current cell is valid else it is not. Count all such valid cells and print the count in the end.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const int N = 3;// Function to return the number of cells// in which mirror can be placedint numberOfCells(int mat[][N]){ bool row[N][N] = { { false } }; bool col[N][N] = { { false } }; // Update the row array where row[i][j] // will store whether the current row i // contains all 1s in the columns // starting from j for (int i = 0; i < N; i++) { for (int j = N - 1; j >= 0; j--) { if (mat[i][j] == 1) { row[i][j] = (j + 1 < N) ? row[i][j + 1] : true; } else { row[i][j] = false; } } } // Update the column array where col[i][j] // will store whether the current column j // contains all 1s in the rows starting from i for (int j = 0; j < N; j++) { for (int i = N - 1; i >= 0; i--) { if (mat[i][j] == 1) { col[i][j] = (i + 1 < N) ? col[i + 1][j] : true; } else { col[i][j] = false; } } } // To store the required result int cnt = 0; // For every cell except the last // row and the last column for (int i = 0; i < N - 1; i++) { for (int j = 0; j < N - 1; j++) { // If the current cell is not blocked // and the light can travel from the // next row and the next column // then the current cell is valid if (row[i][j] && col[i][j]) { cnt++; } } } // For the last column for (int i = 0; i < N; i++) { if (col[i][N - 1]) cnt++; } // For the last row, note that the last column // is not taken into consideration as the bottom // right element has already been considered // in the last column previously for (int j = 0; j < N - 1; j++) { if (row[N - 1][j]) cnt++; } return cnt;}// Driver codeint main(){ int mat[][N] = { { 0, 1, 1 }, { 0, 1, 1 }, { 0, 1, 1 } }; cout << numberOfCells(mat); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{static int N = 3;// Function to return the number of cells// in which mirror can be placedstatic int numberOfCells(int mat[][]){ boolean [][]row = new boolean[N][N]; boolean [][]col = new boolean[N][N]; // Update the row array where row[i][j] // will store whether the current row i // contains all 1s in the columns // starting from j for (int i = 0; i < N; i++) { for (int j = N - 1; j >= 0; j--) { if (mat[i][j] == 1) { row[i][j] = (j + 1 < N) ? row[i][j + 1] : true; } else { row[i][j] = false; } } } // Update the column array where col[i][j] // will store whether the current column j // contains all 1s in the rows starting from i for (int j = 0; j < N; j++) { for (int i = N - 1; i >= 0; i--) { if (mat[i][j] == 1) { col[i][j] = (i + 1 < N) ? col[i + 1][j] : true; } else { col[i][j] = false; } } } // To store the required result int cnt = 0; // For every cell except the last // row and the last column for (int i = 0; i < N - 1; i++) { for (int j = 0; j < N - 1; j++) { // If the current cell is not blocked // and the light can travel from the // next row and the next column // then the current cell is valid if (row[i][j] && col[i][j]) { cnt++; } } } // For the last column for (int i = 0; i < N; i++) { if (col[i][N - 1]) cnt++; } // For the last row, note that the last column // is not taken into consideration as the bottom // right element has already been considered // in the last column previously for (int j = 0; j < N - 1; j++) { if (row[N - 1][j]) cnt++; } return cnt;}// Driver codepublic static void main(String[] args){ int mat[][] = { { 0, 1, 1 }, { 0, 1, 1 }, { 0, 1, 1 } }; System.out.print(numberOfCells(mat));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approachN = 3# Function to return the number of cells# in which mirror can be placeddef numberOfCells(mat): row = [[ False for i in range(N)] for i in range(N)] col = [[ False for i in range(N)] for i in range(N)] # Update the row array where row[i][j] # will store whether the current row i # contains all 1s in the columns # starting from j for i in range(N): for j in range(N - 1, -1, -1): if (mat[i][j] == 1): if j + 1 < N: row[i][j] = row[i][j + 1] else: row[i][j] = True else : row[i][j] = False # Update the column array where col[i][j] # will store whether the current column j # contains all 1s in the rows starting from i for j in range(N): for i in range(N - 1, -1, -1): if (mat[i][j] == 1): if i + 1 < N: col[i][j] = col[i + 1][j] else: col[i][j] = True else: col[i][j] = False # To store the required result cnt = 0 # For every cell except the last # row and the last column for i in range(N - 1): for j in range(N - 1): # If the current cell is not blocked # and the light can travel from the # next row and the next column # then the current cell is valid if (row[i][j] and col[i][j]): cnt += 1 # For the last column for i in range(N): if (col[i][N - 1]): cnt += 1 # For the last row, note that the last column # is not taken into consideration as the bottom # right element has already been considered # in the last column previously for j in range(N - 1): if (row[N - 1][j]): cnt += 1 return cnt# Driver codemat = [[0, 1, 1], [0, 1, 1], [0, 1, 1]]print(numberOfCells(mat))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;class GFG{static int N = 3;// Function to return the number of cells// in which mirror can be placedstatic int numberOfCells(int [,]mat){ bool [,]row = new bool[N, N]; bool [,]col = new bool[N, N]; // Update the row array where row[i,j] // will store whether the current row i // contains all 1s in the columns // starting from j for (int i = 0; i < N; i++) { for (int j = N - 1; j >= 0; j--) { if (mat[i, j] == 1) { row[i, j] = (j + 1 < N) ? row[i, j + 1] : true; } else { row[i, j] = false; } } } // Update the column array where col[i,j] // will store whether the current column j // contains all 1s in the rows starting from i for (int j = 0; j < N; j++) { for (int i = N - 1; i >= 0; i--) { if (mat[i, j] == 1) { col[i, j] = (i + 1 < N) ? col[i + 1, j] : true; } else { col[i, j] = false; } } } // To store the required result int cnt = 0; // For every cell except the last // row and the last column for (int i = 0; i < N - 1; i++) { for (int j = 0; j < N - 1; j++) { // If the current cell is not blocked // and the light can travel from the // next row and the next column // then the current cell is valid if (row[i, j] && col[i, j]) { cnt++; } } } // For the last column for (int i = 0; i < N; i++) { if (col[i, N - 1]) cnt++; } // For the last row, note that the last column // is not taken into consideration as the bottom // right element has already been considered // in the last column previously for (int j = 0; j < N - 1; j++) { if (row[N - 1, j]) cnt++; } return cnt;}// Driver codepublic static void Main(String[] args){ int [,]mat = {{ 0, 1, 1 }, { 0, 1, 1 }, { 0, 1, 1 }}; Console.Write(numberOfCells(mat));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approachlet N = 3;// Function to return the number of cells// in which mirror can be placedfunction numberOfCells(mat){ let row = new Array(N); let col = new Array(N); for(let i=0;i<N;i++) { row[i]=new Array(N); col[i]=new Array(N); for(let j=0;j<N;j++) { row[i][j]=0; col[i][j]=0; } } // Update the row array where row[i][j] // will store whether the current row i // contains all 1s in the columns // starting from j for (let i = 0; i < N; i++) { for (let j = N - 1; j >= 0; j--) { if (mat[i][j] == 1) { row[i][j] = (j + 1 < N) ? row[i][j + 1] : true; } else { row[i][j] = false; } } } // Update the column array where col[i][j] // will store whether the current column j // contains all 1s in the rows starting from i for (let j = 0; j < N; j++) { for (let i = N - 1; i >= 0; i--) { if (mat[i][j] == 1) { col[i][j] = (i + 1 < N) ? col[i + 1][j] : true; } else { col[i][j] = false; } } } // To store the required result let cnt = 0; // For every cell except the last // row and the last column for (let i = 0; i < N - 1; i++) { for (let j = 0; j < N - 1; j++) { // If the current cell is not blocked // and the light can travel from the // next row and the next column // then the current cell is valid if (row[i][j] && col[i][j]) { cnt++; } } } // For the last column for (let i = 0; i < N; i++) { if (col[i][N - 1]) cnt++; } // For the last row, note that the last column // is not taken into consideration as the bottom // right element has already been considered // in the last column previously for (let j = 0; j < N - 1; j++) { if (row[N - 1][j]) cnt++; } return cnt;}// Driver codelet mat = [[0, 1, 1 ], [ 0, 1, 1 ], [ 0, 1, 1 ]]; document.write(numberOfCells(mat));// This code is contributed by patel2127</script> |
Output:
6
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
