C++ Program To Print All Elements In Sorted Order From Row And Column Wise Sorted Matrix

When working with structured data, you often encounter matrices where elements exhibit specific ordering properties. A common and interesting scenario is a matrix where each row is sorted in ascending order, and each column is also sorted in ascending order. Retrieving all elements from such a matrix in a globally sorted order requires a thoughtful approach beyond simple traversal.

In this article, you will learn how to efficiently print all elements from a row and column-wise sorted matrix in ascending order. We will explore different methods, including a brute-force approach and a more optimized solution using a min-heap.

Problem Statement

Consider an N x M matrix where every row is sorted from left to right, and every column is sorted from top to bottom. The task is to extract and print all elements of this matrix in a single, globally sorted sequence. This problem is significant because a simple row-by-row or column-by-column traversal will not necessarily yield a sorted output, necessitating a more sophisticated algorithm.

Example

Let's illustrate with a sample input and its desired output:

Input Matrix:

10 20 30 40
15 25 35 45
27 29 37 48
32 33 39 50

Notice how each row (e.g., 10 20 30 40) and each column (e.g., 10 15 27 32) is sorted.

Desired Output:

10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50

Background & Knowledge Prerequisites

To understand the solutions presented, a basic grasp of the following C++ concepts is helpful:

• Arrays and Vectors: How to declare, initialize, and access elements in multi-dimensional arrays or std::vector of std::vector.
• Standard Library Functions: Familiarity with std::sort for sorting containers.
• Priority Queues (Min-Heap): Understanding how a std::priority_queue works, particularly as a min-heap, and its operations (push, pop, top).
• Custom Comparators: For storing custom objects in a priority queue.

Use Cases or Case Studies

This problem and its solution are applicable in various scenarios where data is inherently structured and sorted:

• Merging Database Query Results: When individual database queries return sorted results (e.g., by time or ID) from different partitions, and you need to merge them into a single, consolidated sorted list.
• Sensor Data Fusion: In IoT applications, if multiple sensors collect time-series data, and each sensor's data stream is sorted by timestamp, you might need to combine them all into one globally sorted stream.
• Multi-Dimensional Search Optimization: In certain search algorithms or data structures, maintaining sorted properties across multiple dimensions can help optimize retrieval of elements in a specific order.
• Financial Data Aggregation: Aggregating sorted transaction logs from various accounts or markets into a single, chronologically ordered sequence.
• Game Leaderboards: Merging sorted score lists from different game servers or regions to create a global leaderboard.

Solution Approaches

We will explore two primary approaches to solve this problem: a straightforward brute-force method and a more efficient approach leveraging a min-heap.

Approach 1: Brute Force (Copy All and Sort)

This is the simplest approach to implement. It involves copying all elements from the 2D matrix into a 1D data structure (like a std::vector) and then sorting that 1D structure.

• Summary: Extract all elements into a temporary one-dimensional container and apply a standard sorting algorithm.
• Time Complexity: O(N*M log(N*M)) due to sorting N*M elements.
• Space Complexity: O(N*M) to store all elements in the temporary container.

Code Example:

// Brute Force Print Sorted Matrix Elements
#include <iostream>
#include <vector>
#include <algorithm> // For std::sort

