Time complexity of this code Get Kth Smallest in Yang Matrix

  • 0

    This is google interview problem

    What's the time complexity of this code? Seems mnlog(mn) but not sure, as I the pq size is changing

    struct Node
        int val;
        int i, j;
        bool operator<(const Node& n) const
            return val>n.val;
    bool visit[1000][1000];
    int YangKthBiggest(vector<vector<int> > data, int k)//1<=k<=m*n
        int m=data.size(), n=data[0].size();
        memset(visit, 0 , sizeof(visit));
        priority_queue<Node> pq;
        pq.push({data[0][0], 0,0});
        for(int i=1;i<k;i++)
            auto cur=pq.top();
            if(cur.i+1<m && !visit[cur.i+1][cur.j])
                visit[cur.i+1][cur.j]=1, pq.push({data[cur.i+1][cur.j], cur.i+1, cur.j});
            if(cur.j+1<n && !visit[cur.i][cur.j+1])
                visit[cur.i][cur.j+1]=1, pq.push({data[cur.i][cur.j+1], cur.i, cur.j+1});
        return pq.top().val;

Log in to reply

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