Given a matrix arr[][] of size M*N containing only positive integers, the task is to check if every row contains all the integers from 1 to N.
Examples:
Input: arr[][] = {{1, 4, 2, 3}, {2, 3, 4, 1}, {3, 4, 2, 1}}
Output: Yes
Explanation: Every row contains all the numbers from 1 to 4Input: arr[][] = {{1, 2}, {2, 3}}
Output: No
Naive Approach: The simplest approach is to sort each row of the matrix and then check each row if it contains all elements from 1 to N or not.
Time Complexity: O(M * N * logN)
Auxiliary Space: O(M * N)
Efficient approach: This problem can be solved using the approach of Find the smallest positive number missing from an unsorted array. The idea is to use the given matrix to use as a structure to mark the numbers that we found. So, if a number between 1 to N is found, mark the index corresponding to that number by inverting the element present at that index.
For example if 2 is found on row 1, change arr[1][2] to arr[1][2] = -arr[1][2]
After applying this operation on all elements in the matrix, the matrix should contain all negatives otherwise all rows do not contain numbers from 1 to N.
Below is the implementation of the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if every row contains // all the integers from 1 to N bool checkMat(vector<vector<int> >& arr) { int N = arr.size(); int M = arr[0].size(); for (auto& x : arr) { for (auto& y : x) { if (abs(y) >= 1 and abs(y) <= M) { x[abs(y) - 1] = -x[abs(y) - 1]; } } } // Check if the matrix contains // all negatives or not for (auto x : arr) { for (auto y : x) { if (y > 0) { return 0; } } } return true; } // Driver Code int main() { vector<vector<int> > arr = { { 1, 4, 2, 3 }, { 2, 3, 4, 1 }, { 3, 4, 2, 1 } }; if (checkMat(arr)) { cout << "Yes"; } else { cout << "No"; } return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to check if every row contains // all the integers from 1 to N static Boolean checkMat(int[][] arr) { int N = arr.length; int M = arr[0].length; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (Math.abs(arr[i][j]) >= 1 && Math.abs(arr[i][j]) <= M) { arr[i][(Math.abs(arr[i][j]) - 1)] = -arr[i][(Math.abs(arr[i][j]) - 1)]; } } } // Check if the matrix contains // all negatives or not for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (arr[i][j] > 0) { return false; } } } return true; } // Driver Code public static void main (String[] args) { int[][] arr = { { 1, 4, 2, 3 }, { 2, 3, 4, 1 }, { 3, 4, 2, 1 } }; if (checkMat(arr)) { System.out.print("Yes"); } else { System.out.print("No"); } } } // This code is contributed by hrithikgarg03188. |
Python3
# Python code for the above approach # Function to check if every row contains # all the integers from 1 to N def checkMat(arr): N = len(arr) M = len(arr[0]) for x in arr: for y in x: if (abs(y) >= 1 and abs(y) <= M): x[abs(y) - 1] = -x[abs(y) - 1] # Check if the matrix contains # all negatives or not for x in arr: for y in x: if (y > 0): return 0 return True # Driver Code arr = [[1, 4, 2, 3], [2, 3, 4, 1], [3, 4, 2, 1]] if (checkMat(arr)): print("Yes") else: print("No") # This code is contributed by Saurabh Jaiswal |
C#
// C# code to implement the above approach using System; class GFG { // Function to check if every row contains // all the integers from 1 to N static Boolean checkMat(int[,] arr) { int N = arr.GetLength(0); int M = arr.GetLength(1); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (Math.Abs(arr[i, j]) >= 1 && Math.Abs(arr[i, j]) <= M) { arr[i, Math.Abs(arr[i, j]) - 1] = -arr[i, Math.Abs(arr[i, j]) - 1]; } } } // Check if the matrix contains // all negatives or not for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (arr[i, j] > 0) { return false; } } } return true; } // Driver Code public static void Main () { int[,] arr = { { 1, 4, 2, 3 }, { 2, 3, 4, 1 }, { 3, 4, 2, 1 } }; if (checkMat(arr)) { Console.Write("Yes"); } else { Console.Write("No"); } } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to check if every row contains // all the integers from 1 to N function checkMat(arr) { let N = arr.length; let M = arr[0].length; for (let x of arr) { for (let y of x) { if (Math.abs(y) >= 1 && Math.abs(y) <= M) { x[(Math.abs(y) - 1)] = -x[(Math.abs(y) - 1)]; } } } // Check if the matrix contains // all negatives or not for (let x of arr) { for (let y of x) { if (y > 0) { return 0; } } } return true; } // Driver Code let arr = [[1, 4, 2, 3], [2, 3, 4, 1], [3, 4, 2, 1]]; if (checkMat(arr)) { document.write("Yes"); } else { document.write("No"); } // This code is contributed by Potta Lokesh </script> |
Yes
Time Complexity: O(M * N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
