Given a binary matrix whose elements are only 0 and 1, we need to print the rows which are duplicates of rows that are already present in the matrix.
Examples:
Input : {1, 1, 0, 1, 0, 1},
{0, 0, 1, 0, 0, 1},
{1, 0, 1, 1, 0, 0},
{1, 1, 0, 1, 0, 1},
{0, 0, 1, 0, 0, 1},
{0, 0, 1, 0, 0, 1}.
Output :
There is a duplicate row at position: 4
There is a duplicate row at position: 5
There is a duplicate row at position: 6
This problem is mainly an extension of find unique rows in a binary matrix.
A Simple Solution is to traverse all rows one by one. For every row, check if it is present anywhere else. If yes print the row.
C++
// C++ code for above approach#include <iostream>#include <vector>using namespace std;// Function to find duplicate rowsvoid duplicate_rows(vector<vector<int>> matrix,int rows,int columns){ // loop through all rows for (int i = 0; i < rows; i++) { // flag to check if current row is // repeated or not bool found = false; // loop through all rows before // the current row for (int j = 0; j < i; j++) { int k = 0; // loop through all elements of current // row and compare with previous row for (k = 0; k < columns; k++) { if (matrix[i][k] != matrix[j][k]) break; } // if all elements are same, mark // the current row as repeated if (k == columns) { found = true; break; } } // if the current row is repeated // print the row position if (found) { cout << "There is a duplicate row at position: "<<i+1; cout << endl; } }}// Driver codeint main() {vector<vector<int>> matrix = {{1, 1, 0, 1, 0, 1}, {0, 0, 1, 0, 0, 1}, {1, 0, 1, 1, 0, 0}, {1, 1, 0, 1, 0, 1}, {0, 0, 1, 0, 0, 1}, {0, 0, 1, 0, 0, 1}};int rows = matrix.size();int columns = matrix[0].size();duplicate_rows(matrix,rows,columns);return 0;}// This code is contributed by Aman Kumar. |
Python3
# Python code for above approachdef duplicate_rows(matrix, rows, columns): # loop through all rows for i in range(rows): # flag to check if current row is repeated or not found = False # loop through all rows before the current row for j in range(i): k = 0 # loop through all elements of current row # and compare with previous row while k < columns: if matrix[i][k] != matrix[j][k]: break k += 1 # if all elements are same, mark the current row as repeated if k == columns: found = True break # if the current row is repeated, print the row position if found: print("There is a duplicate row at position:", i+1)# Driver codematrix = [[1, 1, 0, 1, 0, 1], [0, 0, 1, 0, 0, 1], [1, 0, 1, 1, 0, 0], [1, 1, 0, 1, 0, 1], [0, 0, 1, 0, 0, 1], [0, 0, 1, 0, 0, 1]]rows = len(matrix)columns = len(matrix[0])duplicate_rows(matrix, rows, columns)# This code is contributed by sdeaditysharma |
Javascript
// JavaScript code for above approachfunction duplicate_rows(matrix, rows, columns) { // loop through all rowsfor (let i = 0; i < rows; i++) { // flag to check if current row is repeated or not let found = false; // loop through all rows before the current row for (let j = 0; j < i; j++) { let k = 0; // loop through all elements of current row // and compare with previous row while (k < columns) { if (matrix[i][k] !== matrix[j][k]) { break; } k++; } // if all elements are same, mark the current row as repeated if (k === columns) { found = true; break; } } // if the current row is repeated, print the row position if (found) { console.log(`There is a duplicate row at position: ${i+1}`); }}}// Driver codeconst matrix = [[1, 1, 0, 1, 0, 1],[0, 0, 1, 0, 0, 1],[1, 0, 1, 1, 0, 0],[1, 1, 0, 1, 0, 1],[0, 0, 1, 0, 0, 1],[0, 0, 1, 0, 0, 1]];const rows = matrix.length;const columns = matrix[0].length;duplicate_rows(matrix, rows, columns); |
Java
import java.util.ArrayList;public class Main { // Function to find duplicate rows public static void duplicateRows(ArrayList<ArrayList<Integer> > matrix, int rows, int columns) { // loop through all rows for (int i = 0; i < rows; i++) { // flag to check if current row is repeated or // not boolean found = false; // loop through all rows before the current row for (int j = 0; j < i; j++) { int k = 0; // loop through all elements of current row // and compare with previous row for (k = 0; k < columns; k++) { if (matrix.get(i).get(k) != matrix.get(j).get(k)) break; } // if all elements are same, mark the // current row as repeated if (k == columns) { found = true; break; } } // if the current row is repeated, print the row // position if (found) { System.out.println( "There is a duplicate row at position: " + (i + 1)); } } } // Driver code public static void main(String[] args) { ArrayList<ArrayList<Integer> > matrix = new ArrayList<ArrayList<Integer> >(); matrix.add(new ArrayList<Integer>() { { add(1); add(1); add(0); add(1); add(0); add(1); } }); matrix.add(new ArrayList<Integer>() { { add(0); add(0); add(1); add(0); add(0); add(1); } }); matrix.add(new ArrayList<Integer>() { { add(1); add(0); add(1); add(1); add(0); add(0); } }); matrix.add(new ArrayList<Integer>() { { add(1); add(1); add(0); add(1); add(0); add(1); } }); matrix.add(new ArrayList<Integer>() { { add(0); add(0); add(1); add(0); add(0); add(1); } }); matrix.add(new ArrayList<Integer>() { { add(0); add(0); add(1); add(0); add(0); add(1); } }); int rows = matrix.size(); int columns = matrix.get(0).size(); duplicateRows(matrix, rows, columns); }} |
C#
// C# code for above approachusing System;using System.Collections.Generic;public class Program { // Function to find duplicate rows public static void DuplicateRows(List<List<int> > matrix, int rows, int columns) { // loop through all rows for (int i = 0; i < rows; i++) { // flag to check if current row is // repeated or not bool found = false; // loop through all rows before // the current row for (int j = 0; j < i; j++) { int k = 0; // loop through all elements of current // row and compare with previous row for (k = 0; k < columns; k++) { if (matrix[i][k] != matrix[j][k]) break; } // if all elements are same, mark // the current row as repeated if (k == columns) { found = true; break; } } // if the current row is repeated // print the row position if (found) { Console.WriteLine( "There is a duplicate row at position: " + (i + 1)); } } } // Driver code public static void Main() { List<List<int> > matrix = new List<List<int> >{ new List<int>{ 1, 1, 0, 1, 0, 1 }, new List<int>{ 0, 0, 1, 0, 0, 1 }, new List<int>{ 1, 0, 1, 1, 0, 0 }, new List<int>{ 1, 1, 0, 1, 0, 1 }, new List<int>{ 0, 0, 1, 0, 0, 1 }, new List<int>{ 0, 0, 1, 0, 0, 1 } }; int rows = matrix.Count; int columns = matrix[0].Count; DuplicateRows(matrix, rows, columns); }}// Contributed by adityasha4x71 |
Output
There is a duplicate row at position: 4 There is a duplicate row at position: 5 There is a duplicate row at position: 6
- Time complexity : O(ROW^2 x COL)
- Auxiliary Space : O(1)
Optimal solution using Trie Trie is an efficient data structure used for storing and retrieval of data where the character set is small. The searching complexity is optimal as key length.
The solution approach towards the question is to first insert the matrix in the binary trie and then if the new added row is already present in the trie then we will now that it is a duplicate row
Implementation:
C++
// C++ program to find duplicate rows// in a binary matrix.#include<bits/stdc++.h>const int MAX = 100;/*struct the Trie*/struct Trie{ bool leaf; Trie* children[2];};/*function to get Trienode*/Trie* getNewTrieNode(){ Trie* node = new Trie; node->children[0] = node->children[1] = NULL; node->leaf = false; return node;}/* function to insert a row in Trie*/bool insert(Trie*& head, bool* arr, int N){ Trie* curr = head; for (int i = 0; i < N; i++) { /*creating a new path if it don not exist*/ if (curr->children[arr[i]] == NULL) curr->children[arr[i]] = getNewTrieNode(); curr = curr->children[arr[i]]; } /*if the row already exist return false*/ if (curr->leaf) return false; /* making leaf node tree and return true*/ return (curr->leaf = true);}void printDuplicateRows(bool mat[][MAX], int M, int N){ Trie* head = getNewTrieNode(); /*inserting into Trie and checking for duplicates*/ for (int i = 0; i < M; i++) // If already exists if (!insert(head, mat[i], N)) printf("There is a duplicate row" " at position: %d \n", i+1);}/*driver function to check*/int main(){ bool mat[][MAX] = { {1, 1, 0, 1, 0, 1}, {0, 0, 1, 0, 0, 1}, {1, 0, 1, 1, 0, 0}, {1, 1, 0, 1, 0, 1}, {0, 0, 1, 0, 0, 1}, {0, 0, 1, 0, 0, 1}, }; printDuplicateRows(mat, 6, 6); return 0;} |
Java
// Java program to find duplicate rows// in a binary matrix.class GFG{ static final int MAX = 100; static class Trie { public boolean leaf; public Trie children[] = new Trie[2]; }; //function to get Trienode/ static Trie getNewTrieNode() { Trie node = new Trie(); node.children[0] = null; node.children[1] = null; node.leaf = false; return node; } // function to insert a row in Trie/ static boolean insert(Trie head, int[] arr, int N) { Trie curr = head; for (int i = 0; i < N; i++) { //creating a new path if it don not exist/ if (curr.children[arr[i] ] == null) curr.children[arr[i]] = getNewTrieNode(); curr = curr.children[arr[i]]; } //if the row already exist return false/ if (curr.leaf) return false; // making leaf node tree and return true/ curr.leaf = true; return true; } static void printDuplicateRows(int[][] mat, int M, int N) { Trie head = getNewTrieNode(); //inserting into Trie and checking for duplicates for (int i = 0; i < M; i++) // If already exists if (!insert(head, mat[i], N)) System.out.printf("There is a duplicate row at position: %d \n", i+1); } // driver function to check/ public static void main(String[] args) { int mat[][] = { {1, 1, 0, 1, 0, 1}, {0, 0, 1, 0, 0, 1}, {1, 0, 1, 1, 0, 0}, {1, 1, 0, 1, 0, 1}, {0, 0, 1, 0, 0, 1}, {0, 0, 1, 0, 0, 1}, }; printDuplicateRows(mat, 6, 6); }}// This code is contributed by phasing17. |
Python3
# Python3 program to find duplicate rows# in a binary matrix.class Trie: def __init__(self): self.leaf = False; self.children = [None, None] MAX = 100;# function to get Trienodedef getNewTrieNode(): node = Trie(); node.children[0] = None; node.children[1] = None; node.leaf = False; return node;# function to insert a row in Trie/def insert(head, arr, N): curr = head; for i in range(N): # creating a new path if it don not exist/ if (curr.children[arr[i]] == None): curr.children[arr[i]] = getNewTrieNode(); curr = curr.children[arr[i]]; # if the row already exist return False/ if (curr.leaf): return False; # making leaf node tree and return True/ curr.leaf = True; return True;def printDuplicateRows(mat, M, N): head = getNewTrieNode(); # inserting into Trie and checking for duplicates for i in range(M): # If already exists if (not insert(head, mat[i], N)): print( "There is a duplicate row at position:", (i + 1));# driver function to check/mat = [ [ 1, 1, 0, 1, 0, 1 ], [ 0, 0, 1, 0, 0, 1 ], [ 1, 0, 1, 1, 0, 0 ], [ 1, 1, 0, 1, 0, 1 ], [ 0, 0, 1, 0, 0, 1 ], [ 0, 0, 1, 0, 0, 1 ],];printDuplicateRows(mat, 6, 6);# This code is contributed by phasing17 |
C#
// C# program to find duplicate rows// in a binary matrix.using System;using System.Collections.Generic;class Trie{ public bool leaf; public Trie[] children = new Trie[2];};class GFG{ static int MAX = 100; // function to get Trienode/ static Trie getNewTrieNode() { Trie node = new Trie(); node.children[0] = null; node.children[1] = null; node.leaf = false; return node; } // function to insert a row in Trie/ static bool insert(Trie head, int[] arr, int N) { Trie curr = head; for (int i = 0; i < N; i++) { //creating a new path if it don not exist/ if (curr.children[arr[i] ] == null) curr.children[arr[i]] = getNewTrieNode(); curr = curr.children[arr[i]]; } //if the row already exist return false/ if (curr.leaf) return false; // making leaf node tree and return true/ curr.leaf = true; return true; } static void printDuplicateRows(int[][] mat, int M, int N) { Trie head = getNewTrieNode(); // inserting into Trie and checking for duplicates for (int i = 0; i < M; i++) // If already exists if (!insert(head, mat[i], N)) Console.WriteLine("There is a duplicate row at position: " + (i+1)); } // driver function to check/ public static void Main(string[] args) { int[][] mat = { new int[] {1, 1, 0, 1, 0, 1}, new int[] {0, 0, 1, 0, 0, 1}, new int[] {1, 0, 1, 1, 0, 0}, new int[] {1, 1, 0, 1, 0, 1}, new int[] {0, 0, 1, 0, 0, 1}, new int[] {0, 0, 1, 0, 0, 1}, }; printDuplicateRows(mat, 6, 6); }}// This code is contributed by phasing17. |
Javascript
// JS program to find duplicate rows// in a binary matrix.class Trie { constructor() { this.leaf = false; this.children = new Array(2); }};let MAX = 100;// function to get Trienode/function getNewTrieNode(){ let node = new Trie(); node.children[0] = null; node.children[1] = null; node.leaf = false; return node;}// function to insert a row in Trie/function insert(head, arr, N){ let curr = head; for (let i = 0; i < N; i++) { // creating a new path if it don not exist/ if (curr.children[arr[i]] == null) curr.children[arr[i]] = getNewTrieNode(); curr = curr.children[arr[i]]; } // if the row already exist return false/ if (curr.leaf) return false; // making leaf node tree and return true/ curr.leaf = true; return true;}function printDuplicateRows(mat, M, N){ let head = getNewTrieNode(); // inserting into Trie and checking for duplicates for (let i = 0; i < M; i++) // If already exists if (!insert(head, mat[i], N)) console.log( "There is a duplicate row at position: " + (i + 1));}// driver function to check/let mat = [ [ 1, 1, 0, 1, 0, 1 ], [ 0, 0, 1, 0, 0, 1 ], [ 1, 0, 1, 1, 0, 0 ], [ 1, 1, 0, 1, 0, 1 ], [ 0, 0, 1, 0, 0, 1 ], [ 0, 0, 1, 0, 0, 1 ],];printDuplicateRows(mat, 6, 6);// This code is contributed by phasing17. |
Output
There is a duplicate row at position: 4 There is a duplicate row at position: 5 There is a duplicate row at position: 6
Time Complexity: O(M*N)
Auxiliary Space: O(M*N), to build trie.
Another approach without using Trie but does not work for large number of columns :
Another approach is to convert the decimal equivalent of row and check if a new row has the same decimal equivalent then it is a duplicate row. It will not work if the number of columns is large .
Here is the implementation of the above approach.
C++
#include<iostream>#include<vector>#include<set>using namespace std;vector<int> repeatedRows(vector<vector<int>> matrix, int M, int N) { set<int>s; // vector to store the repeated rows vector<int>res; for(int i=0;i<M;i++){ // calculating decimal equivalent of the row int no=0; for(int j=0;j<N;j++){ no+=(matrix[i][j]<<j); } /* rows with same decimal equivalent will be same, therefore, checking through set if the calculated equivalent was present before; if yes then add to the result otherwise insert in the set */ if(s.find(no)!=s.end()){ res.push_back(i); } else{ s.insert(no); } } return res; } int main() { vector<vector<int>>matrix={ {1, 1, 0, 1, 0, 1}, {0, 0, 1, 0, 0, 1}, {1, 0, 1, 1, 0, 0}, {1, 1, 0, 1, 0, 1}, {0, 0, 1, 0, 0, 1}, {0, 0, 1, 0, 0, 1},}; int m=matrix.size(); int n=matrix[0].size(); vector<int>res=repeatedRows(matrix,m,n); for(int e:res){ cout<< "There is a duplicate row at position: "<<e+1 << '\n'; } return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG { static ArrayList<Integer> repeatedRows(int[][] matrix, int M, int N) { TreeSet<Integer> s = new TreeSet<>(); // vector to store the repeated rows ArrayList<Integer> res = new ArrayList<>(); for(int i = 0; i < M; i++) { // calculating decimal equivalent of the row int no = 0; for(int j = 0; j < N; j++) { no+=(matrix[i][j]<<j); } /* rows with same decimal equivalent will be same, therefore, checking through set if the calculated equivalent was present before; if yes then add to the result otherwise insert in the set */ if(s.contains(no)){ res.add(i); } else{ s.add(no); } } return res; } // Driver Code public static void main(String args[]) { int[][] matrix={ {1, 1, 0, 1, 0, 1}, {0, 0, 1, 0, 0, 1}, {1, 0, 1, 1, 0, 0}, {1, 1, 0, 1, 0, 1}, {0, 0, 1, 0, 0, 1}, {0, 0, 1, 0, 0, 1} }; int m = matrix.length; int n = matrix[0].length; ArrayList<Integer> res = repeatedRows(matrix,m,n); for(int e:res){ System.out.println("There is a duplicate row at position: "+(e+1)); } }}// This code is contributed by shinjanpatra |
Python3
def repeatedRows(matrix, M, N): s = set() # vector to store the repeated rows res = [] for i in range(M): # calculating decimal equivalent of the row no = 0 for j in range(N): no += (matrix[i][j] << j) # rows with same decimal equivalent will be same, # therefore, checking through set if the calculated equivalent was # present before # if yes then add to the result otherwise insert in the set if(no in s): res.append(i) else: s.add(no) return res# driver codematrix = [ [1, 1, 0, 1, 0, 1], [0, 0, 1, 0, 0, 1], [1, 0, 1, 1, 0, 0], [1, 1, 0, 1, 0, 1], [0, 0, 1, 0, 0, 1], [0, 0, 1, 0, 0, 1]] m = len(matrix)n = len(matrix[0])res = repeatedRows(matrix,m,n)for e in res: print("There is a duplicate row at position: "+str(e+1))# This code is contributed by shinjanpatra |
C#
using System;using System.Collections.Generic;class GFG { static List<int> repeatedRows(int[, ] matrix, int M, int N) { HashSet<int> s = new HashSet<int>(); // vector to store the repeated rows List<int> res = new List<int>(); for(int i = 0; i < M; i++) { // calculating decimal equivalent of the row int no = 0; for(int j = 0; j < N; j++) { no+=(matrix[i, j]<<j); } /* rows with same decimal equivalent will be same, therefore, checking through set if the calculated equivalent was present before; if yes then add to the result otherwise insert in the set */ if(s.Contains(no)){ res.Add(i); } else{ s.Add(no); } } return res; } // Driver Code public static void Main(string[] args) { int[, ] matrix={ {1, 1, 0, 1, 0, 1}, {0, 0, 1, 0, 0, 1}, {1, 0, 1, 1, 0, 0}, {1, 1, 0, 1, 0, 1}, {0, 0, 1, 0, 0, 1}, {0, 0, 1, 0, 0, 1} }; int m = matrix.GetLength(0); int n = matrix.GetLength(1); List<int> res = repeatedRows(matrix,m,n); foreach (int e in res){ Console.WriteLine("There is a duplicate row at position: "+(e+1)); } }}// This code is contributed by phasing17 |
Javascript
<script>function repeatedRows(matrix,M,N) { let s = new Set(); // vector to store the repeated rows let res = []; for(let i=0;i<M;i++){ // calculating decimal equivalent of the row let no=0; for(let j=0;j<N;j++){ no+=(matrix[i][j]<<j); } /* rows with same decimal equivalent will be same, therefore, checking through set if the calculated equivalent was present before; if yes then add to the result otherwise insert in the set */ if(s.has(no)){ res.push(i); } else{ s.add(no); } } return res; } // driver codelet matrix = [ [1, 1, 0, 1, 0, 1], [0, 0, 1, 0, 0, 1], [1, 0, 1, 1, 0, 0], [1, 1, 0, 1, 0, 1], [0, 0, 1, 0, 0, 1], [0, 0, 1, 0, 0, 1]]; let m = matrix.length;let n = matrix[0].length;let res = repeatedRows(matrix,m,n);for(let e of res){ document.write("There is a duplicate row at position: "+(e+1),"</br>");}// This code is contributed by shinjanpatra</script> |
Output
There is a duplicate row at position: 4 There is a duplicate row at position: 5 There is a duplicate row at position: 6
Time Complexity: O(M*N)
Auxiliary Space: O(M), where M is number of rows
This article is contributed by Pranav. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
