Given a n x n matrix. The problem is to sort the given matrix in strict order. Here strict order means that 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, 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
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.
Ā
Python3
# Python3 implementation to sort# the given matrixĀ
SIZE = 10Ā
# Function to sort the given matrixdef sortMat(mat, n) :Ā Ā Ā Ā Ā Ā Ā Ā Ā # Temporary matrix of size n^2Ā Ā Ā Ā temp = [0] * (n * n)Ā Ā Ā Ā k = 0Ā
Ā Ā Ā Ā # Copy the elements of matrixĀ Ā Ā Ā Ā # one by one into temp[]Ā Ā Ā Ā for i in range(0, n) :Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for j in range(0, n) :Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā temp[k] = mat[i][j]Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā k += 1Ā
Ā Ā Ā Ā # sort temp[]Ā Ā Ā Ā temp.sort()Ā Ā Ā Ā Ā Ā Ā Ā Ā # copy the elements of temp[] Ā Ā Ā Ā # one by one in mat[][]Ā Ā Ā Ā k = 0Ā Ā Ā Ā Ā Ā Ā Ā Ā for i in range(0, n) :Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for j in range(0, n) :Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā mat[i][j] = temp[k]Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā k += 1Ā
Ā
# Function to print the given matrixdef printMat(mat, n) :Ā Ā Ā Ā Ā Ā Ā Ā Ā for i in range(0, n) :Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for j in range( 0, n ) :Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā print(mat[i][j] , end = " ")Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā print(" ")Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # Driver program to test abovemat = [ [ 5, 4, 7 ],Ā Ā Ā Ā Ā Ā Ā Ā [ 1, 3, 8 ],Ā Ā Ā Ā Ā Ā Ā Ā [ 2, 9, 6 ] ]n = 3Ā
print( "Original Matrix:")printMat(mat, n)Ā
sortMat(mat, n)Ā
print("Matrix After Sorting:")printMat(mat, n)Ā
Ā
# This code is contributed by Nikita Tiwari. |
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).
Ā
To sort the matrix in the required strict order, we can use a different approach. One possibility is to flatten the matrix into a single list, sort the list, and then reshape the list into the original matrix shape.
Here is an example of how this can be done:
Python3
import numpy as npĀ
mat = [[5, 4, 7],Ā Ā Ā Ā Ā Ā Ā [1, 3, 8],Ā Ā Ā Ā Ā Ā Ā [2, 9, 6]]Ā
# flatten the matrix into a single listflat_list = [item for sublist in mat for item in sublist]Ā
# sort the listflat_list.sort()Ā
# reshape the list into the original matrix shapemat = np.array(flat_list).reshape((3, 3))Ā
# print the sorted matrixfor row in mat:Ā Ā Ā Ā print(row) |
This will print the following matrix:
[1 2 3]
[4 5 6]
[7 8 9]
Ā Time complexity: O(N * log N), where N is the number of elements in the matrix.Ā
Ā Auxiliary space: O(N), as it requires an additional list to store the flattened matrix.
Please refer complete article on Sort the given matrix for more details!
Approach#3: Using heapq
Another way to sort the matrix is to use a heap. We can create a min-heap and then extract the minimum element repeatedly to create a sorted list, which can then be reshaped back into a matrix.
Algorithm
1. Create a min-heap and insert all elements of the matrix into it.
2. Extract the minimum element from the heap repeatedly to create a sorted list.
3. Reshape the sorted list back into a matrix.
Python3
import heapqĀ
def sort_matrix(mat):Ā Ā Ā Ā # Step 1: Create a min-heap and insert all elements of the matrix into it.Ā Ā Ā Ā heap = []Ā Ā Ā Ā for row in mat:Ā Ā Ā Ā Ā Ā Ā Ā for num in row:Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā heapq.heappush(heap, num)Ā
Ā Ā Ā Ā # Step 2: Extract the minimum element from the heap repeatedly to create a sorted list.Ā Ā Ā Ā sorted_list = []Ā Ā Ā Ā while heap:Ā Ā Ā Ā Ā Ā Ā Ā sorted_list.append(heapq.heappop(heap))Ā
Ā Ā Ā Ā # Step 3: Reshape the sorted list back into a matrix.Ā Ā Ā Ā n_rows = len(mat)Ā Ā Ā Ā n_cols = len(mat[0])Ā Ā Ā Ā sorted_mat = [sorted_list[i:i+n_cols] for i in range(0, len(sorted_list), n_cols)]Ā
Ā Ā Ā Ā return sorted_matĀ
# Example usage:mat = [[5, 4, 7], [1, 3, 8], [2, 9, 6]]sorted_mat = sort_matrix(mat)for row in sorted_mat:Ā Ā Ā Ā print(row) |
[1, 2, 3] [4, 5, 6] [7, 8, 9]
Time Complexity: O(n log n), where n is the total number of elements in the matrix. This is because inserting n elements into the heap takes O(n log n) time, and extracting n elements from the heap also takes O(n log n) time.
Space Complexity: O(n), where n is the total number
Youāll access excellent video content by our CEO, Sandeep Jain, tackle common interview questions, and engage in real-time coding contests covering various DSA topics. Weāre here to prepare you thoroughly for online assessments and interviews.
Ready to dive in? Explore our free demo content and join our DSA course, trusted by over 100,000neveropen! Whether itās DSA in C++, Java, Python, or JavaScript weāve got you covered. Letās embark on this exciting journey together!
