Question 1

32 comments on “Question 1”

• 
  

  Prajwal

  int maximalSquare(vector<vector>& matrix) {
  int n=matrix.size();
  int m=matrix[0].size();

  vector<vector> dp(matrix.size(), vector(matrix[0].size(), 0));
  int ans=0;
  for(int i=0; i<n; i++){
  for(int j=0; j<m; j++){
  if(i==0 or j==0){
  if(matrix[i][j]=='1'){
  dp[i][j]=1;
  ans=max(ans, dp[i][j]);
  }

  }else{
  if(matrix[i][j]=='1'){
  dp[i][j]=min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1]))+1;
  ans=max(ans, dp[i][j]);
  }
  }
  }

  }

  return ans*ans;
  }

  Log in to Reply
• 
  

  Sri

  x=[[1,1,0,1,0],[1,1,1,1,1],[1,0,1,1,1],[1,0,1,1,0],[1,1,1,1,1]] #input
  count=0
  for i in range(len(x)):
  c=x[i].count(0)
  if c>count:
  count=c
  print(count)
  m=[] #to store matrix
  for i in range(len(x)-count):
  w=[] #to store a single row
  for j in range(len(x)-count):
  w.append(1)
  m.append(w)
  print(m)

  Log in to Reply
• 
  

  SHRUTI

  #include
  #define bool int
  #define R 6
  #define C 5
  using namespace std;

  void printMaxSubSquare(bool M[R][C])
  {
  int i, j;
  int S[R][C];
  int max_of_s, max_i, max_j;

  /* Set first column of S[][]*/
  for (i = 0; i < R; i++)
  S[i][0] = M[i][0];

  /* Set first row of S[][]*/
  for (j = 0; j < C; j++)
  S[0][j] = M[0][j];

  /* Construct other entries of S[][]*/
  for (i = 1; i < R; i++) {
  for (j = 1; j < C; j++) {
  if (M[i][j] == 1)
  S[i][j]
  = min({ S[i][j – 1], S[i – 1][j],
  S[i – 1][j – 1] })
  + 1; // better of using min in case of
  // arguments more than 2
  else
  S[i][j] = 0;
  }
  }

  /* Find the maximum entry, and indexes of maximum entry
  in S[][] */
  max_of_s = S[0][0];
  max_i = 0;
  max_j = 0;
  for (i = 0; i < R; i++) {
  for (j = 0; j < C; j++) {
  if (max_of_s < S[i][j]) {
  max_of_s = S[i][j];
  max_i = i;
  max_j = j;
  }
  }
  }

  cout < max_i – max_of_s; i–) {
  for (j = max_j; j > max_j – max_of_s; j–) {
  cout << M[i][j] << " ";
  }
  cout << "\n";
  }
  }

  int main()
  {
  bool M[R][C] = { { 0, 1, 1, 0, 1 }, { 1, 1, 0, 1, 0 },
  { 0, 1, 1, 1, 0 }, { 1, 1, 1, 1, 0 },
  { 1, 1, 1, 1, 1 }, { 0, 0, 0, 0, 0 } };

  printMaxSubSquare(M);
  }

  Log in to Reply
• 
  

  Nageswar

  n=int(input())
  a=[]
  b=0
  for i in range(n):
  a.append(list(map(int,input().split())))
  m=min(n,len(a[0]))
  for i in range(1,n):
  for j in range(i,n):
  x = a[j – i:j + 1]
  for k in range(i,m):
  o=k-i
  xx=True
  for l in x:
  if sum(l[o:k+1])!=i+1:
  xx=False
  break
  if xx==True:
  b=max(b,i+1)
  if b==0:
  for i in a:
  if 1 in i:
  exit(print([1]))
  for i in range(b):
  for j in range(b):
  print(1,end=” “)
  print()

  Log in to Reply
• 
  

  Dipesh

  class Solution(object):
  def maximalSquare(self, matrix):
  “””
  :type matrix: List[List[str]]
  :rtype: int
  “””
  rows = len(matrix)
  if rows == 0: return 0
  cols = len(matrix[0])

  dp=[[0 for i in range(cols+1)] for j in range(rows+1)]
  larg = 0

  for i in range(1,rows+1):
  for j in range(1,cols+1):
  if matrix[i-1][j-1] == ‘1’:
  dp[i][j] == 1 + min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])
  if dp[i][j] > larg :
  larg = dp[i][j]
  return larg*larg

  Log in to Reply
