Duplicate Rows in a Binary Matrix

Last Updated : 1 Apr, 2026

Given a binary matrix mat[][], print the rows which are duplicates of rows that are already present in the matrix.

Examples: 

Input: 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]]
Output: [4, 5, 6]
Explanation: Row at index 4 is same as 0. Rows at indexes 5 and 6 are same as index 1

Try it on GfG Practice
redirect icon

Table of Content

[Naive Approach] Traverse All Rows - O((m^2)*n) Time and O(1) Space

For each row, check if it already exists by scanning all previous rows.

C++ 
#include <iostream>
#include <vector>
using namespace std;

class Solution {
  public:
    vector<int> repeatedRows(vector<vector<int>> &matrix, int rows, int columns) {
        vector<int> result;

        for (int i = 0; i < rows; i++) {
            bool found = false;

            for (int j = 0; j < i; j++) {
                int k = 0;
                
                // check if all elements of both rows are equal or not
                for (k = 0; k < columns; k++) {
                    if (matrix[i][k] != matrix[j][k])
                        break;
                }

                // all elements matched -> duplicate row found
                if (k == columns) {
                    found = true;
                    break;
                }
            }

            // store index of duplicate row
            if (found) {
                result.push_back(i);
            }
        }

        return result;
    }
};

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

    Solution obj;
    vector<int> duplicates = obj.repeatedRows(matrix, rows, columns);

    for (int idx : duplicates) {
        cout << idx + 1 << " ";
    }

    return 0;
}
Java 
import java.util.ArrayList;

public class GFG {

    public static ArrayList<Integer>
    repeatedRows(ArrayList<ArrayList<Integer>> matrix,
                 int rows, int columns)
    {
        ArrayList<Integer> result = new ArrayList<>();

        for (int i = 0; i < rows; i++) {
            boolean found = false;

            for (int j = 0; j < i; j++) {
                int k = 0;

                // check if all elements of both rows are equal or not
                for (k = 0; k < columns; k++) {
                    if (!matrix.get(i).get(k)
                             .equals(matrix.get(j).get(k)))
                        break;
                }

                // all elements matched -> duplicate row found
                if (k == columns) {
                    found = true;
                    break;
                }
            }

            // store index of duplicate row
            if (found) {
                result.add(i);
            }
        }

        return result;
    }

    public static void main(String[] args)
    {
        ArrayList<ArrayList<Integer>> matrix
            = new ArrayList<>();

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

        ArrayList<Integer> duplicates =
            repeatedRows(matrix, rows, columns);

        for (int idx : duplicates) {
            System.out.print((idx + 1) + " ");
        }
    }
}
Python 
def repeatedRows(matrix, rows, columns):
    result = []

    for i in range(rows):
        found = False

        for j in range(i):
            k = 0
            
            # check if all elements of both rows are equal or not
            while k < columns:
                if matrix[i][k] != matrix[j][k]:
                    break
                k += 1

            # all elements matched -> duplicate row found
            if k == columns:
                found = True
                break

        # store index of duplicate row
        if found:
            result.append(i)

    return result


if __name__ == "__main__":
    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])

    duplicates = repeatedRows(matrix, rows, columns)

    for idx in duplicates:
        print(idx + 1, end=" ")
C# 
using System;
using System.Collections.Generic;

public class GFG {
    
    public static List<int>
    repeatedRows(List<List<int>> matrix, int rows, int columns)
    {
        List<int> result = new List<int>();

        for (int i = 0; i < rows; i++) {
            bool found = false;

            for (int j = 0; j < i; j++) {
                int k = 0;
                
                // check if all elements of both rows are equal or not
                for (k = 0; k < columns; k++) {
                    if (matrix[i][k] != matrix[j][k])
                        break;
                }

                // all elements matched -> duplicate row found
                if (k == columns) {
                    found = true;
                    break;
                }
            }

            // store index of duplicate row
            if (found) {
                result.Add(i);
            }
        }

        return result;
    }

    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;

        List<int> duplicates =
            repeatedRows(matrix, rows, columns);

        foreach (int idx in duplicates) {
            Console.Write((idx + 1) + " ");
        }
    }
}
JavaScript 
function repeatedRows(matrix, rows, columns) {
    const result = [];

    for (let i = 0; i < rows; i++) {
        let found = false;

        for (let j = 0; j < i; j++) {
            let k = 0;
            
            // check if all elements of both rows are equal or not
            while (k < columns) {
                if (matrix[i][k] !== matrix[j][k]) {
                    break;
                }
                k++;
            }

            // all elements matched -> duplicate row found
            if (k === columns) {
                found = true;
                break;
            }
        }

        // store index of duplicate row
        if (found) {
            result.push(i);
        }
    }

    return result;
}

// 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;

const duplicates = repeatedRows(matrix, rows, columns);

for (let idx of duplicates) {
    console.log(idx + 1);
}

