Sorting elements in a matrix that is already sorted both row-wise and column-wise is an interesting problem often encountered in coding interviews. A row-column wise sorted matrix is a matrix in which each row is sorted from left to right, and each column is sorted from top to bottom. The challenge is to efficiently print all the elements of this matrix in a fully sorted order without explicitly sorting them.
In this blog, we’ll explore different approaches to solve this problem, focusing on an optimal method that leverages a min-heap to achieve efficient sorting of the elements.
Problem Statement
Given an n x n matrix where each row and each column is sorted in non-decreasing order, print all the elements of the matrix in sorted order.
Example:
Input:
matrix = [
[10, 20, 30, 40],
[15, 25, 35, 45],
[24, 29, 37, 48],
[32, 33, 39, 50]
]
Output: 10 15 20 24 25 29 30 32 33 35 37 39 40 45 48 50
How to Print Elements in Sorted Order Using a Row-Column Wise Sorted Matrix
Approaches to Solve the Problem
1. Naive Approach: Flatten and Sort
The most intuitive way to solve this problem is to flatten the matrix into a one-dimensional array and then sort it.
Steps:
- Convert the 2D matrix into a 1D array.
- Sort the array.
- Print the sorted elements.
Code Example (Naive Approach):
def printSorted(matrix):
# Flatten the matrix into a list
flat_list = [element for row in matrix for element in row]
# Sort the list
flat_list.sort()
# Print the sorted elements
for element in flat_list:
print(element, end=" ")
# Example usage
matrix = [
[10, 20, 30, 40],
[15, 25, 35, 45],
[24, 29, 37, 48],
[32, 33, 39, 50]
]
print("Sorted elements are:")
printSorted(matrix)Time Complexity: O(n² log n²) = O(n² log n), where n is the number of rows or columns in the matrix.
Space Complexity: O(n²), because we are storing the matrix in a flattened list.
While this method works, it is inefficient for large matrices since sorting a large flattened array can be computationally expensive.
2. Optimal Approach: Using Min-Heap
Given that both the rows and columns of the matrix are sorted, we can use a min-heap (or priority queue) to efficiently extract the smallest element and print the elements in sorted order.
Key Idea:
- Insert the smallest element (the top-left corner) into the heap.
- Extract the minimum element from the heap, and insert its right neighbor and bottom neighbor (if they exist).
- Repeat the process until all elements have been printed in sorted order.
This approach leverages the fact that the matrix is partially sorted both row-wise and column-wise, allowing us to minimize the number of comparisons.
Steps:
- Create a min-heap and insert the first element of the matrix (matrix[0][0]) along with its coordinates.
- Extract the minimum element from the heap, print it, and then insert its right neighbor (matrix[i][j+1]) and bottom neighbor (matrix[i+1][j]) into the heap.
- Use a boolean array or set to track which elements have already been added to the heap to avoid duplicates.
- Repeat the process until the heap is empty.
Code Example (Min-Heap Approach):
import heapq
def printSorted(matrix):
n = len(matrix)
min_heap = []
visited = [[False] * n for _ in range(n)]
# Insert the first element along with its position into the heap
heapq.heappush(min_heap, (matrix[0][0], 0, 0))
visited[0][0] = True
while min_heap:
# Extract the minimum element from the heap
val, i, j = heapq.heappop(min_heap)
print(val, end=" ")
# Insert the right neighbor into the heap if it hasn't been added yet
if j + 1 < n and not visited[i][j + 1]:
heapq.heappush(min_heap, (matrix[i][j + 1], i, j + 1))
visited[i][j + 1] = True
# Insert the bottom neighbor into the heap if it hasn't been added yet
if i + 1 < n and not visited[i + 1][j]:
heapq.heappush(min_heap, (matrix[i + 1][j], i + 1, j))
visited[i + 1][j] = True
# Example usage
matrix = [
[10, 20, 30, 40],
[15, 25, 35, 45],
[24, 29, 37, 48],
[32, 33, 39, 50]
]
print("Sorted elements are:")
printSorted(matrix)Explanation:
- heapq.heappush(min_heap, (value, i, j)) inserts the element
valuealong with its position(i, j)into the min-heap. - heapq.heappop(min_heap) extracts the smallest element from the min-heap.
- We continue pushing the right and bottom neighbors of the extracted element into the heap, as long as they haven’t already been visited.
Time Complexity: O(n² log n), where n is the size of the matrix (assuming an n x n matrix). This is because each element is inserted and extracted from the heap, and heap operations take O(log n) time.
Space Complexity: O(n²), due to the space required for the heap and the visited array.
Comparison of Approaches
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Flatten and Sort (Naive) | O(n² log n²) | O(n²) |
| Min-Heap (Optimal) | O(n² log n) | O(n²) |
The min-heap approach is significantly more efficient than the naive flatten and sort approach because it takes advantage of the partially sorted nature of the matrix.
When dealing with a matrix that is sorted both row-wise and column-wise, a min-heap provides an efficient way to print all elements in sorted order. The naive approach of flattening and sorting works, but for larger matrices, using a min-heap ensures that the solution is optimal, both in terms of time and space complexity.
If you’re preparing for coding interviews or competitive programming, mastering the min-heap approach to this problem is essential. It demonstrates your ability to solve problems efficiently using data structures and algorithms.
Call-to-Action
Now that you’ve learned how to print elements in sorted order from a row-column wise sorted matrix using a min-heap, try practicing this approach on coding platforms like LeetCode or GeeksforGeeks. For more coding tutorials, algorithms, and data structure guides, subscribe to our newsletter!
Frequently Asked Questions
- Can this method work for unsorted matrices?
- No, this method leverages the fact that the matrix is sorted both row-wise and column-wise. For unsorted matrices, you’d need a different approach.
- What if the matrix is not square (n x n)?
- The min-heap approach works for non-square matrices as well, as long as the matrix is sorted row-wise and column-wise.
- Why is the heap approach more efficient?
- The heap approach only inserts the smallest elements into the heap and maintains the order using a priority queue, reducing the number of comparisons compared to flattening and sorting.
- Where can I practice problems like this?
- You can practice this problem on platforms like LeetCode, GeeksforGeeks, and Codeforces.
This blog covers how to print elements in sorted order using a row-column wise sorted matrix, including both naive and optimal approaches, with a focus on efficiency and clarity.
Here are some related outbound links for the topic How to Print Elements in Sorted Order Using a Row-Column Wise Sorted Matrix
- LeetCode – Kth Smallest Element in a Sorted Matrix:
LeetCode Problem: Kth Smallest Element in a Sorted Matrix
This problem is closely related to printing sorted elements from a matrix using an efficient heap-based approach. - GeeksforGeeks – Print Elements in Sorted Order from Row-Column Wise Sorted Matrix:
GeeksforGeeks: Print Elements in Sorted Order from Row-Column Wise Sorted Matrix
A detailed explanation of solving the problem using a min-heap. - Brilliant – Min Heap Data Structure:
Brilliant: Min Heap Data Structure
Learn more about min-heaps, an essential data structure for efficiently solving matrix sorting problems. - Programiz – Python Heaps (Priority Queue):
Programiz: Python Heaps (Priority Queue)
This resource explains how to use Python’s heapq module, which is useful for implementing the optimal solution.
Read More …
Array Sorting: Comprehensive Guide, Techniques, and LeetCode Solutions – https://kamleshsingad.com/wp-admin/post.php?post=5110&action=edit
Bulb Switcher III: A Comprehensive Guide and Solution – https://kamleshsingad.com/wp-admin/post.php?post=5096&action=edit
Minimize the Maximum Difference Between Heights – An Efficient Solution and Approach – https://kamleshsingad.com/wp-admin/post.php?post=5115&action=edit