• 
  

  Satvik

  def max_square_submatrix(matrix):
  rows = len(matrix)
  cols = len(matrix[0])
  dp = [[0 for _ in range(cols)] for _ in range(rows)]
  max_size = 0

  # Initialize the first row and column of the dp array
  for i in range(rows):
  dp[i][0] = matrix[i][0]
  if dp[i][0] == 1:
  max_size = 1
  for j in range(cols):
  dp[0][j] = matrix[0][j]
  if dp[0][j] == 1:
  max_size = 1

  # Fill in the rest of the dp array
  for i in range(1, rows):
  for j in range(1, cols):
  if matrix[i][j] == 1:
  dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
  max_size = max(max_size, dp[i][j])
  return max_size

  Log in to Reply
• 
  

  Prabhanshu

  static int maxSquare(int n, int m, int mat[][]){
  // code here

  int[][] dp = new int[n][m];
  int ans =0;
  for(int i=0; i<n; i++){

  for(int j=0; j<m; j++){

  if(i==0 || j==0){
  dp[i][j] = mat[i][j];
  }
  else{
  if(mat[i][j] == 1){
  dp[i][j] = Math.min(dp[i-1][j] , Math.min(dp[i][j-1] , dp[i-1][j-1]))+1;
  }
  }

  ans = Math.max(ans , dp[i][j]);
  }
  }
  return ans;
  }

  Log in to Reply