Output
4 5 6

[Expected Approach-1] Using Trie - O(m*n) Time and O(m*n) Space

A Trie is used to efficiently store rows of the binary matrix since each row contains only 0 and 1. Each row is inserted as a path in the Trie. If the path already exists and the final node is marked as a leaf, the row is identified as a duplicate, otherwise the row is inserted and the end node is marked.

C++ 
#include <iostream>
#include <vector>
using namespace std;

struct Trie {
    bool leaf;
    Trie* children[2];
};

Trie* getNewTrieNode() {
    Trie* node = new Trie;
    node->children[0] = node->children[1] = NULL;
    node->leaf = false;
    return node;
}

bool insert(Trie*& head, vector<int>& row, int columns) {
    Trie* curr = head;

    for (int i = 0; i < columns; i++) {
        if (curr->children[row[i]] == NULL)
            curr->children[row[i]] = getNewTrieNode();

        curr = curr->children[row[i]];
    }

    // row already exists in trie
    if (curr->leaf)
        return false;

    return (curr->leaf = true);
}

class Solution {
  public:
    vector<int> repeatedRows(vector<vector<int>> &matrix, int rows, int columns) {
        vector<int> result;
        Trie* head = getNewTrieNode();

        for (int i = 0; i < rows; i++) {

            // insert row and check for duplication
            if (!insert(head, matrix[i], columns)) {
                result.push_back(i);
            }
        }

        return result;
    }
};

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

    Solution obj;
    vector<int> duplicates = obj.repeatedRows(matrix, rows, columns);

    for (int idx : duplicates) {
        cout << idx + 1 << " ";
    }

    return 0;
}
Java 
import java.util.ArrayList;

class GFG {
    static class Trie {
        boolean leaf;
        Trie[] children = new Trie[2];
    }

    static Trie getNewTrieNode() {
        Trie node = new Trie();
        node.children[0] = null;
        node.children[1] = null;
        node.leaf = false;
        return node;
    }

    static boolean insert(Trie head, int[] arr, int columns) {
        Trie curr = head;

        for (int i = 0; i < columns; i++) {
            if (curr.children[arr[i]] == null)
                curr.children[arr[i]] = getNewTrieNode();

            curr = curr.children[arr[i]];
        }

        // row already exists in trie
        if (curr.leaf)
            return false;

        return (curr.leaf = true);
    }

    static ArrayList<Integer> repeatedRows(int[][] mat, int rows, int columns) {
        ArrayList<Integer> result = new ArrayList<>();
        Trie head = getNewTrieNode();

        for (int i = 0; i < rows; i++) {

            // insert row and check for duplication
            if (!insert(head, mat[i], columns)) {
                result.add(i);
            }
        }

        return result;
    }

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

        int rows = mat.length;
        int columns = mat[0].length;

        ArrayList<Integer> duplicates =
            repeatedRows(mat, rows, columns);

        for (int idx : duplicates) {
            System.out.print((idx + 1) + " ");
        }
    }
}
Python 
class Trie:
    def __init__(self):
        self.leaf = False
        self.children = [None, None]


def getNewTrieNode():
    return Trie()


def insert(head, arr, columns):
    curr = head

    for i in range(columns):
        if curr.children[arr[i]] is None:
            curr.children[arr[i]] = getNewTrieNode()

        curr = curr.children[arr[i]]

    # row already exists in trie
    if curr.leaf:
        return False

    curr.leaf = True
    return True


def repeatedRows(mat, rows, columns):
    result = []
    head = getNewTrieNode()

    for i in range(rows):

        # insert row and check for duplication
        if not insert(head, mat[i], columns):
            result.append(i)

    return result


if __name__ == "__main__":
    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],
    ]

    rows = len(mat)
    columns = len(mat[0])

    duplicates = repeatedRows(mat, rows, columns)

    for idx in duplicates:
        print(idx + 1, end=" ")
C# 
using System;
using System.Collections.Generic;

class Trie {
    public bool leaf;
    public Trie[] children = new Trie[2];
}

class GFG {

    static Trie getNewTrieNode()
    {
        return new Trie();
    }

    static bool insert(Trie head, int[] arr, int columns)
    {
        Trie curr = head;

        for (int i = 0; i < columns; i++) {
            if (curr.children[arr[i]] == null)
                curr.children[arr[i]] = getNewTrieNode();

            curr = curr.children[arr[i]];
        }

        // row already exists in trie
        if (curr.leaf)
            return false;

        curr.leaf = true;
        return true;
    }

    static List<int> repeatedRows(int[][] mat, int rows, int columns)
    {
        List<int> result = new List<int>();
        Trie head = getNewTrieNode();

        for (int i = 0; i < rows; i++) {

            // insert row and check for duplication
            if (!insert(head, mat[i], columns)) {
                result.Add(i);
            }
        }

        return result;
    }

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

