Kth element in Matrix

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.

Input: n = 4, mat[][] = [[16, 28, 60, 64], [22, 41, 63, 91], [27, 50, 87, 93], [36, 78, 87, 94]], k = 3
Output: 27
Explanation: 27 is the 3rd smallest element.

Input: n = 4, mat[][] = [[10, 20, 30, 40], [15, 25, 35, 45], [24, 29, 37, 48], [32, 33, 39, 50]], k = 7
Output: 30
Explanation: 30 is the 7th smallest element.

Constraints:
1 <= n <= 500
1 <= mat[i][j] <= 10000
1 <= k <= n*n

Approach 01:

class Solution {
  public:
    int kthSmallest(vector<vector<int>> &matrix, int k) {
        vector<int> flattenedList;

        for (const auto& row : matrix) {
            for (int value : row) {
                flattenedList.push_back(value);
            }
        }

        sort(flattenedList.begin(), flattenedList.end());
        return flattenedList[k - 1];
    }
};

class Solution:
    def kthSmallest(self, matrix, k):
        flattenedList = []
        for row in matrix:
            flattenedList.extend(row)
        
        flattenedList.sort()
        return flattenedList[k - 1]

Time Complexity:

• Flattening the matrix:

  The matrix has \(n \times n\) elements, and we visit each element once → \(O(n^2)\).

• Sorting the list:

  We sort the flattened list of size \(n^2\) → \(O(n^2 \log n^2)\).

• Total Time Complexity:

  \(O(n^2 \log n)\).

Space Complexity:

• Flattened list:

  Stores \(n^2\) elements → \(O(n^2)\).

• Total Space Complexity:

  \(O(n^2)\).