Given a square matrix arr[][] of size N * N, the task is to check whether each row and column of a matrix contains all the numbers from 1 to N or not.
Examples:
Input: arr[][] = { {1, 2, 3},
{3, 1, 2},
{2, 3, 1} }
Output: true
Explanation: Every row and column contains number 1 to N, i.e 1 to 3Input: arr[][] = { {1, 1, 1},
{1, 2, 3},
{1, 2, 3} }
Output: false
Approach: The task can be solved using a set data structure (set stores unique elements). Iterate over the matrix, store the elements of each row and each column inside a set, and check whether the size of the set is equal to N or not.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check whether each row and// column has all the numbers from 1 to Nint check(vector<vector<int> >& arr){ int N = arr.size(); set<int> row, col; int flag = 1; for (int i = 0; i < N; i++) { row.clear(); col.clear(); for (int j = 0; j < N; j++) { // Inserting the elements // to row set and column set col.insert(arr[j][i]); row.insert(arr[i][j]); } // Checking the size of each // row and column and if it is // equal or not if (col.size() != N || row.size() != N) flag = 0; } return flag;}// Driver Codeint main(){ int N = 3; vector<vector<int> > arr{ { 1, 2, 3 }, { 3, 1, 2 }, { 2, 3, 1 } }; cout << (!check(arr) ? "false" : "true"); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Function to check whether each row and // column has all the numbers from 1 to N static int check(int[][] arr) { int N = arr.length; Set<Integer> row = new HashSet<Integer>(); Set<Integer> col = new HashSet<Integer>(); int flag = 1; for (int i = 0; i < N; i++) { row.clear(); col.clear(); for (int j = 0; j < N; j++) { // Inserting the elements // to row set and column set col.add(arr[j][i]); row.add(arr[i][j]); } // Checking the size of each // row and column and if it is // equal or not if (col.size() != N || row.size() != N) flag = 0; } return flag; } // Driver Code public static void main (String[] args) { int N = 3; int[][] arr = { { 1, 2, 3 }, { 3, 1, 2 }, { 2, 3, 1 } }; if(check(arr) == 1){ System.out.println("true"); } else{ System.out.println("false"); } }}// This code is contributed by hrithikgarg03188. |
Python3
# Python program for the above approach# Function to check whether each row and# column has all the numbers from 1 to Ndef check (arr): N = len(arr) row = set() col = set(); flag = 1; for i in range(N): row = set() col = set(); for j in range(N): # Inserting the elements # to row set and column set col.add(arr[j][i]); row.add(arr[i][j]); # Checking the size of each # row and column and if it is # equal or not if (len(col) != N or len(row) != N): flag = 0; return flag;# Driver CodeN = 3;arr = [[1, 2, 3], [3, 1, 2], [2, 3, 1]];print("false") if not check(arr) else print("true");# This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approachusing System;using System.Collections.Generic; public class GFG{ // Function to check whether each row and // column has all the numbers from 1 to N static int check(int[,] arr) { int N = 3; HashSet<int> row = new HashSet<int>(); HashSet<int> col = new HashSet<int>(); int flag = 1; for (int i = 0; i < N; i++) { row.Clear(); col.Clear(); for (int j = 0; j < N; j++) { // Inserting the elements // to row set and column set col.Add(arr[j,i]); row.Add(arr[i,j]); } // Checking the size of each // row and column and if it is // equal or not if (col.Count != N || row.Count != N) flag = 0; } return flag; } // Driver Code static public void Main (){ //int N = 3; int[,] arr = { { 1, 2, 3 }, { 3, 1, 2 }, { 2, 3, 1 } }; if(check(arr) == 1){ Console.WriteLine("true"); } else{ Console.WriteLine("false"); } }}// This code is contributed by Shubham Singh |
Javascript
<script> // JavaScript program for the above approach // Function to check whether each row and // column has all the numbers from 1 to N const check = (arr) => { let N = arr.length; let row = new Set(), col = new Set(); let flag = 1; for (let i = 0; i < N; i++) { row.clear(); col.clear(); for (let j = 0; j < N; j++) { // Inserting the elements // to row set and column set col.add(arr[j][i]); row.add(arr[i][j]); } // Checking the size of each // row and column and if it is // equal or not if (col.size != N || row.size != N) flag = 0; } return flag; } // Driver Code let N = 3; let arr = [[1, 2, 3], [3, 1, 2], [2, 3, 1]]; (!check(arr) ? document.write("false") : document.write("true"));// This code is contributed by rakeshsahni</script> |
Output
true
Time Complexity: O(N2 * logN)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
