Sorted Matrix

Problem

Given an NxN matrix Mat. Sort all elements of the matrix.

Examples:

Example 1:

Input:
N=4
Mat=[[10,20,30,40],
[15,25,35,45] 
[27,29,37,48] 
[32,33,39,50]]
Output:
10 15 20 25 
27 29 30 32
33 35 37 39
40 45 48 50
Explanation:
Sorting the matrix gives this result.

Example 2:

Input:
N=3
Mat=[[1,5,3],[2,8,7],[4,6,9]]
Output:
1 2 3 
4 5 6
7 8 9
Explanation:
Sorting the matrix gives this result.

Your task:

You don't need to read input or print anything. Your task is to complete the function sortedMatrix() which takes the integer N and the matrix Mat as input parameters and returns the sorted matrix.

• Expected Time Complexity: $O(N^2LogN)$
• Expected Auxiliary Space: $O(N^2)$

Constraints:

• $1<=N<=1000$
• $1<=Mat[i][j]<=10^5$

Solution

Python

def sortedMatrix(self,N,Mat):
    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
    return Mat

Java

int[][] sortedMatrix(int N, int Mat[][]) {
    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];
            k++;
        }
    }
    Arrays.sort(temp);
    k = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            Mat[i][j] = temp[k];
            k++;
        }
    }
    return Mat;
}

C++

vector<vector<int>> sortedMatrix(int N, vector<vector<int>> Mat) {
    vector<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.begin(), temp.end());
    k = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            Mat[i][j] = temp[k++];
        }
    }
    return Mat;
}

C

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int** sortedMatrix(int N, int **Mat) {
    int *temp = (int *)malloc(N * N * sizeof(int));
    int k = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[k++] = Mat[i][j];
        }
    }
    qsort(temp, N * N, sizeof(int), compare);
    k = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            Mat[i][j] = temp[k++];
        }
    }
    free(temp);
    return Mat;
}

• Time Complexity: $O(N^2LogN)$
• Auxiliary Space: $O(N^2)$