heapq in Python to print all elements in sorted order from row and column wise sorted matrix

0 0 2 minutes read

Given an n x n matrix, where every row and column is sorted in non-decreasing order. Print all elements of matrix in sorted order. Examples:

Input : mat= [[10, 20, 30, 40],
              [15, 25, 35, 45],
              [27, 29, 37, 48],
              [32, 33, 39, 50]]

Output : Elements of matrix in sorted order
         [10, 15, 20, 25, 27, 29, 30, 32, 
          33, 35, 37, 39, 40, 45, 48, 50]

This problem has existing solution please refer link. We will solve this problem in python with the same approach of merging two sorted arrays using heapq module.

Implementation:

Python3

# Function to print all elements in sorted order
# from row and column wise sorted matrix
from heapq import merge
 
def sortedMatrix(mat):
     
    # initialize result variable with first row of matrix
    result=mat[0]
 
    # now traverse through complete matrix
    # after first row and merge each row with
    # result one by one
    # after last operation result will contain
    # list of sorted elements of matrix
    for row in mat[1:]:
        result=list(merge(result,row))
 
    return result
 
if __name__ == "__main__":
    mat = [[10, 20, 30, 40],
        [15, 25, 35, 45],
        [27, 29, 37, 48],
        [32, 33, 39, 50]]
    print ('Elements of matrix in sorted order')
    print (sortedMatrix(mat))

Output

Elements of matrix in sorted order
[10, 15, 20, 25, 27, 29, 30, 32, 33, 35, 37, 39, 40, 45, 48, 50]

This article is contributed by Shashank Mishra (Gullu). If you likezambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on thezambiatek main page and help other Geeks.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
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,000zambiatek! Whether it’s DSA in C++, Java, Python, or JavaScript we’ve got you covered. Let’s embark on this exciting journey together!