# Why I got Time Limit Exceeded with C++

• I use the idea of heap, though it is not a total heap, I just put the max element on the top of the heap, every time I just compare the max element of the heap with the next coming value in the matrix, if the value is smaller than the max element , just replace it and build new heap.
Here is my code, I want to figure how it can be improved to be faster.

``````class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
vector<int> heap(k,0);
int i = 0;
for (auto row: matrix) {
if (i == k && row[0] > heap[0]) break;
for (auto elem: row) {
if (i < k) {
heap[i] = elem;
++i;
if (i == k) buildHeap(heap, k);
continue;
}
if (elem > heap[0]) break;
else {
heap[0] = elem;
buildHeap(heap, k);
}
}
}
return heap[0];
}

void percDown(vector<int>& heap, int i, int len) {
int tmp;
int child = 2*i+1;
if ( child + 1 < len && heap[child] < heap[child+1]) ++child;
if (heap[i] < heap[child]) {
tmp = heap[i];
heap[i] = heap[child];
heap[child] = tmp;
}
}
void buildHeap(vector<int>& heap, int len) {
for (int i = (len-1)/2; i >= 0; --i) percDown(heap, i, len);
}
};
``````

Thanks.

• Try `priority_queue` in C++

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.