Sort rows in ascending order followed by columns in descending

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;

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

Run Code

}

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

You can also try this code with Online Java Compiler

Run Code

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²logN).

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

Also, sorting the matrix one more time would take another N²logN.

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

Time Complexity: O(N²logN)

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!