Time complexity of this code Get Kth Smallest in Yang Matrix


  • 0
    R

    This is google interview problem
    http://www.1point3acres.com/bbs/thread-13146-1-1.html

    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();
            pq.pop();
            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.