Given an N x M matrix mat[][] where all elements are natural numbers starting from 1 and are continuous except 1 element, find that element.
Examples:
Input: mat[][] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 11, 12, 13}}
N = 3, M = 4
Output: 10
Explanation: Missing number is 10 at row no 3.Input: mat[][] = {{1, 2, 3},
{5, 6, 7},
{8, 9, 10}}
N = 3, M = 3
Output: 4
Naive Approach:
The naive approach to solve the problem is to push entire matrix elements to vector and sort the vector in ascending order. Now loop from 1 to M*N and check if it exists in the vector or not. Use binary search to find out their existence. If an integer does not exist, then that that is the answer.
Algorithm:
1. Create a function to find the missing element in matrix, that takes matrix (2D array) and its dimensions (N and M) as input.
2. Create a vector v to store all elements of matrix.
3. Traverse the matrix in row-major order and push each element to vector v.
4. Sort the vector v in ascending order.
5. Loop through all elements from 1 to N*M:
a. Find the position of current element i in the vector v using binary search.
b. If the position of i is equal to the size of vector v or the element at that position is not i:
i. Then i is the missing element, so return i.
Below is the implementation of the approach:
C++
// C++ code for the approach#include <bits/stdc++.h> using namespace std;#define Max 1000// function to find the missing element in matrixint findMissing(int mat[][Max], int N, int M) { // create a vector to store matrix elements vector<int> v; for(int i=0; i<N; i++) { for(int j=0; j<M; j++) { // push element to vector v.push_back(mat[i][j]); } } // sort the vector in ascending order sort(v.begin(), v.end()); // loop through all elements from 1 to N*M for(int i=1; i<=N*M; i++) { // find the position of i in vector using binary search int pos = lower_bound(v.begin(), v.end(), i) - v.begin(); // check if i does not exist in vector if(pos == v.size() || v[pos] != i) { // return the missing element return i; } }}// Driver's codeint main() { int N = 3; int M = 4; int Mat[][Max] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 11, 12, 13 } }; // Function call int missing = findMissing(Mat, N, M); // print the missing element cout << missing << endl; return 0;} |
Java
import java.util.Arrays;import java.util.Vector;class MissingElementInMatrix { static final int Max = 1000; // Function to find the missing element in the matrix static int findMissing(int[][] mat, int N, int M) { // Create a vector to store matrix elements Vector<Integer> v = new Vector<Integer>(); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { // Push the element to the vector v.add(mat[i][j]); } } // Sort the vector in ascending order Arrays.sort(v.toArray()); // Loop through all elements from 1 to N*M for (int i = 1; i <= N * M; i++) { // Find the position of i in the vector using binary search int pos = Arrays.binarySearch(v.toArray(), i); // Check if i does not exist in the vector if (pos < 0) { // Return the missing element return i; } } return -1; // No missing element found } // Driver's code public static void main(String[] args) { int N = 3; int M = 4; int[][] Mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 11, 12, 13 } }; // Function call int missing = findMissing(Mat, N, M); // Print the missing element System.out.println(missing); }} |
Python3
def find_missing(matrix, N, M): # Create a list to store matrix elements v = [] for i in range(N): for j in range(M): # Append element to the list v.append(matrix[i][j]) # Sort the list in ascending order v.sort() # Loop through all elements from 1 to N*M for i in range(1, N*M + 1): # Find the position of i in the list using binary search pos = v.index(i) if i in v else len(v) # Check if i does not exist in the list if pos == len(v) or v[pos] != i: # Return the missing element return i# Driver's codeif __name__ == "__main__": N = 3 M = 4 Mat = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 11, 12, 13]] # Function call missing = find_missing(Mat, N, M) # Print the missing element print(missing) |
C#
using System;using System.Collections.Generic;namespace Geek{ class GFG { // function to find the // missing element in matrix static int FindMissing(int[][] mat, int N, int M) { // create a list to store matrix elements List<int> v = new List<int>(); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { // push element to list v.Add(mat[i][j]); } } // sort the list in ascending order v.Sort(); // loop through all elements from 1 to N*M for (int i = 1; i <= N * M; i++) { // find the position of i in // list using binary search int pos = v.BinarySearch(i); // check if i does not exist in list if (pos < 0) { // return the missing element return i; } } // If no missing element is found // return -1 or any appropriate value return -1; } // Driver's code static void Main(string[] args) { int N = 3; int M = 4; int[][] Mat = new int[][] { new int[] { 1, 2, 3, 4 }, new int[] { 5, 6, 7, 8 }, new int[] { 9, 11, 12, 13 } }; // Function call int missing = FindMissing(Mat, N, M); // print the missing element Console.WriteLine(missing); // Pause console before exit (optional) Console.ReadLine(); } }} |
Javascript
// Function to find the missing element in a matrixfunction findMissing(mat, N, M) { // Create an array to store matrix elements const arr = []; // Traverse the matrix and push elements to the array for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { arr.push(mat[i][j]); } } // Sort the array in ascending order arr.sort((a, b) => a - b); // Loop through all elements from 1 to N*M for (let i = 1; i <= N * M; i++) { // Find the position of i in the array using binary search const pos = arr.findIndex((element) => element >= i); // Check if i does not exist in the array if (pos === -1 || arr[pos] !== i) { // Return the missing element return i; } }}// Driver codefunction main() { const N = 3; const M = 4; const Mat = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 11, 12, 13] ]; // Function call const missing = findMissing(Mat, N, M); // Print the missing element console.log(missing);}main(); |
Output
10
Time Complexity: O( (N*M)*log(N*M) ) because sort function has been called. Also searching each element from 1 to N*M using lower_bound takes O( (N*M)*log(N*M) ) time. So overall complexity is O( (N*M)*log(N*M) ). Here, N and M are rows and columns respectively.
Space Complexity: O( (N*M) ) as vector v has been created which takes O( (N*M) ) space. Here, N and M are rows and columns respectively.
Approach: The problem can be solved by checking multiples of M at the last element of each row of the matrix, if it does not match then the missing element is in that row. Apply linear search and find it.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;#define Max 1000// Function to return Missing// Element from matrix Matint check(int Mat[][Max], int N, int M){ // Edge Case if (Mat[0][0] != 1) return 1; // Initialize last element of // first row int X = Mat[0][0] + M - 1; for (int i = 0; i < N; i++) { // If last element of respective row // matches respective multiples of X if (Mat[i][M - 1] == X) X = X + M; // Else missing element // is in that row else { // Initializing first element // of the row int Y = X - M + 1; // Initializing column index int j = 0; // Linear Search while (Y <= X) { if (Mat[i][j] == Y) { Y++; j++; } else return Y; } } }}// Driver Codeint main(){ int N = 3; int M = 4; int Mat[][Max] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 11, 12, 13 } }; cout << check(Mat, N, M); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to return Missing// Element from matrix Matstatic int check(int Mat[][], int N, int M){ // Edge Case if (Mat[0][0] != 1) return 1; // Initialize last element of // first row int X = Mat[0][0] + M - 1; for (int i = 0; i < N; i++) { // If last element of respective row // matches respective multiples of X if (Mat[i][M - 1] == X) X = X + M; // Else missing element // is in that row else { // Initializing first element // of the row int Y = X - M + 1; // Initializing column index int j = 0; // Linear Search while (Y <= X) { if (Mat[i][j] == Y) { Y++; j++; } else return Y; } } } return 0;}// Driver Codepublic static void main(String[] args){ int N = 3; int M = 4; int Mat[][] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 11, 12, 13 } }; System.out.print(check(Mat, N, M));}}// This code is contributed by Rajput-Ji |
Python3
# Python 3 program for the above approach # Function to return Missing# Element from matrix Matdef check(Mat, N, M): # Edge Case if (Mat[0][0] != 1): return 1 # Initialize last element of # first row X = Mat[0][0] + M - 1; for i in range(N): # If last element of respective row # matches respective multiples of X if (Mat[i][M - 1] == X): X = X + M # Else missing element # is in that row else: # Initializing first element # of the row Y = X - M + 1 # Initializing column index j = 0; # Linear Search while (Y <= X): if (Mat[i][j] == Y): Y = Y + 1 j = j + 1 else: return Y# Driver Codeif __name__ == "__main__": N, M = 3, 4 Mat = [[ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 11, 12, 13]] ans = check(Mat, N, M) print(ans)# This code is contributed by Abhishek Thakur. |
C#
// C# program for the above approachusing System;class GFG { // Function to return Missing // Element from matrix Mat static int check(int [,] Mat, int N, int M) { // Edge Case if (Mat[0, 0] != 1) return 1; // Initialize last element of // first row int X = Mat[0, 0] + M - 1; for (int i = 0; i < N; i++) { // If last element of respective row // matches respective multiples of X if (Mat[i, M - 1] == X) X = X + M; // Else missing element // is in that row else { // Initializing first element // of the row int Y = X - M + 1; // Initializing column index int j = 0; // Linear Search while (Y <= X) { if (Mat[i, j] == Y) { Y++; j++; } else return Y; } } } return 0; } // Driver Code public static void Main() { int N = 3; int M = 4; int[, ] Mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 11, 12, 13 } }; Console.Write(check(Mat, N, M)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach let Max = 1000 // Function to return Missing // Element from matrix Mat function check(Mat, N, M) { // Edge Case if (Mat[0][0] != 1) return 1; // Initialize last element of // first row let X = Mat[0][0] + M - 1; for (let i = 0; i < N; i++) { // If last element of respective row // matches respective multiples of X if (Mat[i][M - 1] == X) X = X + M; // Else missing element // is in that row else { // Initializing first element // of the row let Y = X - M + 1; // Initializing column index let j = 0; // Linear Search while (Y <= X) { if (Mat[i][j] == Y) { Y++; j++; } else return Y; } } } } // Driver Code let N = 3; let M = 4; let Mat = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 11, 12, 13]]; document.write(check(Mat, N, M)); // This code is contributed by Potta Lokesh </script> |
Output
10
Time Complexity: O(N + M)
Auxiliary Space: O(1)
Efficient Approach: The efficient approach is to check multiples of the last element in rows using a binary search algorithm. If it does not match then the missing element is in that row or its previous rows and if it matches then the missing element is in the next rows. First, find that row using binary search then apply binary search in that row in the same way to find the column.
Below is the implementation of the above approach:
C++
// C++ program to implement the above approach#include <bits/stdc++.h>using namespace std;#define Max 1000// Function to return Missing// Element from matrix MAtint check(int Mat[][Max], int N, int M){ // Edge Case if (Mat[0][0] != 1) return 1; // Initialize last element of // first row int X = Mat[0][0] + M - 1; int m, l = 0, h = N - 1; // Checking for row while (l < h) { // Avoiding overflow m = l + (h - l) / 2; if (Mat[m][M - 1] == X * (m + 1)) l = m + 1; else h = m; } // Set the required row index and // last element of previous row int R = h; X = X * h; l = 0, h = M - 1; // Checking for column while (l < h) { // Avoiding overflow m = l + (h - l) / 2; if (Mat[R][m] == X + (m + 1)) l = m + 1; else h = m; } // Returning Missing Element return X + h + 1;}// Driver Codeint main(){ int N = 3; int M = 4; int Mat[][Max] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 11, 12, 13 } }; cout << check(Mat, N, M); return 0;} |
Java
// Java program to implement the above approachimport java.util.*;class GFG{ // Function to return Missing // Element from matrix MAt static int check(int Mat[][], int N, int M) { // Edge Case if (Mat[0][0] != 1) return 1; // Initialize last element of // first row int X = Mat[0][0] + M - 1; int m, l = 0, h = N - 1; // Checking for row while (l < h) { // Avoiding overflow m = l + (h - l) / 2; if (Mat[m][M - 1] == X * (m + 1)) l = m + 1; else h = m; } // Set the required row index and // last element of previous row int R = h; X = X * h; l = 0; h = M - 1; // Checking for column while (l < h) { // Avoiding overflow m = l + (h - l) / 2; if (Mat[R][m] == X + (m + 1)) l = m + 1; else h = m; } // Returning Missing Element return X + h + 1; } // Driver Code public static void main(String[] args) { int N = 3; int M = 4; int Mat[][] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 11, 12, 13 } }; System.out.print(check(Mat, N, M)); }}// This code is contributed by Rajput-Ji |
Python3
# Python program to implement the above approach# Function to return Missing# Element from matrix MAtdef check(Mat, N, M): # Edge Case if (Mat[0][0] != 1): return 1; # Initialize last element of # first row X = Mat[0][0] + M - 1; m = 0; l = 0 h = N - 1; # Checking for row while (l < h): # Avoiding overflow m = l + (h - l) // 2; if (Mat[m][M - 1] == X * (m + 1)): l = m + 1; else: h = m; # Set the required row index and # last element of previous row R = h; X = X * h; l = 0; h = M - 1; # Checking for column while (l < h): # Avoiding overflow m = l + (h - l) // 2; if (Mat[R][m] == X + (m + 1)): l = m + 1; else: h = m; # Returning Missing Element return X + h + 1;# Driver Codeif __name__ == '__main__': N = 3; M = 4; Mat = [[ 1, 2, 3, 4 ],[ 5, 6, 7, 8 ],[ 9, 11, 12, 13 ]] ; print(check(Mat, N, M));# This code is contributed by Rajput-Ji |
C#
// C# program to implement the above approachusing System;public class GFG{ // Function to return Missing // Element from matrix MAt static int check(int [,]Mat, int N, int M) { // Edge Case if (Mat[0,0] != 1) return 1; // Initialize last element of // first row int X = Mat[0,0] + M - 1; int m, l = 0, h = N - 1; // Checking for row while (l < h) { // Avoiding overflow m = l + (h - l) / 2; if (Mat[m,M - 1] == X * (m + 1)) l = m + 1; else h = m; } // Set the required row index and // last element of previous row int R = h; X = X * h; l = 0; h = M - 1; // Checking for column while (l < h) { // Avoiding overflow m = l + (h - l) / 2; if (Mat[R,m] == X + (m + 1)) l = m + 1; else h = m; } // Returning Missing Element return X + h + 1; } // Driver Code public static void Main(String[] args) { int N = 3; int M = 4; int [,]Mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 11, 12, 13 } }; Console.Write(check(Mat, N, M)); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// javascript program to implement the above approach // Function to return Missing // Element from matrix MAt function check(Mat , N , M) { // Edge Case if (Mat[0][0] != 1) return 1; // Initialize last element of // first row var X = Mat[0][0] + M - 1; var m, l = 0, h = N - 1; // Checking for row while (l < h) { // Afunctioning overflow m = l + parseInt((h - l) / 2); if (Mat[m][M - 1] == X * (m + 1)) l = m + 1; else h = m; } // Set the required row index and // last element of previous row var R = h; X = X * h; l = 0; h = M - 1; // Checking for column while (l < h) { // Afunctioning overflow m = l + parseInt((h - l) / 2); if (Mat[R][m] == X + (m + 1)) l = m + 1; else h = m; } // Returning Missing Element return X + h + 1; } // Driver Code var N = 3; var M = 4; var Mat = [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 11, 12, 13 ] ]; document.write(check(Mat, N, M));// This code is contributed by Rajput-Ji</script> |
Output
10
Time Complexity: O(log N + log M)
Auxiliary Space: O(1)
