Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀
100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney
Problem:
https://www.geeksforgeeks.org/problems/kth-element-in-matrix/1
Kth smallest element in a Matrix
Difficulty: Medium Accuracy: 61.42%
Given a matrix mat[][] of size n*n, where each row and column is sorted in non-decreasing order. Find the kth smallest element in the matrix.
Examples:
Input: mat[][] = [[16, 28, 60, 64], k = 3
[22, 41, 63, 91],
[27, 50, 87, 93],
[36, 78, 87, 94]]
Output: 27
Explanation: 27 is the 3rd smallest element.
Input: mat[][] = [[10, 20, 30, 40], k = 7
[15, 25, 35, 45],
[24, 29, 37, 48],
[32, 33, 39, 50]]
Output: 30
Explanation: 30 is the 7th smallest element.
Constraints:
1 ≤ n ≤ 500
1 ≤ mat[i][j] ≤ 104
1 ≤ k ≤ n*n
Solution:
class Solution:
def kthSmallest(self, mat, k):
n = len(mat)
low, high = mat[0][0], mat[-1][-1]
while low < high:
mid = (low + high) // 2
count = 0
for row in mat:
l, r = 0, n
while l < r:
m = (l + r) // 2
if row[m] <= mid:
l = m + 1
else:
r = m
count += l
if count < k:
low = mid + 1
else:
high = mid
return low
Top comments (0)