Determining Sandwich type for Palindromic Matrix
Given a 2D matrix, print if it is a Horizontal, Vertical, Proper, or Improper Sandwich. If all rows of the matrix are palindrome, then it can be folded in a vertical sense so it is a Vertical Sandwich Similarly, if all columns are palindrome, then they can be folded in a horizontal sense so it is a Horizontal Sandwich If any one or none of the rows and columns are palindrome, then it is an Improper Sandwich If all are palindrome, then it is a Proper Sandwich.
Examples:
Input: [[1, 2, 1], [2, 2, 2], [3, 4, 3]]
Output: Vertical Sandwich
Explanation: rows are palindrome, hence it is a vertical sandwichInput: [[1, 2, 1], [2, 5, 6], [1, 2, 1]]
Output: Horizontal Sandwich
Explanation: columns are palindrome, hence it is a horizontal sandwichInput: [[1, 2, 1], [2, 2, 2], [1, 2, 1]]
Output: Proper Sandwich
Explanation: Both columns and rows are palindrome, hence it is a proper sandwichInput: [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
Output: Improper Sandwich
Explanation: Both columns and rows are not palindrome, hence it is an improper sandwich
Approach: To solve the problem follow the below idea:
Idea is to see if matrix can be folded in any manner, if all rows are palindrome then it can be folded from middle in vertical direction, hence it makes a vertical sandwich and similarly for other types of sandwich.
Follow the steps to solve the problem:
- The idea is to traverse all rows and columns to check if they are palindrome.
- If any one of the row is not palindrome, then no need to check for other rows as all rows should be palindrome for it to be vertical sandwich.
- Similarly, traverse all columns and check if all are palindrome.
- If all rows and columns are palindrome then it is a proper sandwich or else improper sandwich.
- We can maintain two flags isVerticalSandwich and isHorizontalSandwich and traverse rows and columns, and then based on results, return values based on values of these flags.
- For traversal of each row or coloumn, we can use two pointers , low and high at start and end of row and check if values at these indexes are same and traverse only till mid of row or column.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <iostream> #include <vector> using namespace std; // Function to determine the sandwich type for // a given matrix string determineSandwichType(vector<vector< int > >& matrix) { int n = matrix.size(); bool isVertical = true ; bool isHorizontal = true ; int low, high; // Check for vertical sandwich -> check if // rows are palindrome for ( int row = 0; row < n; row++) { low = 0; high = n - 1; // Check only till mid of row while (low < high) { if (matrix[row][low] != matrix[row][high]) { isVertical = false ; break ; } low++; high--; } // No need to check for all rows if one // comes out as not palindrome if (!isVertical) break ; } // Check for horizontal sandwich -> check if // columns are palindrome for ( int col = 0; col < n; col++) { low = 0; high = n - 1; // Traverse till mid of column while (low < high) { if (matrix[low][col] != matrix[high][col]) { isHorizontal = false ; break ; } low++; high--; } // No need to check for all columns if // one comes out as not palindrome if (!isHorizontal) break ; } // Determine the sandwich type if (isVertical && isHorizontal) { return "Proper Sandwich"; } else if (isVertical) { return "Vertical Sandwich"; } else if (isHorizontal) { return "Horizontal Sandwich"; } else { return "Improper Sandwich"; } } // Drivers code int main() { int n = 3; vector<vector< int > > matrix = { { 1, 2, 1 }, { 2, 2, 2 }, { 1, 2, 1 } }; // Function Call string sandwichType = determineSandwichType(matrix); cout << sandwichType << endl; return 0; } |
Java
public class SandwichType { public static String determineSandwichType( int [][] matrix) { int n = matrix.length; boolean isVertical = true ; boolean isHorizontal = true ; // Check for vertical sandwich -> check if rows are palindrome for ( int row = 0 ; row < n; row++) { int low = 0 ; int high = n - 1 ; // Check only until the middle of the row while (low < high) { if (matrix[row][low] != matrix[row][high]) { isVertical = false ; break ; } low++; high--; } // No need to check for all rows if one is not a palindrome if (!isVertical) { break ; } } // Check for horizontal sandwich -> check if columns are palindrome for ( int col = 0 ; col < n; col++) { int low = 0 ; int high = n - 1 ; // Traverse until the middle of the column while (low < high) { if (matrix[low][col] != matrix[high][col]) { isHorizontal = false ; break ; } low++; high--; } // No need to check for all columns if one is not a palindrome if (!isHorizontal) { break ; } } // Determine the sandwich type if (isVertical && isHorizontal) { return "Proper Sandwich" ; } else if (isVertical) { return "Vertical Sandwich" ; } else if (isHorizontal) { return "Horizontal Sandwich" ; } else { return "Improper Sandwich" ; } } public static void main(String[] args) { int n = 3 ; int [][] matrix = { { 1 , 2 , 1 }, { 2 , 2 , 2 }, { 1 , 2 , 1 } }; // Function call String sandwichType = determineSandwichType(matrix); System.out.println(sandwichType); } } |
Python3
def determine_sandwich_type(matrix): n = len (matrix) is_vertical = True is_horizontal = True low = 0 high = 0 # Check for vertical sandwich -> check if # rows are palindrome for row in range (n): low = 0 high = n - 1 # Check only until the middle of the row while low < high: if matrix[row][low] ! = matrix[row][high]: is_vertical = False break low + = 1 high - = 1 # No need to check for all rows if one # is not a palindrome if not is_vertical: break # Check for horizontal sandwich -> check if # columns are palindrome for col in range (n): low = 0 high = n - 1 # Traverse until the middle of the column while low < high: if matrix[low][col] ! = matrix[high][col]: is_horizontal = False break low + = 1 high - = 1 # No need to check for all columns if one # is not a palindrome if not is_horizontal: break # Determine the sandwich type if is_vertical and is_horizontal: return "Proper Sandwich" elif is_vertical: return "Vertical Sandwich" elif is_horizontal: return "Horizontal Sandwich" else : return "Improper Sandwich" # Driver code n = 3 matrix = [ [ 1 , 2 , 1 ], [ 2 , 2 , 2 ], [ 1 , 2 , 1 ] ] # Function call sandwich_type = determine_sandwich_type(matrix) print (sandwich_type) |
C#
using System; public class GFG { public static string DetermineSandwichType( int [][] matrix) { int n = matrix.Length; bool isVertical = true ; bool isHorizontal = true ; // Check for vertical sandwich -> check if rows are palindrome for ( int row = 0; row < n; row++) { int low = 0; int high = n - 1; // Check only until the middle of the row while (low < high) { if (matrix[row][low] != matrix[row][high]) { isVertical = false ; break ; } low++; high--; } // No need to check for all rows // if one is not a palindrome if (!isVertical) { break ; } } // Check for horizontal sandwich -> check if columns are palindrome for ( int col = 0; col < n; col++) { int low = 0; int high = n - 1; // Traverse until the middle of column while (low < high) { if (matrix[low][col] != matrix[high][col]) { isHorizontal = false ; break ; } low++; high--; } // No need to check for all columns // if one is not a palindrome if (!isHorizontal) { break ; } } // Determine the sandwich type if (isVertical && isHorizontal) { return "Proper Sandwich" ; } else if (isVertical) { return "Vertical Sandwich" ; } else if (isHorizontal) { return "Horizontal Sandwich" ; } else { return "Improper Sandwich" ; } } public static void Main( string [] args) { int n = 3; int [][] matrix = new int [n][]; matrix[0] = new int [] { 1, 2, 1 }; matrix[1] = new int [] { 2, 2, 2 }; matrix[2] = new int [] { 1, 2, 1 }; // Function call string sandwichType = DetermineSandwichType(matrix); Console.WriteLine(sandwichType); } } |
Javascript
function determineSandwichType(matrix) { const n = matrix.length; let isVertical = true ; let isHorizontal = true ; // Check for vertical sandwich -> check if rows are palindrome for (let row = 0; row < n; row++) { let low = 0; let high = n - 1; // Check only until the middle of the row while (low < high) { if (matrix[row][low] !== matrix[row][high]) { isVertical = false ; break ; } low++; high--; } // No need to check for all rows if one is not a palindrome if (!isVertical) { break ; } } // Check for horizontal sandwich -> check if columns are palindrome for (let col = 0; col < n; col++) { let low = 0; let high = n - 1; // Traverse until the middle of the column while (low < high) { if (matrix[low][col] !== matrix[high][col]) { isHorizontal = false ; break ; } low++; high--; } // No need to check for all columns if one is not a palindrome if (!isHorizontal) { break ; } } // Determine the sandwich type if (isVertical && isHorizontal) { return "Proper Sandwich" ; } else if (isVertical) { return "Vertical Sandwich" ; } else if (isHorizontal) { return "Horizontal Sandwich" ; } else { return "Improper Sandwich" ; } } // Driver code const n = 3; const matrix = [ [1, 2, 1], [2, 2, 2], [1, 2, 1] ]; // Function call const sandwichType = determineSandwichType(matrix); console.log(sandwichType); |
Proper Sandwich
Time Complexity: O(N*M), where N is the number of rows and M is number of columns.
Auxillary Space: O(1)
Contact Us