Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement Explanation
3.
Solution Walkthrough
3.1.
C++ Code
3.2.
Output: 
3.3.
Java Code
4.
Time Complexity Analysis
5.
Frequently Asked Questions
5.1.
Can vectors be used instead of arrays?
5.2.
Is there a different way to solve the problem?
5.3.
What is greater<int>() in C++ implementation ?
5.4.
What is the time complexity to traverse a 2D matrix?
5.5.
Can ArrayList be used instead of arrays in java code?
6.
Conclusion
Last Updated: Mar 27, 2024

Sort rows in ascending order followed by columns in descending

Author Manish Kumar
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

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.

Examples:

                    Input: a [3] [3] = { { 4 , 2 , 6 },

                                               { 8 , 9 , 3 },

                                               { 1 , 7 , 5 } }

        

                     Output: 3 8 9

                                 2 5 7

                                 1 4 6

 

                   Input : a [4] [4] = { { 0 , 12 , 1, 6  },

                                                { 9 , -8 , 7 , 11 }, 

                                                { 16 , 2 , -4 , 3 },

                  { 1 , 21 , 4 , 7 }}

         

                     Output : 1 7 9 21

                                   0 4 7 16

                                   -4 2 6 12

                                  -8 1 3 11

Also see,  Rabin Karp Algorithm

Get the tech career you deserve, faster!
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( N2logN).

We would use the transpose function twice, which would take the time 2N2.

Also, sorting the matrix one more time would take another N2logN.

Therefore, the total time would be O(N2logN+N2logN+2N2), the same as O( N2logN).

Time Complexity: O(N2logN)

Space Complexity: O(1)

Frequently Asked Questions

Can vectors be used instead of arrays?

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 !!

 

Please refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. And also, enrol in our courses and refer to the mock test and problems available. Have a look at the interview experiences and interview bundle for placement preparations.

 

 

Please do upvote our blogs if you find them helpful and informative!

Happy learning!

 

Previous article
Sort all even numbers in the Array without changing the order of odd elements
Next article
Sorting Array Except Elements in a Subarray
Live masterclass