378. Kth Smallest Element in a Sorted Matrix

Question

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element. You must find a solution with a memory complexity better than O(n2). Example 1: Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 Output: 13 Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13 Example 2: Input: matrix = [[-5]], k = 1 Output: -5 Constraints: n == matrix.length == matrix[i].length 1 <= n <= 300 -109 <= matrix[i][j] <= 109 All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order. 1 <= k <= n2 Follow up: Could you solve the problem with a constant memory (i.e., O(1) memory complexity)? Could you solve the problem in O(n) time complexity? The solution may be too advanced for an interview but you may find reading this paper fun.

My Solution

My solution is to an vertical sweep of the matrix to find the kth smallest element.I keep a track of current element index in ith row and traverse through these to find smallest in all the rows till I find the kth element. worst case, O(n^2).

Optimal Solution

Optimal Solution is to perform lowerbound binary search on the matrix using low first element and high as last element of the matrix. we find mid and what rank does mid hold in the matrix, for this we take row =0 and c=m-1; (n rows and m columns) if matrix[r][c]<=mid then we increment r and counter with c+1 or (m). if last element of a row is larger than mid then mid must be in another row. if matrix[r][c]>mid then decrement c till we get lower or equal element than mid. we add this c to count and return count. we get rank of mid. if this is equal or greater than k then update the result with count and high with mid-1. if this is less then we update low with mid;

Comments

Popular posts from this blog

LeetCode 3Sum

New start Day 2 (1/10/2020) codeforces 492B Vanya and Lantern

Heap (min)