Given a n 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 <= n-1, the first element of row ‘i’ 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
Brute Force Using Extra O(n*m) Space:
The Approach:
here in this approach we store the all the element in a vector then sort it we need to fill that matrix again.
C++
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
vector<vector< int >>v{{5, 4, 7},{1, 3, 8},{2, 9, 6}};
int n=v.size();
vector< int >x;
for ( int i=0;i<n;i++){
for ( int j=0;j<n;j++){
x.push_back(v[i][j]);
}
}
sort(x.begin(),x.end());
int k=0;
for ( int i=0;i<n;i++){
for ( int j=0;j<n;j++){
v[i][j]=x[k++];
}
}
cout<< "Sorted Matrix Will be:" <<endl;
for ( auto it:v){
for ( auto vt:it){
cout<<vt<< " " ;
}cout<<endl;
}
return 0;
}
|
Java
import java.util.*;
public class Main {
public static void main(String[] args)
{
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();
}
}
}
|
Python3
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 ("")
|
C#
using System;
class GFG {
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
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>" );
}
|
Output
Sorted Matrix Will be:
1 2 3
4 5 6
7 8 9
Time Complexity: O(n2log2n), O(n*n) for traversing, and O(n2log2n) for sorting the vector x, which has a size of n2. So overall time complexity is O(n2log2n).
Auxiliary Space: O(n*n), For vector.
Approach: Create a temp[] array of size n^2. Starting with the first row one by one copy the elements of the given matrix into temp[]. Sort temp[]. Now one by one copy the elements of temp[] back to the given matrix.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
void sortMat( int mat[SIZE][SIZE], int n)
{
int temp[n * n];
int k = 0;
for ( int i = 0; i < n; i++)
for ( int j = 0; j < n; j++)
temp[k++] = mat[i][j];
sort(temp, temp + k);
k = 0;
for ( int i = 0; i < n; i++)
for ( int j = 0; j < n; j++)
mat[i][j] = temp[k++];
}
void printMat( int mat[SIZE][SIZE], int n)
{
for ( int i = 0; i < n; i++) {
for ( int j = 0; j < n; j++)
cout << mat[i][j] << " " ;
cout << endl;
}
}
int main()
{
int mat[SIZE][SIZE] = { { 5, 4, 7 },
{ 1, 3, 8 },
{ 2, 9, 6 } };
int n = 3;
cout << "Original Matrix:\n" ;
printMat(mat, n);
sortMat(mat, n);
cout << "\nMatrix After Sorting:\n" ;
printMat(mat, n);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
static int SIZE = 10 ;
static void sortMat( int mat[][], int n)
{
int temp[] = new int [n * n];
int k = 0 ;
for ( int i = 0 ; i < n; i++)
for ( int j = 0 ; j < n; j++)
temp[k++] = mat[i][j];
Arrays.sort(temp);
k = 0 ;
for ( int i = 0 ; i < n; i++)
for ( int j = 0 ; j < n; j++)
mat[i][j] = temp[k++];
}
static void printMat( int mat[][], int n)
{
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < n; j++)
System.out.print( mat[i][j] + " " );
System.out.println();
}
}
public static void main(String args[])
{
int mat[][] = { { 5 , 4 , 7 },
{ 1 , 3 , 8 },
{ 2 , 9 , 6 } };
int n = 3 ;
System.out.println( "Original Matrix:" );
printMat(mat, n);
sortMat(mat, n);
System.out.println( "Matrix After Sorting:" );
printMat(mat, n);
}
}
|
Python3
SIZE = 10
def sortMat(mat, n) :
temp = [ 0 ] * (n * n)
k = 0
for i in range ( 0 , n) :
for j in range ( 0 , n) :
temp[k] = mat[i][j]
k + = 1
temp.sort()
k = 0
for i in range ( 0 , n) :
for j in range ( 0 , n) :
mat[i][j] = temp[k]
k + = 1
def printMat(mat, n) :
for i in range ( 0 , n) :
for j in range ( 0 , n ) :
print (mat[i][j] , end = " " )
print ()
mat = [ [ 5 , 4 , 7 ],
[ 1 , 3 , 8 ],
[ 2 , 9 , 6 ] ]
n = 3
print ( "Original Matrix:" )
printMat(mat, n)
sortMat(mat, n)
print ( "\nMatrix After Sorting:" )
printMat(mat, n)
|
C#
using System;
class GFG {
static int SIZE = 10;
static void sortMat( int [, ] mat, int n)
{
int [] temp = new int [n * n];
int k = 0;
for ( int i = 0; i < n; i++)
for ( int j = 0; j < n; j++)
temp[k++] = mat[i, j];
Array.Sort(temp);
k = 0;
for ( int i = 0; i < n; i++)
for ( int j = 0; j < n; j++)
mat[i, j] = temp[k++];
}
static void printMat( int [, ] mat, int n)
{
for ( int i = 0; i < n; i++) {
for ( int j = 0; j < n; j++)
Console.Write(mat[i, j] + " " );
Console.WriteLine();
}
}
public static void Main()
{
int [, ] mat = { { 5, 4, 7 },
{ 1, 3, 8 },
{ 2, 9, 6 } };
int n = 3;
Console.WriteLine( "Original Matrix:" );
printMat(mat, n);
sortMat(mat, n);
Console.WriteLine( "Matrix After Sorting:" );
printMat(mat, n);
}
}
|
Javascript
<script>
let SIZE = 10
function sortMat(mat, n)
{
let temp = new Array(n * n);
let k = 0;
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
temp[k++] = mat[i][j];
temp.sort((a, b) => a - b);
k = 0;
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
mat[i][j] = temp[k++];
}
function printMat(mat, n)
{
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++)
document.write( mat[i][j] + " " );
document.write( "<br>" );
}
}
let mat = [ [ 5, 4, 7 ],
[ 1, 3, 8 ],
[ 2, 9, 6 ] ];
let n = 3;
document.write( "Original Matrix: " + "<br>" );
printMat(mat, n);
sortMat(mat, n);
document.write( "<br>" );
document.write( "\nMatrix After Sorting: " + "<br>" );
printMat(mat, n);
</script>
|
Output
Original Matrix:
5 4 7
1 3 8
2 9 6
Matrix After Sorting:
1 2 3
4 5 6
7 8 9
Time Complexity: O(n2log2n).
Auxiliary Space: O(n2), since n * n extra space has been taken.
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 geeks!