Minimum index at which 1 row and 1 column completely vanishes
Given an array X[] and a matrix M[][]. Then the task is to output the minimum elements needed to remove so that one row and one column of M[][] becomes completely empty, return -1 if not possible. For that, you are allowed to remove the first element of X[] and remove the same element from M[][].
Note: All elements of X[] and M[][] are unique. All the elements of X[] will surely present in M[][], but vice – versa is not true.
Examples:
Input: X[] = {1, 4, 6, 2, 8, 7, 5, 9, 3}, M[][] = {{3, 2, 5}, {1, 4, 6}, {8, 7, 9}}
Output: 6
Explanation:Input: X[] = {1, 4}, M[][] = {{3, 2}, {1, 4}}
Output: -1
Explanation: It can be verified that X[] becomes empty, But any row and any column of matrix didn’t become empty. Therefore, output is -1
Approach: Implement the idea below to solve the problem:
The problem can be solved by using HashMap for storing the position of element in M[][] and Frequency arrays for storing the frequency of vanished element of rows and columns. For more clarifications see the Concept of approach section below.
Concept of approach:
The problem can be solved easily, If we can get the location of an element in matrix efficiently and number of elements vanished in row and column. We can resolve both of this.
- How to get location of elements efficiently: Create a HashMap<Integer, Pair> which stores element and its location in Pair(Row, Col) in form of Key and Value. As it is given that all the elements are unique so no duplicacy will occur and map, Thus it is a perfect data structure to use here. After this we can get location of any element in O(1) time.
- How to get number of elements vanished in row or column: Create two frequency arrays Row[] and Col[], Which stores number of vanished elements in particular row or column. These frequency arrays will reduce time to check that any row or column is vanished or not.
After this just implement the below approach:
- Traverse on Matrix and initialize all elements’ location in map.
- Create two arrays Row[] and Col[].
- Traverse on X[] and get location of current element and increment number of vanished elements in row[] and col[] at same location.
- If any value in Row[] become equal to M[0].length and any value of column[] become equal to M.length.Then return the number of elements traversed in X[].
- Else return -1.
Steps were taken to solve the problem:
- Create a HashMap<Integer, Pair(int, int)> let’s say map for storing an element and its location.
- Run two nested loops for traversing on M[][] and initialize elements and their location in the map.
- Initialize a variable let’s say min_element for storing the minimum number of elements required.
- Create two frequency arrays Row[] and Col[] and two boolean variables Row_max and Col_max, and set them initially as false.
- Run a loop for traversing X[] and follow the below-mentioned steps under the scope of the loop:
- Increment min_element.
- Get the location of the current element of X[]. Let say location of current element in M[][] will be = (r, c)
- Increment Row[r] by 1.
- Increment Col by 1.
- If (Row[r] == M[0].length), Then mark Row_max flag as true.
- If (Col == M.length), then mark the Col_max flag as true.
- If (Row_max == True && Col_max == True), Then return the value of min_element.
- Return -1.
Below is the code to implement the approach:
C++
#include <iostream> #include <unordered_map> #include <utility> using namespace std; // Method to return int Min_Element( int X[], int M[][2], int n, int m) { // HashMap for storing the // position of elements in M[][] unordered_map< int , pair< int , int >> map; // Loops for initializing HashMap for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { map[M[i][j]] = make_pair(i, j); } } // Frequency arrays, Which will // store Number of vanished // elements in partiular Row or // Column of M[][] int row[n] = {0}; int col[m] = {0}; // Variable for storing minimum // number of elements int min_element = 0; // Boolean flags for checking // either one row or column is // completely vanished or not bool row_max = false ; bool col_max = false ; // Loop for traversing over X[] for ( int i = 0; i < 2; i++) { // Increment min_element // It means we are vanishing // on element min_element++; // Get the location(row, col) // of current element = (X[i]) // From HashMap pair< int , int > y = map[X[i]]; // Incrementing number of // vanished elements in both // frequency arrays row[y.first] += 1; col[y.second] += 1; // If any row completely // vanishes then marking // row_max flag as true if (row[y.first] == m) { row_max = true ; } // If any col completely // vanishes then marking // row_col flag as true if (col[y.second] == n) { col_max = true ; } // This block will execute, // When both flags will be // true. Formally, When a // row and a column will // completly become empty if (row_max && col_max) { // Returning the value of // min_element variable return min_element; } } // If no row ans no column become // empty Then returning -1 // as Not Possible return -1; } // Driver Function int main() { // Inputs int X[] = { 1, 4 }; int M[][2] = { { 3, 2 }, { 1, 4 }, }; // Function call and stroing // answer as returned value int ans = Min_Element(X, M, 2, 2); // Ouptut of returned value cout << ans << endl; return 0; } |
Java
// Java code to implement the approach import java.util.*; // Custom pair class class pair { int row, col; pair( int row, int col) { this .row = row; this .col = col; } } public class GFG { // Driver Function public static void main(String[] args) { // Inputs int [] X = { 1 , 4 }; int [][] M = { { 3 , 2 }, { 1 , 4 }, }; // Function call and stroing // answer as returned value int ans = Min_Element(X, M); // Ouptut of returned value System.out.println(ans); } // Method to return static int Min_Element( int [] X, int [][] M) { // HashMap for storing the // position of elements in M[][] HashMap<Integer, pair> map = new HashMap<>(); // Loops for initializing HashMap for ( int i = 0 ; i < M.length; i++) { for ( int j = 0 ; j < M[ 0 ].length; j++) { map.put(M[i][j], new pair(i, j)); } } // Frequency arrays, Which will // store Number of vanished // elements in partiular Row or // Column of M[][] int [] row = new int [M.length]; int [] col = new int [M[ 0 ].length]; // Variable for storing minimum // number of elements int min_element = 0 ; // Boolean flags for checking // either one row or column is // completely vanished or not boolean row_max = false ; boolean col_max = false ; // Loop for traversing over X[] for ( int i = 0 ; i < X.length; i++) { // Increment min_element // It means we are vanishing // on element min_element++; // Get the location(row, col) // of current element = (X[i]) // From HashMap pair y = map.get(X[i]); // Incrementing number of // vanished elements in both // frequency arrays row[y.row] += 1 ; col[y.col] += 1 ; // If any row completely // vanishes then marking // row_max flag as true if (row[y.row] == M[ 0 ].length) { row_max = true ; } // If any col completely // vanishes then marking // row_col flag as true if (col[y.col] == M.length) { col_max = true ; } // This block will execute, // When both flags will be // true. Formally, When a // row and a column will // completly become empty if (row_max && col_max) { // Returning the value of // min_element variable return min_element; } } // If no row ans no column become // empty Then returning -1 // as Not Possible return - 1 ; } } |
Python3
class Pair: def __init__( self , row, col): self .row = row self .col = col def min_element(X, M): # HashMap for storing the position of elements in M[][] map = {} # Loops for initializing HashMap for i in range ( len (M)): for j in range ( len (M[ 0 ])): map [M[i][j]] = Pair(i, j) # Frequency arrays, Which will store the number of vanished # elements in particular Row or Column of M[][] row = [ 0 ] * len (M) col = [ 0 ] * len (M[ 0 ]) # Variable for storing the minimum number of elements min_element = 0 # Boolean flags for checking either one row or column is # completely vanished or not row_max = False col_max = False # Loop for traversing over X[] for i in range ( len (X)): # Increment min_element # It means we are vanishing # one element min_element + = 1 # Get the location (row, col) # of the current element (X[i]) # From HashMap y = map [X[i]] # Incrementing the number of vanished elements in both # frequency arrays row[y.row] + = 1 col[y.col] + = 1 # If any row completely vanishes then marking # row_max flag as true if row[y.row] = = len (M[ 0 ]): row_max = True # If any column completely vanishes then marking # col_max flag as true if col[y.col] = = len (M): col_max = True # This block will execute, # When both flags will be # true. Formally, When a # row and a column will # completely become empty if row_max and col_max: # Returning the value of # min_element variable return min_element # If no row and no column become empty, # then returning -1 as Not Possible return - 1 # Driver Function if __name__ = = "__main__" : # Inputs X = [ 1 , 4 ] M = [ [ 3 , 2 ], [ 1 , 4 ], ] # Function call and storing # answer as the returned value ans = min_element(X, M) # Output of the returned value print (ans) # This code is contributed by shivamgupta310570 |
C#
using System; using System.Collections.Generic; public class Solution { // Method to return private static int MinElement( int [] X, int [,] M, int n, int m) { // Dictionary for storing the // position of elements in M[,] Dictionary< int , Tuple< int , int >> map = new Dictionary< int , Tuple< int , int >>(); // Loops for initializing Dictionary for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { map[M[i, j]] = Tuple.Create(i, j); } } // Frequency arrays, Which will // store Number of vanished // elements in particular Row or // Column of M[,] int [] row = new int [n]; int [] col = new int [m]; // Variable for storing minimum // number of elements int minElement = 0; // Boolean flags for checking // whether one row or column is // completely vanished or not bool rowMax = false ; bool colMax = false ; // Loop for traversing over X[] for ( int i = 0; i < 2; i++) { // Increment minElement // It means we are vanishing // one element minElement++; // Get the location(row, col) // of current element = (X[i]) // From Dictionary Tuple< int , int > y = map[X[i]]; // Incrementing number of // vanished elements in both // frequency arrays row[y.Item1] += 1; col[y.Item2] += 1; // If any row completely // vanishes then marking // rowMax flag as true if (row[y.Item1] == m) { rowMax = true ; } // If any col completely // vanishes then marking // colMax flag as true if (col[y.Item2] == n) { colMax = true ; } // This block will execute, // When both flags will be // true. Formally, When a // row and a column will // completely become empty if (rowMax && colMax) { // Returning the value of // minElement variable return minElement; } } // If no row and no column become // empty then returning -1 // as Not Possible return -1; } // Driver Function public static void Main( string [] args) { // Inputs int [] X = { 1, 4 }; int [,] M = { { 3, 2 }, { 1, 4 } }; // Function call and storing // answer as returned value int ans = MinElement(X, M, 2, 2); // Output of returned value Console.WriteLine(ans); } } |
Javascript
class Pair { constructor(row, col) { this .row = row; this .col = col; } } function minElement(X, M) { const map = new Map(); for (let i = 0; i < M.length; i++) { for (let j = 0; j < M[0].length; j++) { map.set(M[i][j], new Pair(i, j)); } } const row = new Array(M.length).fill(0); const col = new Array(M[0].length).fill(0); let minElementCount = 0; let rowMax = false ; let colMax = false ; for (let i = 0; i < X.length; i++) { minElementCount++; const y = map.get(X[i]); row[y.row]++; col[y.col]++; if (row[y.row] === M[0].length) { rowMax = true ; } if (col[y.col] === M.length) { colMax = true ; } if (rowMax && colMax) { return minElementCount; } } return -1; } // Example Inputs const X = [1, 4]; const M = [ [3, 2], [1, 4] ]; // Calling the function and printing the output const ans = minElement(X, M); console.log(ans); // CONTRIBUTED BY Aditi Tyagi |
-1
Time Complexity: O(M*N), As HashMap is used to store the location of an element in M[][] in the form of Pairs.
Auxiliary Space: O((M + N) + (M*N)), Frequency arrays of size M and N are used to store values. Where M and N are the numbers of rows and columns of M[][] and HashMap of space (N*M) is used.