# Hack O(k log k) solution in C succeeds non-deterministically

• This solution uses a min heap and bfs, but I mark visited elements of the matrix by assigning them a random value... which is very unlikely to be one of the matrix values.

It could be fixed without increasing time or space complexity by using a hash table of tuples that have been visited (but you have to implement the data structure, of course).

``````struct mElem{
int i;
int j;
int val;
};

struct minHeap{
int size;
int maxSize;
struct mElem *h;
};

void initMinHeap(struct minHeap **mh, int maxSize){
*mh=malloc(sizeof **mh);
(*mh)->maxSize=maxSize;
(*mh)->size=0;
(*mh)->h=malloc(maxSize * sizeof *(*mh)->h);
}

void destroyMinHeap(struct minHeap **mh){
if(!mh) return;
if(*mh && (*mh)->h) free((*mh)->h);
if(*mh) free(*mh);
*mh=NULL;
}

int isFullMinHeap(struct minHeap *mh){
if(mh->size < mh->maxSize){
return 0;
}else if(mh->size == mh->maxSize){
return 1;
}else{
printf("size larger than maxSize?\n");
exit(-1);
}
}

void doubleMinHeap(struct minHeap *mh){
struct mElem *tmp;
tmp=realloc(mh->h,2*mh->maxSize*sizeof *mh->h);
if(!tmp) exit(-1);
mh->h=tmp;
mh->maxSize*=2;
}

int parent(int i){
return (i-1)/2;
}

int l_child(int i){
return 2*i+1;
}

int r_child(int i){
return 2*i+2;
}

void swap(struct minHeap *mh, int i, int j){
struct mElem *A=mh->h;
struct mElem tmp;
tmp=A[i];
A[i]=A[j];
A[j]=tmp;
}

int valMinHeap(struct minHeap *mh,int i){
if(i>=mh->size){
printf("outside range\n");
exit(-1);
}
return mh->h[i].val;
}

int ltmElem(struct minHeap *mh, int i, int j){
return valMinHeap(mh,i)<valMinHeap(mh,j);
}

void upMinHeap(struct minHeap *mh){
int i=mh->size-1;
while(i>0){
if(ltmElem(mh,i,parent(i))){
swap(mh,i,parent(i));
i=parent(i);
}else{
break;
}
}
}

void downMinHeap(struct minHeap *mh){
int i=0;
int smallest;
int l,r;
while((l=l_child(i))<mh->size){
smallest=i;
if(ltmElem(mh,l,smallest)){
smallest=l;
}
if((r=r_child(i))<mh->size && ltmElem(mh,r,smallest)){
smallest=r;
}
if(smallest!=i){
swap(mh,i,smallest);
i=smallest;
}else break;
}
}

void insertMinHeap(struct minHeap *mh,struct mElem e){
if(isFullMinHeap(mh)){
doubleMinHeap(mh);
insertMinHeap(mh,e);
}else{
mh->h[mh->size++]=e;
upMinHeap(mh);
}
}

int isEmptyMinHeap(struct minHeap *mh){
if(mh->size==0){
return 1;
}else if(mh->size<0){
printf("Heap with negative size\n");
exit(-1);
}else{
return 0;
}
}

struct mElem popMinHeap(struct minHeap *mh){
if(isEmptyMinHeap(mh)){
printf("Trying to pop an empty min heap\n");
exit(-1);
}
struct mElem res=mh->h[0];
mh->h[0]=mh->h[--mh->size];
downMinHeap(mh);
return res;
}

int kthSmallest(int **matrix, int matrixRowSize, int matrixColSize, int k) {
int count;
struct minHeap *mh;
struct mElem e={0,0,matrix[0][0]},f={0,0,0};
initMinHeap(&mh,1);
insertMinHeap(mh,e);
int hack_visited_value_lol=rand();
matrix[e.i][e.j]=hack_visited_value_lol;//mark as visited
for(count=0;count<k;count++){
e=popMinHeap(mh);
//printf("e.val %d\n",e.val);
if(e.i+1<matrixRowSize && matrix[e.i+1][e.j]!=hack_visited_value_lol){
insertMinHeap(mh,(struct mElem){e.i+1,e.j,matrix[e.i+1][e.j]});
matrix[e.i+1][e.j]=hack_visited_value_lol;//mark as visited
}
if(e.j+1<matrixColSize && matrix[e.i][e.j+1]!=hack_visited_value_lol){
insertMinHeap(mh,(struct mElem){e.i,e.j+1,matrix[e.i][e.j+1]});
matrix[e.i][e.j+1]=hack_visited_value_lol;//mark as visited
}
//printMinHeap(mh);
}
destroyMinHeap(&mh);
return e.val;
}
``````

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