int main() {
    // Step 1: Define the matrix
    std::vector<std::vector<int>> matrix = {
        {10, 20, 30, 40},
        {15, 25, 35, 45},
        {27, 29, 37, 48},
        {32, 33, 39, 50}
    };

    // Step 2: Create a 1D vector to store all elements
    std::vector<int> allElements;
    int R = matrix.size();
    int C = matrix[0].size();

    // Step 3: Copy all elements from the matrix to the 1D vector
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            allElements.push_back(matrix[i][j]);
        }
    }

    // Step 4: Sort the 1D vector
    std::sort(allElements.begin(), allElements.end());

    // Step 5: Print the sorted elements
    std::cout << "Sorted elements (Brute Force):" << std::endl;
    for (int element : allElements) {
        std::cout << element << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

Sample Output:

Sorted elements (Brute Force):
10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50

Stepwise Explanation:

1. Initialize a sample matrix.
2. Declare an empty std::vector called allElements.
3. Iterate through each row and column of the matrix.
4. For each element encountered, add it to the allElements vector.
5. After copying all elements, use std::sort() to sort allElements in ascending order.
6. Finally, print each element from the sorted allElements vector.

Approach 2: Using a Min-Heap (Priority Queue)

This approach is more efficient, particularly when the matrix is large, as it avoids storing all elements in a sorted intermediate array. It leverages the property that both rows and columns are sorted, similar to the "merge k sorted lists" problem. A min-heap (std::priority_queue) is used to efficiently find the minimum element among the current candidates from each row.

• Summary: Initialize a min-heap with the first element from each row. Continuously extract the minimum element, print it, and then add the next element from the *same row* into the heap.
• Time Complexity: O(N*M log N), where N is the number of rows. Each of the N*M elements is inserted and extracted from a heap that can hold up to N elements.
• Space Complexity: O(N) to store elements in the min-heap.

Code Example:

// Min-Heap Print Sorted Matrix Elements
#include <iostream>
#include <vector>
#include <queue> // For std::priority_queue

// Structure to hold element value, its row, and column index
struct Element {
    int value;
    int row;
    int col;

    // Custom comparator for min-heap (smallest value on top)
    bool operator>(const Element& other) const {
        return value > other.value;
    }
};

int main() {
    // Step 1: Define the matrix
    std::vector<std::vector<int>> matrix = {
        {10, 20, 30, 40},
        {15, 25, 35, 45},
        {27, 29, 37, 48},
        {32, 33, 39, 50}
    };

    int R = matrix.size();
    if (R == 0) {
        std::cout << "Matrix is empty." << std::endl;
        return 0;
    }
    int C = matrix[0].size();
    if (C == 0) {
        std::cout << "Matrix rows are empty." << std::endl;
        return 0;
    }

    // Step 2: Create a min-priority queue (min-heap)
    // The Element struct's operator> defines the min-heap behavior
    std::priority_queue<Element, std::vector<Element>, std::greater<Element>> minHeap;

    // Step 3: Push the first element of each row into the min-heap
    // along with its row and column index
    for (int i = 0; i < R; ++i) {
        minHeap.push({matrix[i][0], i, 0});
    }

    // Step 4: Extract elements from the heap and add next from same row
    std::cout << "Sorted elements (Min-Heap):" << std::endl;
    while (!minHeap.empty()) {
        // Get the smallest element from the heap
        Element current = minHeap.top();
        minHeap.pop();

        // Print the element
        std::cout << current.value << " ";

        // If there's a next element in the same row, push it to the heap
        if (current.col + 1 < C) {
            minHeap.push({matrix[current.row][current.col + 1], current.row, current.col + 1});
        }
    }
    std::cout << std::endl;

    return 0;
}

Run

Sample Output:

Sorted elements (Min-Heap):
10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50

Stepwise Explanation:

1. Define Element struct: Create a simple structure Element to store the value, its row index, and col index. This is necessary because the priority queue needs to know which row an element came from to fetch the next one.
2. Custom Comparator: Overload the operator> for the Element struct. This makes std::priority_queue behave as a min-heap (smallest value has higher priority).
3. Initialize Min-Heap: Declare a std::priority_queue named minHeap.
4. Initial Population: Iterate through each row of the matrix. For each row, push the *first element* (matrix[i][0]) along with its row index (i) and col index (0) into the minHeap. At this point, the heap contains the smallest element from each of the R rows.
5. Extraction and Insertion Loop:

• While the minHeap is not empty, perform the following:
• Extract the current smallest Element from the top of the minHeap using minHeap.top() and minHeap.pop().
• Print current.value.
• Check if there's a *next element* in the same row from which current was extracted (current.col + 1 < C).
• If a next element exists, push it into the minHeap with its new value, row, and col index.

1. This process continues until all elements have been extracted and printed.

Conclusion

Printing elements from a row and column-wise sorted matrix in global sorted order is a classic problem that highlights the power of efficient data structures. While a brute-force approach of copying all elements and then sorting them is simple to implement, it becomes inefficient for large matrices due to its higher time and space complexity. The min-heap based solution offers a significantly more optimized approach by leveraging the sorted nature of the rows and efficiently merging elements from all rows. This method reduces the time complexity and uses less auxiliary space, making it the preferred choice for larger datasets.

Summary

• Problem: Print all elements from a matrix, sorted row-wise and column-wise, in global ascending order.
• Brute Force: Copy all N*M elements to a 1D array, then sort.
• Time Complexity: O(N*M log(N*M))
• Space Complexity: O(N*M)
• Min-Heap Approach:
• Use a std::priority_queue (min-heap) to store (value, row, col) of candidate elements.
• Initially, add the first element of each row to the heap.
• Repeatedly extract the minimum element, print it, and add the next element from the same row to the heap.
• Time Complexity: O(N*M log N) (where N is number of rows)
• Space Complexity: O(N) (for the heap)
• The min-heap approach is generally more efficient for larger matrices due to its better time and space complexity.