Given a matrix mat of N*N (N is a perfect square|) and two points x and y, the task is to return all the elements of the submatrix in which the element A[x][y] lies.
Note: The matrix is divided into N equal submatrix each of size K*K (where K is the square root of N)
Examples:
Input: N = 9, x = 4, y = 4
mat = {{1, 2, 3, 9, 8, 7, 1, 2, 1}, {4, 5, 6, 1, 2, 3, 7, 9, 8}, {7, 8, 9, 2, 2, 0, 1, 5, 7},
{0, 2, 9, 1, 2, 3, 4, 5, 3}, {9, 8, 7, 4, 5, 6, 7, 4, 1}, {1, 4, 7, 7, 8, 9, 9, 8, 7},
{5, 6, 1, 9, 8, 7, 5, 2, 3}, {4, 5, 1, 6, 5, 4, 9, 7, 4}, {8, 7, 9, 3, 2, 1, 9, 4, 9}},
Output: {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
Explanation: Given x = 4, y = 4 that element lies in the middle grid.Input: N = 9, x = 6, y= 4
mat = {{1, 2, 3, 9, 8, 7, 1, 2, 1}, {4, 5, 6, 1, 2, 3, 7, 9, 8}, {7, 8, 9, 2, 2, 0, 1, 5, 7},
{0, 2, 9, 1, 2, 3, 4, 5, 3}, {9, 8, 7, 4, 5, 6, 7, 4, 1}, {1, 4, 7, 7, 8, 9, 9, 8, 7},
{5, 6, 1, 9, 8, 7, 5, 2, 3}, {4, 5, 1, 6, 5, 4, 9, 7, 4}, {8, 7, 9, 3, 2, 1, 9, 4, 9}}
Output: {{9, 8, 7}, {6, 5, 4}, {3, 2, 1}}
Explanation: Given x =6, y = 4 that element lies in the grid shown below.
Approach: The problem can be solved based on the following observation:
An element at index (x, y) in a square matrix of perfect square length, lies in submatrix[n*(x/n), (n*(y/n)], where each value shows the positioning with respect to other submatrices. So the idea is to just print that submatrix.
Follow the steps mentioned below to implement the idea:
- Find square root on N.
- Store the submatrix where the coordinate (x, y) lies in a new matrix.
- Return the new array.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to print submatrix vector<vector< int > > getSubGrid( int N, vector<vector< int > >& matrix, int x, int y) { int n = sqrt (N); vector<vector< int > > subGrid(n, vector< int >(n)); for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { subGrid[i][j] = matrix[n * (x / n) + (j / n) + i] [n * (y / n) + j % n]; } } // Return the submatrix return subGrid; } // Driver Code int main() { int N = 9; vector<vector< int > > matrix = { { 1, 2, 3, 9, 8, 7, 1, 2, 1 }, { 4, 5, 6, 1, 2, 3, 7, 9, 8 }, { 7, 8, 9, 2, 2, 0, 1, 5, 7 }, { 0, 2, 9, 1, 2, 3, 4, 5, 3 }, { 9, 8, 7, 4, 5, 6, 7, 4, 1 }, { 1, 4, 7, 7, 8, 9, 9, 8, 7 }, { 5, 6, 1, 9, 8, 7, 5, 2, 3 }, { 4, 5, 1, 6, 5, 4, 9, 7, 4 }, { 8, 7, 9, 3, 2, 1, 9, 4, 9 } }; int x = 4; int y = 4; // Function call vector<vector< int > > subGrid = getSubGrid(N, matrix, x, y); for ( int i = 0; i < subGrid.size(); i++) { cout << "[" ; int j = 0; for (; j < subGrid.size() - 1; j++) { cout << subGrid[i][j] << ", " ; } cout << subGrid[i][j] << "] " ; } return 0; } // This code is contributed by Rohit Pradhan |
Java
// Java code to implement the approach import java.io.*; import java.util.*; class GFG { // Function to print submatrix static int [][] getSubGrid( int N, int [][] matrix, int x, int y) { int n = ( int )Math.sqrt(N); int subGrid[][] = new int [n][n]; for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < n; j++) { subGrid[i][j] = matrix[n * (x / n) + (j / n) + i] [n * (y / n) + j % n]; } } // Return the submatrix return subGrid; } // Driver code public static void main(String[] args) { int N = 9 ; int matrix[][] = { { 1 , 2 , 3 , 9 , 8 , 7 , 1 , 2 , 1 }, { 4 , 5 , 6 , 1 , 2 , 3 , 7 , 9 , 8 }, { 7 , 8 , 9 , 2 , 2 , 0 , 1 , 5 , 7 }, { 0 , 2 , 9 , 1 , 2 , 3 , 4 , 5 , 3 }, { 9 , 8 , 7 , 4 , 5 , 6 , 7 , 4 , 1 }, { 1 , 4 , 7 , 7 , 8 , 9 , 9 , 8 , 7 }, { 5 , 6 , 1 , 9 , 8 , 7 , 5 , 2 , 3 }, { 4 , 5 , 1 , 6 , 5 , 4 , 9 , 7 , 4 }, { 8 , 7 , 9 , 3 , 2 , 1 , 9 , 4 , 9 } }; int x = 4 ; int y = 4 ; // Function call int subGrid[][] = getSubGrid(N, matrix, x, y); System.out.println(Arrays.deepToString(subGrid)); } } |
Python3
# python3 code to implement the approach import math # Function to print submatrix def getSubGrid(N, matrix, x, y): n = int (math.sqrt(N)) subGrid = [[ 0 for _ in range (n)] for _ in range (n)] for i in range ( 0 , n): for j in range ( 0 , n): subGrid[i][j] = matrix[n * (x / / n) + (j / / n) + i][n * (y / / n) + j % n] # Return the submatrix return subGrid # Driver Code if __name__ = = "__main__" : N = 9 matrix = [[ 1 , 2 , 3 , 9 , 8 , 7 , 1 , 2 , 1 ], [ 4 , 5 , 6 , 1 , 2 , 3 , 7 , 9 , 8 ], [ 7 , 8 , 9 , 2 , 2 , 0 , 1 , 5 , 7 ], [ 0 , 2 , 9 , 1 , 2 , 3 , 4 , 5 , 3 ], [ 9 , 8 , 7 , 4 , 5 , 6 , 7 , 4 , 1 ], [ 1 , 4 , 7 , 7 , 8 , 9 , 9 , 8 , 7 ], [ 5 , 6 , 1 , 9 , 8 , 7 , 5 , 2 , 3 ], [ 4 , 5 , 1 , 6 , 5 , 4 , 9 , 7 , 4 ], [ 8 , 7 , 9 , 3 , 2 , 1 , 9 , 4 , 9 ]] x = 4 y = 4 # Function call subGrid = getSubGrid(N, matrix, x, y) for i in range ( 0 , len (subGrid)): print ( "[" , end = "") j = 0 while (j < len (subGrid) - 1 ): print (subGrid[i][j], end = ", " ) j + = 1 print (subGrid[i][j], end = "] " ) # This code is contributed by rakeshsahni |
C#
// C# code to implement the approach using System; class GFG { // Function to print submatrix static int [,] getSubGrid( int N, int [,] matrix, int x, int y) { int n = ( int )Math.Sqrt(N); int [,]subGrid = new int [n,n]; for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { subGrid[i,j] = matrix[n * (x / n) + (j / n) + i,n * (y / n) + j % n]; } } // Return the submatrix return subGrid; } // Driver code public static void Main( string [] args) { int N = 9; int [,]matrix = { { 1, 2, 3, 9, 8, 7, 1, 2, 1 }, { 4, 5, 6, 1, 2, 3, 7, 9, 8 }, { 7, 8, 9, 2, 2, 0, 1, 5, 7 }, { 0, 2, 9, 1, 2, 3, 4, 5, 3 }, { 9, 8, 7, 4, 5, 6, 7, 4, 1 }, { 1, 4, 7, 7, 8, 9, 9, 8, 7 }, { 5, 6, 1, 9, 8, 7, 5, 2, 3 }, { 4, 5, 1, 6, 5, 4, 9, 7, 4 }, { 8, 7, 9, 3, 2, 1, 9, 4, 9 } }; int x = 4; int y = 4; // Function call int [,]subGrid = getSubGrid(N, matrix, x, y); Console.Write( "[" ) ; for ( int i = 0; i< subGrid.GetLength(0); i++){ Console.Write( "[" ) ; for ( int j = 0; j < subGrid.GetLength(1) ; j++) Console.Write(subGrid[i,j] + " ," ); Console.Write( "] " ); } Console.Write( "]" ) ; } } // This code is contributed by AnkThon |
Javascript
<script> // javascript code to implement the approach // Function to print submatrix function getSubGrid(N, matrix, x , y) { var n = parseInt(Math.sqrt(N)); var subGrid = Array(n).fill(0).map(x => Array(n).fill(0)); for ( var i = 0; i < n; i++) { for ( var j = 0; j < n; j++) { subGrid[i][j] = matrix[n * parseInt(x / n) + parseInt(j / n) + i] [n * parseInt(y / n) + j % n]; } } // Return the submatrix return subGrid; } // Driver code var N = 9; var matrix = [ [ 1, 2, 3, 9, 8, 7, 1, 2, 1 ], [ 4, 5, 6, 1, 2, 3, 7, 9, 8 ], [ 7, 8, 9, 2, 2, 0, 1, 5, 7 ], [ 0, 2, 9, 1, 2, 3, 4, 5, 3 ], [ 9, 8, 7, 4, 5, 6, 7, 4, 1 ], [ 1, 4, 7, 7, 8, 9, 9, 8, 7 ], [ 5, 6, 1, 9, 8, 7, 5, 2, 3 ], [ 4, 5, 1, 6, 5, 4, 9, 7, 4 ], [ 8, 7, 9, 3, 2, 1, 9, 4, 9 ] ]; var x = 4; var y = 4; // Function call var subGrid = getSubGrid(N, matrix, x, y); document.write( "[" ); for (let i = 0; i < subGrid.length; i++) { document.write( "[" ); for (let j = 0; j < subGrid[i].length; j++) { document.write(subGrid[i][j]+ ", " ); } document.write( "]" ); } document.write( "]" ); // This code contributed by shikhasingrajput </script> |
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Time Complexity: O(N)
Auxiliary Space: O(1)