Find duplicate rows in a binary matrix

Last Updated : 15 Apr, 2024

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 rows void 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 code 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 rows = matrix.size();  int columns = matrix[0].size();  duplicate_rows(matrix, rows, columns);  return 0; } // This code is contributed by Aman Kumar.

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);  } }

Python3

# Python code for above approach def 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 code 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]] rows = len(matrix) columns = len(matrix[0]) duplicate_rows(matrix, rows, columns) # This code is contributed by sdeaditysharma

// C# code for above approach using 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

JavaScript

// JavaScript code for above approach function duplicate_rows(matrix, rows, columns) { // loop through all rows for (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 code const 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);

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 Trienode def 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# 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 <set> #include <vector> 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 code 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] ] 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

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 code let 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

Finding duplicate rows in a binary matrix by converting each row into string:

Use a hash set to store string representations of each row, allowing for quick lookup and comparison. By iterating through the rows and concatenating their elements into strings, then checks for duplicate strings in the hash set. If a duplicate is found, the index of the corresponding row is added to a result array.

Steps-by-step approach:

Create an empty hash set called rows to store string representations of the rows in the matrix.
Iterate Through Rows, for each row in the matrix:
- Create an empty string temp.
- Iterate through the elements of the row and concatenate them to temp. This creates a string representation of the row.
- Check if temp already exists in the rows hash set.
  - If it does, it means the row is a duplicate, so add its index to the result vector.
  - If it doesn't, insert temp into the rows hash set.
After processing all rows, return the result[] array containing the indices of the duplicate rows.

Below are the implementation of the above approach:

C++

// C++ program to find duplicate rows // in a binary matrix. #include <bits/stdc++.h> using namespace std; // Function to find duplicate rows in a binary matrix vector<int> repeatedRows(vector<vector<int> > matrix, int M,  int N) {  // Stores the indices of duplicate rows  vector<int> result;  // Hash set to store string representation of rows  unordered_set<string> rows;  // Traverse each row of the matrix  for (int i = 0; i < M; ++i) {  string temp = "";  // Concatenate each element of the row to form a  // string  for (int j = 0; j < N; ++j) {  temp = temp + to_string(matrix[i][j]);  }  // If the row string is already present in the set,  // it's a duplicate row, so add its index to the  // result vector  if (rows.find(temp) != rows.end()) {  result.push_back(i);  }  // Otherwise, insert the row string into the set  else {  rows.insert(temp);  }  }  return result; } // Main function int main() {  // Binary matrix  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 },  };  // Number of rows in the matrix  int m = matrix.size();  // Number of columns in the matrix  int n = matrix[0].size();  // Find duplicate rows and store their indices in res  // vector  vector<int> res = repeatedRows(matrix, m, n);  // Print the indices of duplicate rows  for (int e : res) {  cout << "There is a duplicate row at position: "  << e + 1 << '\n';  }  return 0; }

Java

import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; public class DuplicateRowsInMatrix {  // Function to find duplicate rows in a binary matrix  public static List<Integer> repeatedRows(int[][] matrix)  {  // Stores the indices of duplicate rows  List<Integer> result = new ArrayList<>();  // Set to store string representation of rows  Set<String> rows = new HashSet<>();  // Traverse each row of the matrix  for (int i = 0; i < matrix.length; i++) {  StringBuilder temp = new StringBuilder();  // Concatenate each element of the row to form a  // string  for (int j = 0; j < matrix[0].length; j++) {  temp.append(matrix[i][j]);  }  String rowString = temp.toString();  // If the row string is already present in the  // set, it's a duplicate row, so add its index  // to the result list  if (rows.contains(rowString)) {  result.add(i);  }  else {  // Otherwise, insert the row string into the  // set  rows.add(rowString);  }  }  return result;  }  // Main method  public static void main(String[] args)  {  // Binary matrix  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 }  };  // Find duplicate rows and store their indices in  // res list  List<Integer> res = repeatedRows(matrix);  // Print the indices of duplicate rows  for (int e : res) {  System.out.println(  "There is a duplicate row at position: "  + (e + 1));  }  } }

Python3

# Function to find duplicate rows in a binary matrix def repeated_rows(matrix): # Stores the indices of duplicate rows result = [] # Set to store string representation of rows rows = set() # Traverse each row of the matrix for i, row in enumerate(matrix): # Convert row to string row_str = ''.join(map(str, row)) # If the row string is already present in the set, # it's a duplicate row, so add its index to the # result list if row_str in rows: result.append(i) # Otherwise, insert the row string into the set else: rows.add(row_str) return result # Binary matrix 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], ] # Find duplicate rows and store their indices in res list res = repeated_rows(matrix) # Print the indices of duplicate rows for idx in res: print("There is a duplicate row at position:", idx + 1)

JavaScript

// Function to find duplicate rows in a binary matrix function repeatedRows(matrix) {  // Stores the indices of duplicate rows  let result = [];  // Set to store string representation of rows  let rows = new Set();  // Traverse each row of the matrix  for (let i = 0; i < matrix.length; i++) {  let temp = '';  // Concatenate each element of the row to form a string  for (let j = 0; j < matrix[0].length; j++) {  temp += matrix[i][j];  }  let rowString = temp;  // If the row string is already present in the set, it's a duplicate row, so add its index to the result list  if (rows.has(rowString)) {  result.push(i);  } else {  // Otherwise, insert the row string into the set  rows.add(rowString);  }  }  return result; } // Main method function main() {  // Binary matrix  let 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]  ];  // Find duplicate rows and store their indices in result array  let result = repeatedRows(matrix);  // Print the indices of duplicate rows  result.forEach(e => {  console.log("There is a duplicate row at position: " + (e + 1));  }); } // Calling the main function main();

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

pranav gupta

Article Tags :

Find duplicate rows in a binary matrix

Finding duplicate rows in a binary matrix by converting each row into string:

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem

My Profile

Thank You!

What kind of Experience do you want to share?