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


  • 0
    A

    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;
    }
    

Log in to reply
 

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