        int rows = mat.Length;
        int columns = mat[0].Length;

        List<int> duplicates =
            repeatedRows(mat, rows, columns);

        foreach (int idx in duplicates) {
            Console.Write((idx + 1) + " ");
        }
    }
}
JavaScript 
class Trie {
    constructor() {
        this.leaf = false;
        this.children = new Array(2).fill(null);
    }
}

function getNewTrieNode() {
    return new Trie();
}

function insert(head, arr, columns) {
    let curr = head;

    for (let i = 0; i < columns; i++) {
        if (curr.children[arr[i]] === null)
            curr.children[arr[i]] = getNewTrieNode();

        curr = curr.children[arr[i]];
    }

    // row already exists in trie
    if (curr.leaf)
        return false;

    curr.leaf = true;
    return true;
}

function repeatedRows(mat, rows, columns) {
    const result = [];
    let head = getNewTrieNode();

    for (let i = 0; i < rows; i++) {

        // insert row and check for duplication
        if (!insert(head, mat[i], columns)) {
            result.push(i);
        }
    }

    return result;
}

// Driver code
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],
];

let rows = mat.length;
let columns = mat[0].length;

let duplicates = repeatedRows(mat, rows, columns);

for (let idx of duplicates) {
    console.log(idx + 1);
}

Output
4 5 6

[Expected Approach-2] Using a hash set of rows as strings: O(m*n) Time and O(m*n) Space

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.

C++ 
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
  public:
    vector<int> repeatedRows(vector<vector<int>> &matrix, int rows, int columns) {
        vector<int> result;
        unordered_set<string> seen;

        for (int i = 0; i < rows; i++) {
            string temp = "";
            
            // build string representation of current row
            for (int j = 0; j < columns; j++) {
                temp += to_string(matrix[i][j]);
            }

            // row already exists in set
            if (seen.find(temp) != seen.end()) {
                result.push_back(i);
            }
            else {
                seen.insert(temp);
            }
        }

        return result;
    }
};

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

    Solution obj;
    vector<int> duplicates = obj.repeatedRows(matrix, rows, columns);

    for (int idx : duplicates) {
        cout << idx + 1 << " ";
    }

    return 0;
}
Java 
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class GFG {

    public static List<Integer> repeatedRows(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        Set<String> seen = new HashSet<>();

        for (int i = 0; i < matrix.length; i++) {
            StringBuilder temp = new StringBuilder();
            
            // build string representation of current row
            for (int j = 0; j < matrix[0].length; j++) {
                temp.append(matrix[i][j]);
            }

            String rowString = temp.toString();

            // row already exists in set
            if (seen.contains(rowString)) {
                result.add(i);
            }
            else {
                seen.add(rowString);
            }
        }

        return result;
    }

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

        List<Integer> duplicates = repeatedRows(matrix);

        for (int idx : duplicates) {
            System.out.print((idx + 1) + " ");
        }
    }
}
Python 
def repeatedRows(matrix):
    result = []
    seen = set()

    for i, row in enumerate(matrix):
        
        # build string representation of current row
        row_str = ''.join(map(str, row))

        # row already exists in set
        if row_str in seen:
            result.append(i)
        else:
            seen.add(row_str)

    return result


if __name__ == "__main__":
    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],
    ]

    duplicates = repeatedRows(matrix)

    for idx in duplicates:
        print(idx + 1, end=" ")
C# 
using System;
using System.Collections.Generic;

class GFG {

    static List<int> repeatedRows(int[][] matrix)
    {
        List<int> result = new List<int>();
        HashSet<string> seen = new HashSet<string>();
        
        for (int i = 0; i < matrix.Length; i++) {
            string temp = "";
            
            // build string representation of current row
            for (int j = 0; j < matrix[0].Length; j++) {
                temp += matrix[i][j];
            }

            // row already exists in set
            if (seen.Contains(temp)) {
                result.Add(i);
            }
            else {
                seen.Add(temp);
            }
        }

        return result;
    }

    public static void Main(string[] args)
    {
        int[][] matrix = {
            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 }
        };

        List<int> duplicates = repeatedRows(matrix);

        foreach (int idx in duplicates) {
            Console.Write((idx + 1) + " ");
        }
    }
}
JavaScript 
function repeatedRows(matrix) {
    const result = [];
    const seen = new Set();

    for (let i = 0; i < matrix.length; i++) {
        let temp = '';
        
        // build string representation of current row 
        for (let j = 0; j < matrix[0].length; j++) {
            temp += matrix[i][j];
        }

        // row already exists in set
        if (seen.has(temp)) {
            result.push(i);
        } else {
            seen.add(temp);
        }
    }

    return result;
}

// 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 result = repeatedRows(matrix);

for (let idx of result) {
    console.log(idx + 1);
}

Output
4 5 6
Comment
Article Tags:
Matrix
Advanced Data Structure
DSA
Trie

Explore