Sort the given matrix

Try it on GfG Practice

Given a m x n matrix. The problem is to sort the given matrix in strict order. Here strict order means that the matrix is sorted in a way such that all elements in a row are sorted in increasing order and for row ‘i’, where 1 <= i <= m-1, the first element is greater than or equal to the last element of row 'i-1'.

Examples: 

Input : mat[][] = { {5, 4, 7},
{1, 3, 8},
{2, 9, 6} }
Output : 1 2 3
4 5 6
7 8 9

Input: mat[][] = { {5, 4, 7},
{1, 3, 8} }
Output: 1 3 4
5 7 8

Naive Approach - O(mn Log mn) Time and O(mn) Space

We first store the matrix elements in a m x n sized 1D array, then sort the array and finally copy the elements back to the matrix,

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void sortMatrix(vector<vector<int>>& mat) {
    vector<int> temp;
    
    // Collect all elements in a temporary vector
    for (auto& row : mat) {
        for (int x : row) {
            temp.push_back(x);
        }
    }
    
    // Sort the vector
    sort(temp.begin(), temp.end());
    
    // Put sorted values back into the matrix
    int k = 0;
    for (auto& row : mat) {
        for (int& x : row) {
            x = temp[k++];
        }
    }
}

int main() {
    vector<vector<int>> mat{{5, 4, 7}, {1, 3, 8}, {2, 9, 6}};
    
    sortMatrix(mat);
    
    for (auto& row : mat) {
        for (int x : row) {
            cout << x << " ";
        }
        cout << endl;
    }
    
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args)
    {
        // Initialize the 2D vector with some values
        List<List<Integer> > v
            = new ArrayList<>(Arrays.asList(
                new ArrayList<>(Arrays.asList(5, 4, 7)),
                new ArrayList<>(Arrays.asList(1, 3, 8)),
                new ArrayList<>(Arrays.asList(2, 9, 6))));

        int n = v.size();
        List<Integer> x = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                x.add(v.get(i).get(j));
            }
        }
        Collections.sort(x);
        int k = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                v.get(i).set(j, x.get(k++));
            }
        }

        System.out.println("Sorted Matrix Will be:");
        for (List<Integer> row : v) {
            for (int num : row) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }
}

# Python program for the above approach
# driver code
v = [[5,4,7], [1,3,8], [2,9,6]]
n = len(v)

x = []
for i in range(n):
    for j in range(n):
        x.append(v[i][j])

x.sort()
k = 0
for i in range(n):
    for j in range(n):
        v[i][j] = x[k]
        k += 1

print("Sorted Matrix will be: ")
for i in range(n):
    for j in range(n):
        print(v[i][j], end=" ")
    print("")

# THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL(KIRTIAGARWAL23121999)

// C# implementation to
// sort the given matrix
using System;
 
class GFG {
    // Driver code
    public static void Main()
    {
        int[, ] mat = { { 5, 4, 7 },
                        { 1, 3, 8 },
                        { 2, 9, 6 } };
        int n = 3;
        int temp = 0;
        int[] x = new int[n*n];
        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                x[temp++] = mat[i,j];
            }
        }
 
        Array.Sort(x);
        temp = 0;
        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                mat[i,j] = x[temp++];
            }
        }
        Console.WriteLine("Sorted Matrix will be : ");
        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                Console.Write(mat[i,j] + " ");
            }
            Console.WriteLine("");
        }
    }
}

// JavaScript program for the above approach
let v = [[5,4,7], [1,3,8], [2,9,6]];
let n = v.length;
let x = [];

for(let i = 0; i<n; i++){
    for(let j = 0; j<n; j++){
        x.push(v[i][j]);
    }
}

x.sort((a, b) => a - b);
let k = 0;
for(let i = 0; i<n; i++){
    for(let j = 0; j<n; j++){
        v[i][j] = x[k++];
    }
}
document.write("Sorted Matrix will be : <br>");
for(let i = 0; i<n; i++){
    for(let j = 0; j<n; j++){
        document.write(v[i][j] + " ");
    }
    document.write("<br>");
}
// this code is contributed by Yash Agarwal(yashagarwal2852002)

Sorted Matrix Will be:
1 2 3 
4 5 6 
7 8 9 

Time Complexity: O(mnlog₂mn)
Auxiliary Space: O(mn) for the auxiliary 1D array.

Treating the Given Array as 1D Array - O(1) Space

The idea is to treat the 2D-Array as a 1D-Array to sort the matrix without using extra space. This can also be explained with the help of the following example. 

For Example:

There is a 2*2 Matrix with 4 elements,
The idea is to treat the elements of the matrix
as 1D Array of 4 elements.
1 2
3 4

As In the given matrix each element can be accessed as -
1st Element - 0th Row, 0th Col
2nd Element - 0th Row, 1st Col
3rd Element - 1st Row, 0th Col
4th Element - 1st Row, 1st Col 

So, for Accessing i^th element of the matrix, the relation can be defined as:

I^th Element of the Matrix = Mat[ i / n ][ i % n ]  
Where n is number of columns

Please refer Sort the given Matrix | Memory Efficient Approach for implementation