Queries to find index of Kth occurrence of X in diagonal traversal of a Matrix

#include <bits/stdc++.h>

using namespace std;

  

bool isValid(int i, int j, int R, int C)

{

    if (i < 0 || i >= R || j >= C || j < 0)

        return false;

    return true;

}

  

void kthOccurrenceOfElement(

    vector<vector<int> > arr,

    vector<vector<int> > Q)

{

    

    int R = arr.size();

    int C = arr[0].size();

  

    

    

    unordered_map<int, vector<int> > um;

  

    int pos = 1;

  

    

    for (int k = 0; k < R; k++) {

  

        

        um[arr[k][0]].push_back(pos);

  

        

        pos++;

  

        

        

        int i = k - 1;

  

        

        

        int j = 1;

  

        

        while (isValid(i, j, R, C)) {

  

            um[arr[i][j]].push_back(pos);

            pos++;

            i--;

  

            

            j++;

        }

    }

  

    

    for (int k = 1; k < C; k++) {

  

        um[arr[R - 1][k]].push_back(pos);

        pos++;

  

        

        

        int i = R - 2;

  

        

        

        int j = k + 1;

  

        

        while (isValid(i, j, R, C)) {

            um[arr[i][j]].push_back(pos);

            pos++;

            i--;

  

            

            j++;

        }

    }

  

    

    for (int i = 0; i < Q.size(); i++) {

  

        int X = Q[i][0];

        int K = Q[i][1];

  

        

        

        if (um.find(X) == um.end()

            || um[X].size() < K) {

  

            

            cout << -1 << "\n";

        }

  

        

        

        else {

            cout << um[X][K - 1] << ", ";

        }

    }

}

  

int main()

{

    vector<vector<int> > A = { { 1, 4 },

                               { 2, 5 } };

  

    vector<vector<int> > Q = { { 4, 1 },

                               { 5, 1 },

                               { 10, 2 } };

  

    kthOccurrenceOfElement(A, Q);

  

    return 0;

}

Let's block ads! (Why?)