Print elements in sorted order using row-column wise sorted matrix

Problem Statement

Given an m x n matrix where each row and each column is sorted in ascending order, print all elements of the matrix in sorted order.

Example:

• Input: matrix = [[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]

Approach 1: Brute Force (Flatten and Sort)

Intuition

Copy all elements to a 1D array and sort it.

Algorithm

1. Traverse the matrix and copy all elements to an array
2. Sort the array
3. Return/print the sorted array

import java.util.*;

public class Solution {
    public int[] sortedMatrixBrute(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[] result = new int[m * n];
        int index = 0;
        
        // Flatten the matrix
        for (int[] row : matrix) {
            for (int val : row) {
                result[index++] = val;
            }
        }
        
        // Sort and return
        Arrays.sort(result);
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(mnlog(m*n)) - Sorting all elements
• Space Complexity: O(m*n) - Storing all elements

Approach 2: Min-Heap / Merge K Sorted Lists (Optimal)

Intuition

This is similar to merging k sorted lists. Use a min-heap to always extract the smallest element among all row heads. After extracting, push the next element from the same row.

Algorithm

1. Initialize a min-heap with the first element of each row
2. While heap is not empty:
   • Extract minimum element and add to result
   • Push the next element from the same row (if exists)
3. Return the result

import java.util.*;

public class Solution {
    public int[] sortedMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[] result = new int[m * n];
        int index = 0;
        
        // Min-heap: {value, row, col}
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        
        // Initialize heap with first element of each row
        for (int i = 0; i < m; i++) {
            minHeap.offer(new int[]{matrix[i][0], i, 0});
        }
        
        // Extract elements in sorted order
        while (!minHeap.isEmpty()) {
            int[] curr = minHeap.poll();
            int val = curr[0], row = curr[1], col = curr[2];
            
            result[index++] = val;
            
            // Push next element from same row
            if (col + 1 < n) {
                minHeap.offer(new int[]{matrix[row][col + 1], row, col + 1});
            }
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(mnlog(m)) - Each of m*n elements is pushed and popped from heap of size m
• Space Complexity: O(m) - Heap stores at most m elements

Approach 3: Young Tableau Property

Intuition

Repeatedly extract the minimum element (always at top-left after restructuring). After extraction, restructure the matrix to maintain sorted property.

Complexity Analysis

• Time Complexity: O(mn(m+n)) - Each extraction takes O(m+n)
• Space Complexity: O(m*n) - Copy of matrix

Approach 4: Merge Sort Style (Divide and Conquer)

Intuition

Merge rows pairwise, similar to merge sort, until we have one sorted array.

Complexity Analysis

• Time Complexity: O(mnlog(m)) - log(m) merge levels, each processing m*n elements
• Space Complexity: O(m*n) - Storing merged results

Comparison of Approaches

| Approach | Time | Space | When to Use | |----------|------|-------|-------------| | Brute Force | O(mnlog(mn)) | O(mn) | Simple, small matrices | | Min-Heap | O(mnlog(m)) | O(m) | Best for large matrices | | Young Tableau | O(mn(m+n)) | O(mn) | Educational purposes | | Merge Sort | O(mnlog(m)) | O(mn) | When heap not available |

Key Takeaways

1. Min-heap approach is optimal for merging k sorted lists/rows
2. The heap always maintains the smallest unprocessed element at top
3. This is the classic "Merge K Sorted Lists" problem applied to matrix rows
4. Young Tableau is an interesting data structure but not optimal here
5. The merge sort approach has same time complexity as heap but uses more space
6. This technique is fundamental for external sorting and streaming data