Given a matrix mat[][] of size N * N (1 ? N ? 1000), the task is to find the number of pairs of rows and columns (Rowi, Colj), such that row Rowi and column Colj are equal.
Note: A row and column pair are considered equal if they contain the same elements in the same order (i.e. an equal array).
Example:
Input:
Matrix
Output: 3
Explanation: The row-column pairs are {1, 1}, {3, 2}, {3, 3}.Input:
Example matrix
Output: 6
An approach using Hashing:
Iterate on the matrix and keep all the elements of each row into a string and store these strings into map with their frequency. Iterate over the map and keep all the elements of each column into a string and then check if column string has any occurrence into map. If there exist any occurrence into map then keep adding their count into result.
Follow the steps below to implement the above idea:
- Initialize a map for mapping all columns with their frequency of occurrence.
- Iterate over every row
- Initialize an empty string s = “”.
- Keep appending all the elements into the string s.
- Increment the frequency count of string s in the map
- Initialize a result variable for storing the number of pairs such that the row and column are equal
- Iterate over every column
- Initialize an empty string s = “”.
- Keep appending all the elements into the string s.
- Add into the result of the frequency count of s in the map.
- Return the result.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to count the row-column pairsint equalPairs(vector<vector<int> >& grid){ // Initialize a map for mapping all // column with their frequency of // occurrence. unordered_map<string, int> unmap; // Iterate over all rows for (int i = 0; i < grid.size(); i++) { // Initialize an empty string s = "" string s = ""; // Keep appending all the element // into string s for (int j = 0; j < grid[0].size(); j++) { s += to_string(grid[i][j]); s += "*"; } // Increment the frequency count of // string s in map unmap[s]++; } // Initialize a result variable for // storing the number of pair such that // row and column are equal int result = 0; // Iterate over all the columns for (int j = 0; j < grid[0].size(); j++) { // Initialize an empty string s = "" string s = ""; // Keep appending all the element // into string s for (int i = 0; i < grid.size(); i++) { s += to_string(grid[i][j]); s += "*"; } // Add into result of frequency // count of s in map. result += unmap[s]; } // Return the result return result;}// Driver codeint main(){ vector<vector<int> > arr = { { 2, 4, 1, 1 }, { 4, 5, 6, 6 }, { 1, 6, 4, 4 }, { 1, 6, 4, 4 }, }; // Function Call cout << equalPairs(arr); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // Function to count the row-column pairs public static int equalPairs(int grid[][]) { // Initialize a map for mapping all // column with their frequency of // occurrence. HashMap<String, Integer> unmap = new HashMap<String, Integer>(); // Iterate over all rows for (int i = 0; i < grid.length; i++) { // Initialize an empty string s = "" String s = ""; // Keep appending all the element // into string s for (int j = 0; j < grid[0].length; j++) { s += Integer.toString(grid[i][j]); s += "*"; } // Increment the frequency count of // string s in map if (unmap.get(s) == null) { unmap.put(s, 1); } else { unmap.put(s, unmap.get(s) + 1); } } // Initialize a result variable for // storing the number of pair such that // row and column are equal int result = 0; // Iterate over all the columns for (int j = 0; j < grid[0].length; j++) { // Initialize an empty string s = "" String s = ""; // Keep appending all the element // into string s for (int i = 0; i < grid.length; i++) { s += Integer.toString(grid[i][j]); s += "*"; } // Add into result of frequency // count of s in map. result += unmap.get(s); } // Return the result return result; } // Driver Code public static void main(String[] args) { int arr[][] = { { 2, 4, 1, 1 }, { 4, 5, 6, 6 }, { 1, 6, 4, 4 }, { 1, 6, 4, 4 }, }; // Function Call System.out.print(equalPairs(arr)); }}// This code is contributed by Rohit Pradhan |
Python3
# Python3 code to implement the approach# Function to count the row-column pairsdef equalPairs(grid) : # Initialize a map for mapping all # column with their frequency of # occurrence. unmap = {}; # Iterate over all rows for i in range(len(grid)) : # Initialize an empty string s = "" s = ""; # Keep appending all the element # into string s for j in range(len(grid[0])) : s += str(grid[i][j]); s += "*"; if s in unmap : # Increment the frequency count of # string s in map unmap[s] += 1; else : unmap[s] = 1; # Initialize a result variable for # storing the number of pair such that # row and column are equal result = 0; # Iterate over all the columns for j in range(len(grid[0])) : # Initialize an empty string s = "" s = ""; # Keep appending all the element # into string s for i in range(len(grid)) : s += str(grid[i][j]); s += "*"; # Add into result of frequency # count of s in map. result += unmap[s]; # Return the result return result;# Driver codeif __name__ == "__main__" : arr = [ [ 2, 4, 1, 1 ], [ 4, 5, 6, 6 ], [ 1, 6, 4, 4 ], [ 1, 6, 4, 4 ], ]; # Function Call print(equalPairs(arr)); # This code is contributed by AnkThon |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class GFG { // Function to count the row-column pairs static int equalPairs(int[, ] grid, int N, int M) { // Initialize a map for mapping all // column with their frequency of // occurrence. Dictionary<string, int> mp = new Dictionary<string, int>(); // Iterate over all rows for (int i = 0; i < N; i++) { // Initialize an empty string s = "" string s = ""; // Keep appending all the element // into string s for (int j = 0; j < M; j++) { s += grid[i, j].ToString(); s += "*"; } // Increment the frequency count of // string s in map if (mp.ContainsKey(s)) { int val = mp[s]; mp.Remove(s); mp.Add(s, val + 1); } else mp.Add(s, 1); } // Initialize a result variable for // storing the number of pair such that // row and column are equal int result = 0; // Iterate over all the columns for (int j = 0; j < M; j++) { // Initialize an empty string s = "" string s = ""; // Keep appending all the element // into string s for (int i = 0; i < N; i++) { s += grid[i, j].ToString(); s += "*"; } // Add into result of frequency // count of s in map. result += mp[s]; } // Return the result return result; } static void Main() { int[, ] arr = { { 2, 4, 1, 1 }, { 4, 5, 6, 6 }, { 1, 6, 4, 4 }, { 1, 6, 4, 4 }, }; // Function Call Console.Write(equalPairs(arr, 4, 4)); }}// This code is contributed by garg28harsh. |
Javascript
// JavaScript code for the above approach// Function to count the row-column pairsfunction equalPairs(grid){ // Initialize a map for mapping all // column with their frequency of // occurrence. let unmap = new Map(); // Iterate over all rows for (let i = 0; i < grid.length; i++) { // Initialize an empty string s = "" let s = ""; // Keep appending all the element // into string s for (let j = 0; j < grid[0].length; j++) { s += (grid[i][j]).toString(); s += "*"; } // Increment the frequency count of // string s in map if (unmap.has(s)) { unmap.set(s, unmap.get(s) + 1) } else { unmap.set(s, 1) } } // Initialize a result variable for // storing the number of pair such that // row and column are equal let result = 0; // Iterate over all the columns for (let j = 0; j < grid[0].length; j++) { // Initialize an empty string s = "" let s = ""; // Keep appending all the element // into string s for (let i = 0; i < grid.length; i++) { s += grid[i][j].toString(); s += "*"; } // Add into result of frequency // count of s in map. result += unmap.get(s); } // Return the result return result;}// Driver codelet arr = [ [ 2, 4, 1, 1 ], [ 4, 5, 6, 6 ], [ 1, 6, 4, 4 ], [ 1, 6, 4, 4 ],];// Function Callconsole.log(equalPairs(arr));// This code is contributed by Potta Lokesh |
Output
6
Time Complexity: O(N2)
Auxiliary Space: O(N2)
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!
