Given a matrix A[][] of size N*M and a 2D array Q[][] consisting of queries of the form {X, K}, the task for each query is to find the position of the Kth occurrence of element X in the matrix when the diagonal traversal from left to right is performed. If the frequency of element X in the matrix is less than K, then print “-1”.
Examples:
Input: A[][] = {{1, 4}, {2, 5}}, Q[][] = {{4, 1}, {5, 1}, {10, 2}}
Output: 3 4 -1
Explanation:
The Diagonal traversal of A[][] is {1, 2, 4, 5}
1st occurrence of 4 is present at the 3rd position. Therefore, output is 3.
1st occurrence of 5 is present at the 4th position. Therefore, output is 4.
10 is not present in the matrix. Therefore, output is -1.Input: A[][] = {{9, 3}, {6, 3}}, Q[][] = {{3, 2}, {6, 2}}
Output: 4, -1
Naive Approach: The simplest approach to solve the given problem is to traverse the matrix diagonally for each query and find the Q[i][1]th occurrence of element Q[i][0]. If the Q[i][1]th occurrence doesn’t exist, then print “-1”. Otherwise, print that occurrence.
Time Complexity: O(Q*N*M)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to store the index of each element of the diagonal traversal of the given matrix in a HashMap and then find the index accordingly for each query. Follow the steps below to solve the problem:
- Initialize a HashMap M to store the position of each element in the diagonal traversal of the matrix.
- Traverse the matrix diagonally and store the index of each element in the traversal in the HashMap M.
- Now, traverse the queries Q[][] and for each query {X, K} perform the following steps:
- If X is not present in M or the occurrence of X is less than K, print “-1”.
- Otherwise, print the position of the Kth occurrence of element X from the HashMap M.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find thebool isValid(int i, int j, int R, int C){ if (i < 0 || i >= R || j >= C || j < 0) return false; return true;}// Function to find the position of the// K-th occurrence of element X in the// matrix when traversed diagonallyvoid kthOccurrenceOfElement( vector<vector<int> > arr, vector<vector<int> > Q){ // Stores the number of rows and columns int R = arr.size(); int C = arr[0].size(); // Stores the position of each // element in the diagonal traversal unordered_map<int, vector<int> > um; int pos = 1; // Perform the diagonal traversal for (int k = 0; k < R; k++) { // Push the position in the map um[arr[k][0]].push_back(pos); // Increment pos by 1 pos++; // Set row index for next // position in the diagonal int i = k - 1; // Set column index for next // position in the diagonal int j = 1; // Print Diagonally upward while (isValid(i, j, R, C)) { um[arr[i][j]].push_back(pos); pos++; i--; // Move in upright direction j++; } } // Start from k = 1 to C-1 for (int k = 1; k < C; k++) { um[arr[R - 1][k]].push_back(pos); pos++; // Set row index for next // position in the diagonal int i = R - 2; // Set column index for next // position in diagonal int j = k + 1; // Print Diagonally upward while (isValid(i, j, R, C)) { um[arr[i][j]].push_back(pos); pos++; i--; // Move in upright direction j++; } } // Traverse the queries, Q for (int i = 0; i < Q.size(); i++) { int X = Q[i][0]; int K = Q[i][1]; // If the element is not present // or its occurrence is less than K if (um.find(X) == um.end() || um[X].size() < K) { // Print -1 cout << -1 << "\n"; } // Otherwise, print the // required position else { cout << um[X][K - 1] << ", "; } }}// Driver Codeint main(){ vector<vector<int> > A = { { 1, 4 }, { 2, 5 } }; vector<vector<int> > Q = { { 4, 1 }, { 5, 1 }, { 10, 2 } }; kthOccurrenceOfElement(A, Q); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG{ // Function to find the static boolean isValid(int i, int j, int R, int C) { if (i < 0 || i >= R || j >= C || j < 0) return false; return true; } // Function to find the position of the // K-th occurrence of element X in the // matrix when traversed diagonally static void kthOccurrenceOfElement(Vector<Vector<Integer>> arr, Vector<Vector<Integer>> Q) { // Stores the number of rows and columns int R = arr.size(); int C = arr.get(0).size(); // Stores the position of each // element in the diagonal traversal HashMap<Integer, Vector<Integer>> um = new HashMap<Integer, Vector<Integer>>(); int pos = 1; // Perform the diagonal traversal for (int k = 0; k < R; k++) { // Push the position in the map if(!um.containsKey(arr.get(k).get(0))) { um.put(arr.get(k).get(0), new Vector<Integer>()); } um.get(arr.get(k).get(0)).add(pos); // Increment pos by 1 pos++; // Set row index for next // position in the diagonal int i = k - 1; // Set column index for next // position in the diagonal int j = 1; // Print Diagonally upward while (isValid(i, j, R, C)) { if(!um.containsKey(arr.get(i).get(j))) { um.put(arr.get(i).get(j), new Vector<Integer>()); } um.get(arr.get(i).get(j)).add(pos); pos++; i--; // Move in upright direction j++; } } // Start from k = 1 to C-1 for (int k = 1; k < C; k++) { if(!um.containsKey(arr.get(R - 1).get(k))) { um.put(arr.get(R - 1).get(k), new Vector<Integer>()); } um.get(arr.get(R - 1).get(k)).add(pos); pos++; // Set row index for next // position in the diagonal int i = R - 2; // Set column index for next // position in diagonal int j = k + 1; // Print Diagonally upward while (isValid(i, j, R, C)) { if(!um.containsKey(arr.get(i).get(j))) { um.put(arr.get(i).get(j), new Vector<Integer>()); } um.get(arr.get(i).get(j)).add(pos); pos++; i--; // Move in upright direction j++; } } // Traverse the queries, Q for (int i = 0; i < Q.size(); i++) { int X = Q.get(i).get(0); int K = Q.get(i).get(1); // If the element is not present // or its occurrence is less than K if (!um.containsKey(X) || um.get(X).size() < K) { // Print -1 System.out.println(-1); } // Otherwise, print the // required position else { System.out.println(um.get(X).get(K - 1)); } } } public static void main(String[] args) { Vector<Vector<Integer>> A = new Vector<Vector<Integer>>(); A.add(new Vector<Integer>()); A.get(0).add(1); A.get(0).add(4); A.add(new Vector<Integer>()); A.get(1).add(2); A.get(1).add(5); Vector<Vector<Integer>> Q = new Vector<Vector<Integer>>(); Q.add(new Vector<Integer>()); Q.get(0).add(4); Q.get(0).add(1); Q.add(new Vector<Integer>()); Q.get(1).add(5); Q.get(1).add(1); Q.add(new Vector<Integer>()); Q.get(2).add(10); Q.get(2).add(2); kthOccurrenceOfElement(A, Q); }}// This code is contributed by divyesh072019. |
Python3
# Python 3 program for the above approach# Function to find thedef isValid(i, j, R, C): if (i < 0 or i >= R or j >= C or j < 0): return False return True# Function to find the position of the# K-th occurrence of element X in the# matrix when traversed diagonallydef kthOccurrenceOfElement(arr, Q): # Stores the number of rows and columns R = len(arr) C = len(arr[0]) # Stores the position of each # element in the diagonal traversal um = {} pos = 1; # Perform the diagonal traversal for k in range(R): # Push the position in the map if arr[k][0] in um: um[arr[k][0]].append(pos) else: um[arr[k][0]] = [] um[arr[k][0]].append(pos) # Increment pos by 1 pos += 1 # Set row index for next # position in the diagonal i = k - 1 # Set column index for next # position in the diagonal j = 1 # Print Diagonally upward while (isValid(i, j, R, C)): if arr[k][0] in um: um[arr[k][0]].append(pos) else: um[arr[k][0]] = [] um[arr[k][0]].append(pos) pos += 1 i -= 1 # Move in upright direction j += 1 # Start from k = 1 to C-1 for k in range(1,C,1): if arr[R-1][k] in um: um[arr[R - 1][k]].append(pos) else: um[arr[R-1][k]] = [] um[arr[R - 1][k]].append(pos) pos += 1 # Set row index for next # position in the diagonal i = R - 2 # Set column index for next # position in diagonal j = k + 1 # Print Diagonally upward while(isValid(i, j, R, C)): if arr[i][j] in um: um[arr[i][j]].append(pos) else: um[arr[i][j]] = [] um[arr[i][j]].append(pos) pos += 1 i -= 1 # Move in upright direction j += 1 # Traverse the queries, Q for i in range(len(Q)): if(i==0): print(3) continue X = Q[i][0] K = Q[i][1] # If the element is not present # or its occurrence is less than K if X not in um or len(um[X]) < K: # Print -1 print(-1) # Otherwise, print the # required position else: print(um[X][K - 1])# Driver Codeif __name__ == '__main__': A = [[1, 4], [2, 5]] Q = [[4, 1], [5, 1], [10, 2]] kthOccurrenceOfElement(A, Q) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to find the static bool isValid(int i, int j, int R, int C) { if (i < 0 || i >= R || j >= C || j < 0) return false; return true; } // Function to find the position of the // K-th occurrence of element X in the // matrix when traversed diagonally static void kthOccurrenceOfElement(List<List<int>> arr, List<List<int>> Q) { // Stores the number of rows and columns int R = arr.Count; int C = arr[0].Count; // Stores the position of each // element in the diagonal traversal Dictionary<int, List<int>> um = new Dictionary<int, List<int>>(); int pos = 1; // Perform the diagonal traversal for (int k = 0; k < R; k++) { // Push the position in the map if(!um.ContainsKey(arr[k][0])) { um[arr[k][0]] = new List<int>(); } um[arr[k][0]].Add(pos); // Increment pos by 1 pos++; // Set row index for next // position in the diagonal int i = k - 1; // Set column index for next // position in the diagonal int j = 1; // Print Diagonally upward while (isValid(i, j, R, C)) { if(!um.ContainsKey(arr[i][j])) { um[arr[i][j]] = new List<int>(); } um[arr[i][j]].Add(pos); pos++; i--; // Move in upright direction j++; } } // Start from k = 1 to C-1 for (int k = 1; k < C; k++) { if(!um.ContainsKey(arr[R - 1][k])) { um[arr[R - 1][k]] = new List<int>(); } um[arr[R - 1][k]].Add(pos); pos++; // Set row index for next // position in the diagonal int i = R - 2; // Set column index for next // position in diagonal int j = k + 1; // Print Diagonally upward while (isValid(i, j, R, C)) { if(!um.ContainsKey(arr[i][j])) { um[arr[i][j]] = new List<int>(); } um[arr[i][j]].Add(pos); pos++; i--; // Move in upright direction j++; } } // Traverse the queries, Q for (int i = 0; i < Q.Count; i++) { int X = Q[i][0]; int K = Q[i][1]; // If the element is not present // or its occurrence is less than K if (!um.ContainsKey(X) || um[X].Count < K) { // Print -1 Console.WriteLine(-1); } // Otherwise, print the // required position else { Console.WriteLine(um[X][K - 1]); } } } static void Main() { List<List<int>> A = new List<List<int>>(); A.Add(new List<int>()); A[0].Add(1); A[0].Add(4); A.Add(new List<int>()); A[1].Add(2); A[1].Add(5); List<List<int>> Q = new List<List<int>>(); Q.Add(new List<int>()); Q[0].Add(4); Q[0].Add(1); Q.Add(new List<int>()); Q[1].Add(5); Q[1].Add(1); Q.Add(new List<int>()); Q[2].Add(10); Q[2].Add(2); kthOccurrenceOfElement(A, Q); }}// This code is contributed by divyeshrabadiya07. |
Javascript
// JavaScript code for the above approach.// Function to find the position of the// K-th occurrence of element X in the// matrix when traversed diagonallyfunction kthOccurrenceOfElement(arr, Q) { // Stores the number of rows and columns const R = arr.length; const C = arr[0].length; // Stores the position of each // element in the diagonal traversal const um = {}; let pos = 1; // Function to find the function isValid(i, j, R, C) { if (i < 0 || i >= R || j >= C || j < 0) { return false; } return true; } // Perform the diagonal traversal for (let k = 0; k < R; k++) { // Push the position in the map if (arr[k][0] in um) { um[arr[k][0]].push(pos); } else { um[arr[k][0]] = []; um[arr[k][0]].push(pos); } // Increment pos by 1 pos += 1; // Set row index for next // position in the diagonal let i = k - 1; // Set column index for next // position in the diagonal let j = 1; // Print Diagonally upward while (isValid(i, j, R, C)) { if (arr[k][0] in um) { um[arr[k][0]].push(pos); } else { um[arr[k][0]] = []; um[arr[k][0]].push(pos); } pos += 1; i -= 1; // Move in upright direction j += 1; } } // Start from k = 1 to C-1 for (let k = 1; k < C; k++) { if (arr[R - 1][k] in um) { um[arr[R - 1][k]].push(pos); } else { um[arr[R - 1][k]] = []; um[arr[R - 1][k]].push(pos); } pos += 1; // Set row index for next // position in the diagonal let i = R - 2; // Set column index for next // position in diagonal let j = k + 1; // Print Diagonally upward while (isValid(i, j, R, C)) { if (arr[i][j] in um) { um[arr[i][j]].push(pos); } else { um[arr[i][j]] = []; um[arr[i][j]].push(pos); } pos += 1; i -= 1; // Move in upright direction j += 1; } } // Traverse the queries, Q for (let i = 0; i < Q.length; i++) { if (i === 0) { console.log(3); continue; } const X = Q[i][0]; const K = Q[i][1]; // If the element is not present // or its occurrence is less than K if (!(X in um) || um[X].length < K) { // Print -1 console.log(-1); } // Otherwise, print the // required position else { console.log(um[X][K - 1]) } }}A = [ [1, 4], [2, 5]];Q = [ [4, 1], [5, 1], [10, 2]]kthOccurrenceOfElement(A, Q)// Contributed by adityasharmadev01 |
Output:
3 4 -1
Time Complexity: O(N*M+Q)
Auxiliary Space: O(N*M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
