Given a Grid of size NxM, and two integers X and Y, the task is to count the minimum number of rows between the row containing X and the row containing Y in such a way that the adjacent rows in between them have at least one element in common. Multiple occurrences of a number are allowed in the grid. In other words, two rows are said to be adjacent if they have at least one element in common.
Examples:
Input: arr[][] = {{1, 2, 3}, {2, 5, 6}, {7, 8, 13}}, X = 1, Y = 6
Output: 0
Explanation: X = 1 is present in row 0 (considering 0 – indexing) and Y = 6 is in row 2.
Both the rows have ‘2’ in common both of them are adjacent and there are 0 rows in between.Input: arr[][] = {{1, 2, 3}, {2, 5, 6}, {3, 7, 13}}, X = 2, Y = 6
Output: 0
Explanation: Both the numbers are in same row.Input: arr[][] = {{1, 2, 3}, {2, 5, 6}, {3, 7, 13}}, X = 2, Y = 8
Output: -1
Explanation: There is no possible combination of adjacent rows between row containing X and row containing Y.Input: arr[][] = {{1, 2, 3, 21}, {1, 11, 12, 25}, {12, 13, 14, 7}, {3, 5, 6, 7}, {6, 8, 9, 10}}, X = 1, Y = 9
Output: 1
Explanation: One possible combination of adjacent rows is 0 -> 1 -> 2 -> 3 -> 4 which has 3 adjacent rows between them.
Another possible way 1 -> 2 -> 3 -> 4 which has 2 adjacent rows between them.
The path which have minimum rows would be 0 -> 4 -> 5 which has only 1 row in-between.
Approach: The given problem can be solved by using the shortest path in an unweighted graph that uses BFS Algorithm.
- Create an unweighted graph where each node represents a row.
- Two nodes of this graph are connected if they share at least 1 common number between them.
- Run outer for loop from i = 0 to N where N is the number of rows.
- Run an inner loop from j = i + 1 to N .
- Connect row ‘i’ and row ‘j’ if there is something common in both rows.
- Run outer for loop from i = 0 to N where N is the number of rows.
- Now the problem is reduced to finding the shortest path from the node having X to the node having Y.
- Again run another nested loop and store the rows which have X in a queue to be used for BFS.
- Also, storing all the rows which have Y, it will be used to detect if the node has target number is reached or not.
- If the current node in the BFS traversal of the graph has a Y, return the number of edges traveled – 1.
- If BFS is over return -1 as there is no possible combination of adjacent rows between both rows.
Below is the implementation of the above approach:
C++
// C++ program to implement the approach#include <bits/stdc++.h>using namespace std;// class to represent node in queueclass Node { public: int rowNo; int edgesTravelled; Node(int r, int e) { this->rowNo = r; this->edgesTravelled = e; }};// function to check connection b/w two rowsbool shareCommon(vector<int>& i, vector<int>& j){ // adding all elements of larger array to hashset then // iterating other array set<int> row1; if (i.size() > j.size()) { for (int idx = 0; idx < i.size(); idx++) { row1.insert(i[idx]); } for (int idx = 0; idx < j.size(); idx++) { if (row1.count(j[idx])) return true; } } else { for (int idx = 0; idx < j.size(); idx++) { row1.insert(j[idx]); } for (int idx = 0; idx < i.size(); idx++) { if (row1.count(i[idx])) return true; } } return false;}void minRowsBetweenXY(vector<vector<int> >& arr, int X, int Y){ // No. of rows int N = arr.size(); if (X == Y) { cout << 0; return; } // constructing graph: vector<vector<int> > graph(N); for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // if row i and j share something in common then // connect row i and j if (shareCommon(arr[i], arr[j])) { graph[i].push_back(j); graph[j].push_back(i); } } } // queue for BFS queue<Node> q; // visited array for bfs vector<bool> visited(N, false); // Set to store rows having Y set<int> targetRows; for (int i = 0; i < N; i++) { for (int j = 0; j < arr[i].size(); j++) { if (arr[i][j] == Y) { targetRows.insert(i); } if (arr[i][j] == X && !visited[i]) { q.push(Node(i, 0)); // q.add(new Node(i, 0)); visited[i] = true; } } } // using bfs algorithm: while (q.size() > 0) { Node rm = q.front(); q.pop(); // if the removed node is in the target row then // return if (targetRows.count(rm.rowNo)) { if (rm.edgesTravelled == 0) { cout << 0; return; } cout << rm.edgesTravelled - 1; return; } // adding neighbouring nodes for (int nbr : graph[rm.rowNo]) { if (!visited[nbr]) { int edgesTravelledBeforeNbr = rm.edgesTravelled; q.push( Node(nbr, 1 + edgesTravelledBeforeNbr)); visited[nbr] = true; } } } // if bfs over => path not possible cout << -1;}// Driver codeint main(){ vector<vector<int> > arr = { { 1, 2, 3, 21 }, { 1, 11, 12, 25 }, { 12, 13, 14, 7 }, { 3, 5, 6, 7 }, { 6, 8, 9, 10 } }; int X = 1; int Y = 9; minRowsBetweenXY(arr, X, Y); return 0;}// This code is contributed by abhishekghoshindia. |
Java
// Java program to find minimum adjacent// rows between rows containing X and Yimport java.util.*;class GFG { static void minRowsBetweenXY(int[][] arr, int X, int Y) { // No. of rows int N = arr.length; if (X == Y) { System.out.println(0); return; } // constructing graph: ArrayList<ArrayList<Integer> > graph = new ArrayList<ArrayList<Integer> >(); for (int i = 0; i < N; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // if row i and j share // something in common // then connect row i and j if (shareCommon(arr[i], arr[j])) { graph.get(i).add(j); graph.get(j).add(i); } } } // queue fo BFS Queue<Node> q = new ArrayDeque<>(); // visited array for bfs boolean[] visited = new boolean[N]; // hashset to store rows // having Y HashSet<Integer> targetRows = new HashSet<>(); for (int i = 0; i < N; i++) { for (int j = 0; j < arr[i].length; j++) { if (arr[i][j] == Y) { targetRows.add(i); } if (arr[i][j] == X && !visited[i]) { q.add(new Node(i, 0)); visited[i] = true; } } } // using bfs algorithm: while (q.size() > 0) { Node rm = q.remove(); // if the removed node is in // the target row then return: if (targetRows.contains(rm.rowNo)) { if (rm.edgesTravelled == 0) { System.out.println(0); return; } System.out.println( rm.edgesTravelled - 1); return; } // adding neighbouring nodes for (Integer nbr : graph.get(rm.rowNo)) { if (!visited[nbr]) { int edgesTravelledBeforeNbr = rm.edgesTravelled; q.add(new Node( nbr, edgesTravelledBeforeNbr + 1)); visited[nbr] = true; } } } // if bfs over // => path not possible System.out.println(-1); } // function to check connection b/w // two rows static boolean shareCommon(int[] i, int[] j) { // adding all elements // of larger array to hashset // then iterating other array HashSet<Integer> row1 = new HashSet<>(); if (i.length > j.length) { for (int idx = 0; idx < i.length; idx++) { row1.add(i[idx]); } for (int idx = 0; idx < j.length; idx++) { if (row1.contains(j[idx])) return true; } } else { for (int idx = 0; idx < j.length; idx++) { row1.add(j[idx]); } for (int idx = 0; idx < i.length; idx++) { if (row1.contains(i[idx])) return true; } } return false; } // class to represent node in queue static class Node { int rowNo; int edgesTravelled; Node(int r, int e) { this.rowNo = r; this.edgesTravelled = e; } } // driver code public static void main(String[] args) { int[][] arr = { { 1, 2, 3, 21 }, { 1, 11, 12, 25 }, { 12, 13, 14, 7 }, { 3, 5, 6, 7 }, { 6, 8, 9, 10 } }; int X = 1; int Y = 9; minRowsBetweenXY(arr, X, Y); }} |
Python3
# Python code to implement the approach# class to represent node in queueclass Node: def __init__(self, r, e): self.rowNo = r self.edgesTravelled = e# function to check connection b/w two rowsdef shareCommon(i, j): # adding all elements of larger array to hashset then # iterating other array row1 = set() if (len(i) > len(j)): for idx in range(len(i)): row1.add(i[idx]) for idx in range(len(j)): if (j[idx] in row1): return True else: for idx in range(len(j)): row1.add(j[idx]) for idx in range(len(i)): if (i[idx] in row1): return True return Falsedef minRowsBetweenXY(arr, X, Y): # No. of rows N = len(arr) if (X == Y): print(0) return # constructing graph: graph = [0] * N for i in range(N): graph[i] = [] for i in range(N): for j in range(i + 1, N): # if row i and j share something in common then # connect row i and j if (shareCommon(arr[i], arr[j])): graph[i].append(j) graph[j].append(i) # queue for BFS q = [] # visited array for bfs visited = [0] * N for i in range(N): visited[i] = False # Set to store rows having Y targetRows = set() for i in range(N): for j in range(len(arr[i])): if (arr[i][j] == Y): targetRows.add(i) if (arr[i][j] == X and not visited[i]): q.append(Node(i, 0)) # q.add(new Node(i, 0)); visited[i] = True # using bfs algorithm: while (len(q) > 0): rm = q[0] q.pop(0) # if the removed node is in the target row then # return if (rm.rowNo in targetRows): if (rm.edgesTravelled == 0): print(0) return print(rm.edgesTravelled - 1) return # adding neighbouring nodes for i in range(len(graph[rm.rowNo])): nbr = graph[rm.rowNo][i] if (not visited[nbr]): edgesTravelledBeforeNbr = rm.edgesTravelled q.append(Node(nbr, 1 + edgesTravelledBeforeNbr)) visited[nbr] = True # if bfs over => path not possible print(-1)# Driver codearr = [[1, 2, 3, 21], [1, 11, 12, 25], [12, 13, 14, 7], [3, 5, 6, 7], [6, 8, 9, 10] ]X = 1Y = 9minRowsBetweenXY(arr, X, Y)# This code is contributed by Saurabh Jaiswal |
C#
// C# program to find minimum adjacent// rows between rows containing X and Yusing System;using System.Collections.Generic;public class GFG { // class to represent node in queue public class Node { public int rowNo; public int edgesTravelled; public Node(int r, int e) { this.rowNo = r; this.edgesTravelled = e; } } public static int[] GetRow(int[,] matrix, int row) { var rowLength = matrix.GetLength(1); var rowVector = new int[rowLength]; for (var i = 0; i < rowLength; i++) rowVector[i] = matrix[row, i]; return rowVector; } static void minRowsBetweenXY(int[,] arr, int X, int Y) { // No. of rows int N = arr.GetLength(0); if (X == Y) { Console.WriteLine(0); return; } // constructing graph: List<List<int> > graph = new List<List<int> >(); for (int i = 0; i < N; i++) { graph.Add(new List<int>()); } for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // if row i and j share // something in common // then connect row i and j int[] t1 = GetRow(arr,i); int[] t2 = GetRow(arr,j); if (shareCommon(t1,t2)) { graph[i].Add(j); graph[j].Add(i); } } } // queue fo BFS List<Node> q = new List<Node>(); // visited array for bfs bool[] visited = new bool[N]; // hashset to store rows // having Y HashSet<int> targetRows = new HashSet<int>(); for (int i = 0; i < N; i++) { for (int j = 0; j < arr.GetLength(1); j++) { if (arr[i,j] == Y) { targetRows.Add(i); } if (arr[i,j] == X && !visited[i]) { q.Add(new Node(i, 0)); visited[i] = true; } } } // using bfs algorithm: while (q.Count > 0) { Node rm = q[0]; q.RemoveAt(0); // if the removed node is in // the target row then return: if (targetRows.Contains(rm.rowNo)) { if (rm.edgesTravelled == 0) { Console.WriteLine(0); return; } Console.WriteLine( rm.edgesTravelled - 1); return; } // adding neighbouring nodes foreach (int nbr in graph[rm.rowNo]) { if (!visited[nbr]) { int edgesTravelledBeforeNbr = rm.edgesTravelled; q.Add(new Node( nbr, edgesTravelledBeforeNbr + 1)); visited[nbr] = true; } } } // if bfs over // => path not possible Console.WriteLine(-1); } // function to check connection b/w // two rows static bool shareCommon(int[] i, int[] j) { // adding all elements // of larger array to hashset // then iterating other array HashSet<int> row1 = new HashSet<int>(); if (i.Length > j.Length) { for (int idx = 0; idx < i.Length; idx++) { row1.Add(i[idx]); } for (int idx = 0; idx < j.Length; idx++) { if (row1.Contains(j[idx])) return true; } } else { for (int idx = 0; idx < j.Length; idx++) { row1.Add(j[idx]); } for (int idx = 0; idx < i.Length; idx++) { if (row1.Contains(i[idx])) return true; } } return false; } // driver code public static void Main(String[] args) { int[,] arr = { { 1, 2, 3, 21 }, { 1, 11, 12, 25 }, { 12, 13, 14, 7 }, { 3, 5, 6, 7 }, { 6, 8, 9, 10 } }; int X = 1; int Y = 9; minRowsBetweenXY(arr, X, Y); }}// This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript code to implement the approach // class to represent node in queue class Node { constructor(r, e) { this.rowNo = r; this.edgesTravelled = e; } } // function to check connection b/w two rows function shareCommon(i, j) { // adding all elements of larger array to hashset then // iterating other array var row1 = new Set() if (i.length > j.length) { for (let idx = 0; idx < i.length; idx++) { row1.add(i[idx]) } for (let idx = 0 ; idx < j.length ; idx++) { if (row1.has(j[idx])){ return true } } } else { for (let idx = 0; idx < j.length; idx++) { row1.add(j[idx]); } for (let idx = 0; idx < i.length; idx++) { if (row1.has(i[idx])){ return true } } } return false; } function minRowsBetweenXY(arr, X, Y) { // No. of rows let N = arr.length; if (X == Y) { console.log(0) return; } // constructing graph: var graph = Array(N) for(let i = 0 ; i < N ; i++){ graph[i] = Array() } for (let i = 0; i < N; i++) { for (let j = i + 1; j < N; j++) { // if row i and j share something in common then // connect row i and j if (shareCommon(arr[i], arr[j])) { graph[i].push(j); graph[j].push(i); } } } // queue for BFS var q = Array() // visited array for bfs var visited = Array(N); for(let i = 0 ; i < N ; i++){ visited[i] = false } // Set to store rows having Y var targetRows = new Set() for (let i = 0; i < N; i++) { for (let j = 0; j < arr[i].length; j++) { if (arr[i][j] == Y) { targetRows.add(i) } if (arr[i][j] == X && !visited[i]) { q.push(new Node(i, 0)) // q.add(new Node(i, 0)); visited[i] = true } } } // using bfs algorithm: while (q.length > 0) { var rm = q[0] q.shift() // if the removed node is in the target row then // return if (targetRows.has(rm.rowNo)) { if (rm.edgesTravelled == 0) { console.log(0) return; } console.log(rm.edgesTravelled - 1) return; } // adding neighbouring nodes for(let i = 0 ; i < graph[rm.rowNo].length ; i++){ var nbr = graph[rm.rowNo][i] if (!visited[nbr]) { let edgesTravelledBeforeNbr = rm.edgesTravelled; q.push(new Node(nbr, 1 + edgesTravelledBeforeNbr)); visited[nbr] = true; } } } // if bfs over => path not possible console.log(-1) } // Driver code var arr = [ [ 1, 2, 3, 21 ], [ 1, 11, 12, 25 ], [ 12, 13, 14, 7 ], [ 3, 5, 6, 7 ], [ 6, 8, 9, 10 ] ]; var X = 1; var Y = 9; minRowsBetweenXY(arr, X, Y); // This code is contributed by subhamgoyal2014.</script> |
Output:
1
Time Complexity: O(N2 + N * M)
Auxiliary Space: O(N2 + 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!
