Hey Ninja! Do you know a lot of companies ask matrix-related questions in coding interviews? Moreover, many advanced DSA topics, such as Dynamic Programming, use 2D matrices. Therefore it becomes critical to have in-depth knowledge of matrices. This blog will go through a problem based on sorting involving matrices. We will cover various approaches to solving the problem and analysing it thoroughly. So without further ado, let's jump into the problem statement.

Problem Statement Explanation

In this problem, we need to first sort the rows of the 2-D matrix in ascending order, then sort columns in descending order. The dimensions will be of (n*n) type.

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Solution Walkthrough

Step 1: In the driver code, take the dimension 'n' input. Initialise the matrix of size n*n and take input using a for loop.

Step 2: Make two functions, rowSort() and transpose(), pass the matrix as an argument. Here, we would be using call-by-reference to save on space.

Step 3: In the rowSort() function, initiate a for loop and call the inbuilt sort() function for sorting each row. Keep a flag to indicate whether to sort in ascending or descending order.

Step 4: Complete the transpose() function definition and use nested for loop and swap to achieve this.

Step 5: Again, call the rowSort() function; this time flag would indicate descending order sorting.

Step 6: Call the transpose() function to revert to the original position.

Step 7: Print the matrix.

C++ Code

//C++ Code
#include<bits/stdc++.h>
using namespace std;
//Transpose function to which works
// by swapping elements according to given logic
void transpose(vector<vector<int>>&matrix,int size)
{
for(int i=0;i<size;i++)
{
for(int j=i+1;j<size;j++)
{
swap(matrix[i][j],matrix[j][i]);
}
}
}
//row sorting function based on boolean flag
void rowSort(vector<vector<int>>&matrix,int n,bool flag)
{
for(int i=0;i<n;i++)
{
if(flag)
sort(matrix[i].begin(),matrix[i].end());
else
sort(matrix[i].begin(),matrix[i].end(), greater<int>());
}
}
int main()
{
cout<<"Enter the matrix edge length: ";
int n;
cin>>n;
cout<<endl;
vector<vector<int>>matrix(n,vector<int>(n));
//Taking input for the matrix
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>matrix[i][j];
}
}
cout<<"-----------\n";
rowSort(matrix,n,true);
transpose(matrix,n);
rowSort(matrix,n,false);
transpose(matrix,n);
//Print the contents of the matrix
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
return 0;

}

Output:

Java Code

//Java Code
import java.util.*;
class Main
{
// function to find transpose of the matrix
static void change(Integer matrix[][], int size)
{
for (int i = 0; i < size; i++)
for (int j = i + 1; j < size; j++)
{
//Swapping algorithm applied
int help = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = help;
}
}
//function to sort row wise with the help boolean flag
static void rowSort(Integer matrix[][], int n,
boolean flag)
{
for (int i = 0; i < n; i++)
{
if (flag)
Arrays.sort(matrix[i]);//Using built in sort method
else
Arrays.sort(matrix[i],Collections.reverseOrder());
}
}
// function to sort the matrix row-wise
// and column-wise
static void helper(Integer matrix[][],int n)
{
//Sorting row wise and then taking transpose
//Repeating this step twice
rowSort(matrix, n, true);
change(matrix, n);
rowSort(matrix, n, false);
change(matrix, n);
}
// Driver code
public static void main (String[] args)
{
int n = 4;
Integer matrix[][] = {{-1, 2, -3,12},
{10, 11, 17,6},
{15, -2, 4,-9},
{12, -8, 9, 6}};
System.out.print("Input Matrix:\n");
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
System.out.print(matrix[i][j] + " ");
System.out.println();
}
helper(matrix, n);
System.out.print("\nOutput :\n");
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
System.out.print(matrix[i][j] + " ");
System.out.println();
}
}
}

Output :

Time Complexity Analysis

Here each row contains 'n' elements. Therefore the time to sort one row is n*logn. Now we have 'n' rows. Thus, the time taken to sort the matrix would be n*nlogn, i.e. O( N^{2}logN).

We would use the transpose function twice, which would take the time 2N^{2}.

Also, sorting the matrix one more time would take another N^{2}logN.

Therefore, the total time would be O(N^{2}logN+N^{2}logN+2N^{2}), the same as O( N^{2}logN).

Yes, you can use vectors to implement your code. It would help to allocate matrix sizes in runtime dynamically.

Is there a different way to solve the problem?

You can solve it by making a custom columnSort() function, which would sort the matrix column-wise. Using row sort and column sort, this problem can be tackled efficiently.

What is greater<int>() in C++ implementation ?

The comparator argument tells the compiler to sort in descending order. We could have also defined a custom comparator function to achieve this.

What is the time complexity to traverse a 2D matrix?

The time taken is O(n*n).

Can ArrayList be used instead of arrays in java code?

You can use ArrayList as well.

Conclusion

In this blog, you learned how to deal with a 2-D matrix and the concepts of sorting a matrix's rows and columns. You also learned about the transpose of a matrix and its implementation and usage. A thorough analysis of time complexity was also discussed.

To learn more, check out the excellent coding content on the Coding Ninjas Website. Happy Coding !!