Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem statement
1.2.
Examples 
2.
Brute force Approach
2.1.
Implementation in Java
2.1.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Implementation in Java
3.1.1.
Complexity analysis
4.
Frequently Asked Questions
4.1.
What are the sorted elements?
4.2.
What is a binary search? How does it work?
4.3.
What is the median of the array?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Find median of row-wise sorted matrix

Author Ashish Sharma
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this article, we will discuss a famous problem of the matrix. But before discussing the problem, let us first understand what is a row-wise sorted matrix, it is a matrix that is ​​arranged in such a way that all the elements in a row are sorted in increasing order, and in a row 'i', where 1 <= i <= n-1, the first element of row 'i' is greater or equal to the last element of row '1'.

                                                                              

                   Unsorted matrix                                                                               Sorted matrix                   

Problem statement

We are given a row-wise sorted matrix of size M, N where M and N represent rows and columns, respectively. Our task is to find the median of a matrix of the row-wise sorted matrix.

Examples 

Input

Output

The Median is 5.

 

Input  

Output

 The Median is 4.

 

Input

 

Output

The Median is 2.

In the above examples, we have found the median of a row-wise sorted matrix.

Recommended Topic, Array Implementation of Queue and  Rabin Karp Algorithm

Brute force Approach

In the brute force approach, to find the median of a row-wise sorted matrix, just fill all the elements in an array and after that sort the array, now we just need to print the middle element of the array, in case of even size array the average of the two middle elements is considered.

Implementation in Java

import java.util.*;
 class median {
    public static void main(String args[]) {
    int row, col;
        Scanner scan = new Scanner(System.in);
     // entering the row, column and elements of matrix respectively.
          System.out.print("Enter the number of rows in the matrix");
          row = scan.nextInt(); 
          System.out.print("Enter the number of columns in the matrix ");
          col = scan.nextInt(); 
          int [][]A=new int[row][col];
            System.out.println("Enter all the elements of matrix");
            for (int i = 0; i < row; i++) 
            {
                for (int j = 0; j < col; j++) 
                {
                    A[i][j] = scan.nextInt();
                }
            }
          // finding the median of the matrix
            int[] median = new int[row * col];
            int index = 0;
            for (int i = 0; i < row; i++) {
              for (int j = 0; j < col; j++) {
                median[index] = A[i][j];
                index++;
            } 
  }
  System.out.println("Median of the row-wise sorted matrix is"+ median[(row * col) / 2]);
 }
}

 

Output

                                   

Complexity Analysis

Time complexity

As we all know the time complexity required to sort the n elements of an array is O(n*log(n)) so if we change the number of the elements from n to ( r1*c1) the time complexity would be O((r1*c1)*log(r1*c1)) for sorting the elements of the matrix and finding the median of the row-wise sorted matrix.

Space complexity

The space complexity would be O(row*col) for storing the elements in a linear array.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

In the optimized approach, we are using binary search which helps us to get O(row*log col) time complexity and O(1) space complexity. In this approach, we are trying to find the mid element of the matrix and checking around how many elements are currently in the matrix now. After this we check if the counter is half of the sum of row*col then it may be the answer, if it is less than then we are increasing the min by 1 and in case it is greater than then, we mark it as the mid and check if it is the answer or not by continuing the above conditions.

Implementation in Java

import java.util.*;
 class median {
    public static int smallmidcount(int[]  A, int mid, int n) {
      int l = 0, h = n - 1;
      while (l <= h) {
        int md = (l + h) >> 1;
        if (A[md] <= mid) {
          l = md + 1;
        } else {
          h = md - 1;
        }
      }
      return l;
    }
   
    public static void main(String args[]) {
      int row, col;
      Scanner scan = new Scanner(System.in);
   // entering the row, col and element of matrix respectively. 
      System.out.print("Enter the number of rows size of the matrix");
      row = scan.nextInt(); 
      System.out.print("Enter the number of columns size of the matrix");
      col = scan.nextInt(); 
      int [][]A=new int[row][col];
        System.out.println("Enter all the elements of matrix");
        for (int i = 0; i < row; i++) 
        {
            for (int j = 0; j < col; j++) 
            {
                A[i][j] = scan.nextInt();
            }
        }
// finding the median of the matrix.
      int low = 1;
      int high = 1000000000;
      int n = row;
      int m = col;
      while (low <= high) {
        int mid = (low + high) >> 1;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
          cnt += smallmidcount(A[i], mid, col);
        }
        if (cnt <= (n * m) / 2)
          low = mid + 1;
        else
          high = mid - 1;
      }
      System.out.println("Median of the row-wise sorted matrix is "+ low);
    }
  }

 

Output

                      

 

Complexity analysis

Time complexity

O(row*log(col)) because we have used binary search, and binary search takes log(n) time and inside binary search, we are checking for the number of elements less than the current element

Space complexity

O(1), since we haven't used any of the extra space to find the median of the matrix.

Frequently Asked Questions

What are the sorted elements?

The sorted elements are those in which each element is in increasing order. Elements can be a number or an alphabet. In java and c++, some predefined functions can be used to sort the elements of the array.  

What is a binary search? How does it work?

Binary search is an efficient algorithm for finding elements in a sorted list of elements. This works by repeatedly dividing the portion of the list that may contain items until you narrow down the possible locations to one. The time complexity of the binary search is O(log(N)) where N is the number of elements.

What is the median of the array?

If we sort the array, the median is the middle element of the array when the length of the array is odd but in the case of even length, there are two medians of the array which need to be printed. 

Conclusion

In this article, we have discussed the famous problem of matrix i.e., to find the median of a row-wise sorted matrix, we have discussed it with examples. We have discussed two different approaches to solve this problem, one being the brute force and the other being the optimized approach and in the end, we have mentioned the algorithmic complexities of each approach. 

After reading about the problem to find the median of the row-wise sorted matrix, are you not feeling excited to read/explore more articles on the topic of file systems? Don't worry; Coding Ninjas has you covered. if you want to practice on matrix then you should follow these questions Search in a 2d arraymatrix chain multiplicationinplace matrix rotate 90 degreesempty cells in a matrixMerge K Sorted Arrays.

Recommended Problems - 


Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Range GCD Query Using Sparse Table
Next article
Minimum Operations required to make each Column and Row of the Matrix Equals
Live masterclass