• 
  

  SIVAGURU

  #include
  #define bool int
  #define R 6
  #define C 5

  void printMaxSubSquare (bool M[R][C])
  {
  int i, j;
  int S[R][C];
  int max_of_s, max_i, max_j;

  /* Set first column of S[][]*/
  for (i = 0; i < R; i++)
  S[i][0] = M[i][0];

  /* Set first row of S[][]*/
  for (j = 0; j < C; j++)
  S[0][j] = M[0][j];

  /* Construct other entries of S[][]*/
  for (i = 1; i < R; i++)
  {
  for (j = 1; j < C; j++)
  {
  if (M[i][j] == 1)
  S[i][j] = min (S[i][j – 1], S[i – 1][j], S[i – 1][j – 1]) + 1;
  else
  S[i][j] = 0;
  }
  }

  /* Find the maximum entry, and indexes of maximum entry
  in S[][] */
  max_of_s = S[0][0];
  max_i = 0;
  max_j = 0;
  for (i = 0; i < R; i++)
  {
  for (j = 0; j < C; j++)
  {
  if (max_of_s max_i – max_of_s; i–)
  {
  for (j = max_j; j > max_j – max_of_s; j–)
  {
  printf (“%d “, M[i][j]);
  }
  printf (“\n”);
  }
  }

  /* UTILITY FUNCTIONS */
  /* Function to get minimum of three values */
  int min (int a, int b, int c)
  {
  int m = a;
  if (m > b)
  m = b;
  if (m > c)
  m = c;
  return m;
  }

  /* Driver function to test above functions */
  int main ()
  {
  bool M[R][C] = { {0, 1, 1, 0, 1},
  {1, 1, 0, 1, 0},
  {0, 1, 1, 1, 0},
  {1, 1, 1, 1, 0},
  {1, 1, 1, 1, 1},
  {0, 0, 0, 0, 0}
  };

  printMaxSubSquare (M);
  getchar ();
  }

  Log in to Reply
• 
  

  lalit

  #include
  #define bool int
  #define R 6
  #define C 5

  void printMaxSubSquare (bool M[R][C])
  {
  int i, j;
  int S[R][C];
  int max_of_s, max_i, max_j;

  /* Set first column of S[][]*/
  for (i = 0; i < R; i++)
  S[i][0] = M[i][0];

  /* Set first row of S[][]*/
  for (j = 0; j < C; j++)
  S[0][j] = M[0][j];

  /* Construct other entries of S[][]*/
  for (i = 1; i < R; i++)
  {
  for (j = 1; j < C; j++)
  {
  if (M[i][j] == 1)
  S[i][j] = min (S[i][j – 1], S[i – 1][j], S[i – 1][j – 1]) + 1;
  else
  S[i][j] = 0;
  }
  }

  /* Find the maximum entry, and indexes of maximum entry
  in S[][] */
  max_of_s = S[0][0];
  max_i = 0;
  max_j = 0;
  for (i = 0; i < R; i++)
  {
  for (j = 0; j < C; j++)
  {
  if (max_of_s max_i – max_of_s; i–)
  {
  for (j = max_j; j > max_j – max_of_s; j–)
  {
  printf (“%d “, M[i][j]);
  }
  printf (“\n”);
  }
  }

  /* UTILITY FUNCTIONS */
  /* Function to get minimum of three values */
  int min (int a, int b, int c)
  {
  int m = a;
  if (m > b)
  m = b;
  if (m > c)
  m = c;
  return m;
  }

  /* Driver function to test above functions */
  int main ()
  {
  bool M[R][C] = { {0, 1, 1, 0, 1},
  {1, 1, 0, 1, 0},
  {0, 1, 1, 1, 0},
  {1, 1, 1, 1, 0},
  {1, 1, 1, 1, 1},
  {0, 0, 0, 0, 0}
  };

  printMaxSubSquare (M);
  getchar ();
  }

  Log in to Reply
• 
  

  culbgaming12

  #include

  using namespace std;

  int min(int a, int b, int c)
  {
  if (a < b && a < c)
  {
  return a;
  }

  if (b < a && b < c)
  {
  return b;
  }

  if (c < a && c > row;
  cin >> col;

  int mat[row][col];
  int dp[row + 1][col + 1];
  for (int i = 0; i < row; i++)
  {
  for (int j = 0; j > mat[i][j];
  }
  }

  for (int i = 0; i <= row; i++)
  {
  for (int j = 0; j <= col; j++)
  {
  dp[0][j] = 0;
  dp[i][0] = 0;
  }
  }

  for (int i = 1; i <= row; i++)
  {
  for (int j = 1; j <= col; j++)
  {
  if (mat[i – 1][j – 1] == 1)
  {
  dp[i][j] = 1 + min(dp[i][j – 1], dp[i – 1][j], dp[i – 1][j – 1]);
  }

  else
  {
  dp[i][j] = 0;
  }
  }
  }

  // Max size of the sub square matrix

  int res = 0;
  int max_i = 0;
  int max_j = 0;

  for (int i = 1; i <= row; i++)
  {
  for (int j = 1; j <= col; j++)
  {
  if (res max_i – res; i–)
  {
  for (int j = max_j; j > max_j – res; j–)
  {
  cout << mat[i – 1][j – 1] << " ";
  }

  cout << endl;
  }

  return 0;
  }

  Log in to Reply
• 
  

  Dharmendra

  Java Solution:
  public int maximalSquare(char[][] matrix) {
  int row = matrix.length;
  int col = matrix[0].length;
  int ans = 0;

  int[][] dp = new int[row][col];
  for(int i=row-1; i>=0; i–) {
  for(int j=col-1; j>=0; j–) {
  if(i == row-1 && j == col-1) {
  dp[i][j] = Character.getNumericValue(matrix[i][j]);
  } else if(i == row-1) {
  dp[i][j] = Character.getNumericValue(matrix[i][j]);
  } else if(j == col-1) {
  dp[i][j] = Character.getNumericValue(matrix[i][j]);
  } else {
  if(matrix[i][j] == ‘0’)
  dp[i][j] = 0;
  else {
  int min = Math.min(dp[i][j+1], dp[i+1][j]);
  min = Math.min(min, dp[i+1][j+1]);
  dp[i][j] = min+1;
  }
  // if(dp[i][j] > ans)
  // ans = dp[i][j];
  }
  }
  }

  ans = findMax(dp);

  return ans*ans;
  }

  public static int findMax(int[][] dp) {
  int max = dp[0][0];
  for (int i = 0; i < dp.length; i++) {
  for (int j = 0; j max) {
  max = dp[i][j];
  }
  }
  }
  return max;
  }

  Log in to Reply
• 
  

  hemanth

  import java.util.*;
  public class max_square_submatrix {
  public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int m=sc.nextInt();
  int[][] a=new int[n][m];
  for(int i=0;i<n;i++)
  {
  for(int j=0;j<m;j++)
  {
  a[i][j]=sc.nextInt();
  }
  }
  int[][] dp=new int[n+1][m+1];
  int largest=0;
  for(int i=0;i<n;i++)
  {
  dp[i][0]=0;
  }
  for(int j=0;j<m;j++)
  {
  dp[0][j]=0;
  }
  for(int i=1;i<=n;i++)
  {
  for(int j=1;jlargest)
  {
  largest=dp[i][j];
  }
  }
  else {
  dp[i][j]=0;
  }
  }
  }
  for(int i=0;i<largest;i++)
  {
  for(int j=0;j<largest;j++)
  {
  System.out.print("1"+" ");
  }
  System.out.println();
  }
  }
  }

  Log in to Reply
• 
  

  Baleegh

  my python code:-

  n=int(input())
  l=[]
  arr=[]
  for i in range(n):
  l.append(list(map(int,input().split())))
  for i in range(n):
  c=0
  for j in range(n):
  if(l[i][j]==1):
  c+=1
  arr.append(c)
  c=min(arr)
  l=[]
  for i in range(n):
  arr=[]
  for j in range(c):
  arr.append(1)
  l.append(arr)
  print(l)

  Log in to Reply