Find all permuted rows of a given row in a matrix

Introduction

In this article, we are going to learn how we can find all the permute rows of a given row in a matrix with the help of the hash set.

A hash set is a collection of objects that do not contain duplicate values in the set. It quickly helps to determine whether the particular object is present in the set or not. It has various operations that will help us to find a optimal solution.

Problem Statement

The problem statement is here that we have given an m*n 2-d matrix, and we are asked to find all the permutations of a particular row in the matrix. Permutations here mean that all the elements of the given row should be present in other rows

Sample Examples

Input: ArrayMatrix=[  [ 12,4,8,10],

                                  [ 1,4,6,10],

                                  [ 10,12,4,8],

                                  [ 4,12,10,8] ]

Output: 1 , 2

Explanation

Approach

For this problem, we are going to use a HashSet in order to find the solution. Firstly we will store the given row whose permutations are going to be found in the HashSet; after this will traverse over the given matrix to find the permuted rows except for the given row. In the traversing, we will use the check whether the elements in each row are present in the HashSet or not. If all of that particular row is present in the HashSet, we will print the row number on the console.

Algorithm

• Start
• Declare the size of the matrix mxn and row number whose permutation we need to find.
• Declare the 2-d matrix
• Print the matrix and row number on console
• Intialise the hashset for the problem
• Insert the given row into the hashset
• Iterate in a nested loop of m and n to find the permuted row.
• Ignore the iteration if the given row number and current row are the same.
• After finding the permuted row print on the console.
• End

Implementation

C++

#include<iostream>
#include<unordered_set>
#define MAX 100
using namespace std;
int main()
{
    int row = 4, col = 4,r = 2;
    int matrix[][MAX] = {{6, 5, 9, 2},
        {18, 6, 9, 3},
        {3, 18, 9, 6},
        {6, 18, 3, 9}
    };
    
    /* given matrix */
    cout<<"Given matrix:"<<endl;
    for(int i=0;i<row;i++)
    {
        cout<<"["<<" ";
        for(int j=0;j<col;j++)
        {
            cout<<matrix[i][j]<<" ";
        }
        cout<<"]\n";
    }
    
    /* printing given row */
    cout<<"Row number: "<<r<<endl;
    
    /*create hashset */
    unordered_set<int> s;
    
    /* inserting the given row into hashset */
    for (int j=0; j<col; j++)
        s.insert(matrix[r][j]);
        
    /* checking and printing the permuted rows */
    cout<<"permuted rows: ";
    for (int i=0; i<row; i++)
    {
        if (i==r)
            continue;
        int j;
        for (j=0; j<col; j++)
            if(s.find(matrix[i][j]) == s.end())
                break;
        if (j != col)
            continue;
        cout << i << ", ";
    }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Python

if __name__ == '__main__':
    row = 4
    col = 4
    r = 3
    mat = [[6, 5, 9, 2],
        [18, 6, 9, 3],
        [3, 18, 9, 6],
        [6, 18, 3, 9]]


    print("Given matrix: ",mat)
    print("row number: ",r)
    
    #create hashset
    s=set()
    
    #inserting the given row into hashset
    for i in range(col):
        s.add(mat[r][i])
    
    #checking and printing the permuted rows
    print("permuted rows:",end=" ")
    for i in range(row):
        if i == r:
            continue
        for j in range(col):
            if mat[i][j] not in s:
                j = j - 2
                break
            if j + 1 !=col:
                continue
            print(i,end=" ")

You can also try this code with Online Python Compiler

Run Code

Java

import java.util.LinkedHashSet;
class Main
{
    private static int MAX = 100;
    public static void main(String[] args)
    {
        int  row= 4, col = 4,r = 2;
        int matrix[][] ={{6, 5, 9, 2},
        {18, 6, 9, 3},
        {3, 18, 9, 6},
        {6, 18, 3, 9}};
        
        
    /* given matrix */
    System.out.println("Given matrix:");
    for(int i=0;i<row;i++)
    {
       System.out.print("[");
        for(int j=0;j<col;j++)
        {
        System.out.print(matrix[i][j] + " ");
        }
        System.out.println("]");
    }
    
    /* printing given row */
     System.out.println("Row number:" + r);
     
     /* create hashset */
     LinkedHashSet<Integer> SET = new LinkedHashSet<>();
     
     
    /* inserting the given row into hashset */
       System.out.print("Permuted rows: ");
        for (int j = 0; j < col; j++)
            SET.add(matrix[r][j]);
            
        
    /* checking and printing the permuted rows */
        for (int i = 0; i < row; i++)
        {
            if (i == r)
                continue;
            int j;
            for (j = 0; j < col; j++)
                if (!SET.contains(matrix[i][j]))
                    break;
            if (j != col)
                continue;
            System.out.print(i+", ");
        }

    }
}

You can also try this code with Online Java Compiler

Run Code

Input: {{6, 5, 9, 2},

        {18, 6, 9, 3},

        {3, 18, 9, 6},

        {6, 18, 3, 9}};

r = 2 (here r is the given row)

Output:

Time Complexity

O(m*n) here m and n are rows and columns of the given matrix. Whether it is to find the permuted rows or to print the given matrix both are done in row*column iterations. So that's why.

Space Complexity

O(n).

You can also read about the Longest Consecutive Sequence.