Given a square matrix mat every element of which is either 0 or 1. A value 1 means connected and 0 means not connected. The task is to find the largest length of a path in the matrix after changing atmost one 0 to 1. A path is a 4-directionally connected group of 1s.
Examples:
Input: mat[][] = {{1, 1}, {1, 0}}
Output: 4 Change the only 0 to 1 and the length of the largest path will be 4.Input: mat[][] = {{1, 1}, {1, 1}}
Output: 4
Naive Approach: The idea is to change each ‘0’ to ‘1’ one by one and do a Depth First Search to find the size of the largest path.
Efficient Approach: In the naive approach, we have checked every ‘0’. However, we can also make this efficient by storing the size of each group, so that we do not have to use depth-first search to repeatedly calculate the same size all over again.
Note: We need to take care when the 0 touches the same group. For example, consider grid = [[0, 1], [1, 1]]. The right and bottom neighbor of the 0 will belong to the same group after changing 0 to 1. We can solve this problem by keeping track of group Id (or Index), that will be unique for each group.
- For each groups, fill it with value Index and remember its size as an element in the array area[Index] which can be found out with a depth first search..
- Then for each 0, look at the neighboring group IDs and add the area of those groups, and add 1 for the 0 we are toggling. This will give us the answer, and we take the maximum of it from previous answer.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// check if index is within rangevector<vector<int> > neighbors(int r, int c, int N){ vector<vector<int> > list = { { r - 1, c }, { r + 1, c }, { r, c - 1 }, { r, c + 1 } }; vector<vector<int> > res; for (vector<int> x : list) { if (x[0] >= 0 && x[0] < N && x[1] >= 0 && x[1] < N) { res.push_back(x); } } return res;}// dfs to calculate length of pathint dfs(int R, int C, int index, vector<vector<int> >& grid, int N){ int ans = 1; grid[R][C] = index; for (vector<int> x : neighbors(R, C, N)) { int nr = x[0], nc = x[1]; if (grid[nr][nc] == 1) { ans += dfs(nr, nc, index, grid, N); } } return ans;}// function to return largest possible length of Pathint largestPath(vector<vector<int> >& grid){ int N = grid.size(); unordered_map<int, int> area; int index = 2; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (grid[i][j] == 1) { area[index] = dfs(i, j, index, grid, N); index++; } } } int ans = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (grid[i][j] == 0) { unordered_set<int> seen; for (vector<int> x : neighbors(i, j, N)) { int nr = x[0], nc = x[1]; if (grid[nr][nc] > 1) { seen.insert(grid[nr][nc]); } } int temp = 1; for (int k : seen) { temp += area[k]; } ans = max(ans, temp); } } } // return maximum possible length return ans;}// Driver codeint main(){ vector<vector<int> > I = { { 1, 0 }, { 0, 1 } }; cout << largestPath(I) << endl; return 0;} |
Java
// Java implementation for the above approachimport java.util.*;class GFG { // check if index is within range static int[][] neighbors(int r, int c, int N) { int[][] list = {{r - 1, c}, {r + 1, c}, {r, c - 1}, {r, c + 1}}; ArrayList<int[]> res = new ArrayList<int[]>(); for (int[] x: list) { if (x[0] >= 0 && x[0] < N && x[1] >= 0 && x[1] < N) { res.add(x); } } return res.toArray(new int[res.size()][]); } // dfs to calculate length of path static int dfs(int R, int C, int index, int[][] grid, int N) { int ans = 1; grid[R][C] = index; for (int[] x: neighbors(R, C, N)) { int nr = x[0], nc = x[1]; if (grid[nr][nc] == 1) { ans += dfs(nr, nc, index, grid, N); } } return ans; } // function to return largest possible length of Path static int largestPath(int[][] grid) { int N = grid.length; HashMap<Integer, Integer> area = new HashMap<Integer, Integer>(); int index = 2; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (grid[i][j] == 1) { area.put(index, dfs(i, j, index, grid, N)); index++; } } } int ans = Collections.max(area.values(), null); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (grid[i][j] == 0) { HashSet<Integer> seen = new HashSet<Integer>(); for (int[] x: neighbors(i, j, N)) { int nr = x[0], nc = x[1]; if (grid[nr][nc] > 1) { seen.add(grid[nr][nc]); } } int temp = 1; for (int k: seen) { temp += area.get(k); } ans = Math.max(ans, temp); } } } // return maximum possible length return ans; } // Driver code public static void main(String[] args) { int[][] I = {{1, 0}, {0, 1}}; System.out.println(largestPath(I)); }} |
Python3
# Python3 implementation of above approach# check if index is within rangedef neighbors(r, c, N): for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)): if 0 <= nr < N and 0 <= nc < N: yield nr, nc# dfs to calculate length of pathdef dfs(R, C, index, grid, N): ans = 1 grid[R][C] = index for nr, nc in neighbors(R, C, N): if grid[nr][nc] == 1: ans += dfs(nr, nc, index) return ans# function to return largest possible length of Pathdef largestPath(grid): N = len(grid) area = {} index = 2 for i in range(N): for j in range(N): if grid[i][j] == 1: area[index] = dfs(i, j, index, grid, N) index += 1 ans = max(area.values() or [0]) for i in range(N): for j in range(N): if grid[i][j] == 0: seen = {grid[nr][nc] for nr, nc in neighbors(i, j, N) if grid[nr][nc] > 1} ans = max(ans, 1 + sum(area[i] for i in seen)) # return maximum possible length return ans# Driver codeI = [[1, 0], [0, 1]]# Function call to print answerprint(largestPath(I))# This code is written by# Sanjit_Prasad |
C#
using System;using System.Collections.Generic;class GFG {// check if index is within rangestatic int[][] neighbors(int r, int c, int N) { int[][] list = new int[4][]{new int[]{r - 1, c},new int[] {r + 1, c}, new int[]{r, c - 1},new int[] {r, c + 1}}; List<int[]> res = new List<int[]>(); foreach (int[] x in list) { if (x[0] >= 0 && x[0] < N && x[1] >= 0 && x[1] < N) { res.Add(x); } } return res.ToArray();}// dfs to calculate length of pathstatic int dfs(int R, int C, int index, int[][] grid, int N) { int ans = 1; grid[R][C] = index; foreach (int[] x in neighbors(R, C, N)) { int nr = x[0], nc = x[1]; if (grid[nr][nc] == 1) { ans += dfs(nr, nc, index, grid, N); } } return ans;}// function to return largest possible length of Pathstatic int largestPath(int[][] grid) { int N = grid.Length; Dictionary<int, int> area = new Dictionary<int, int>(); int index = 2; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (grid[i][j] == 1) { area.Add(index, dfs(i, j, index, grid, N)); index++; } } } int ans = 0; foreach (int a in area.Values) { ans = Math.Max(ans, a); } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (grid[i][j] == 0) { HashSet<int> seen = new HashSet<int>(); foreach (int[] x in neighbors(i, j, N)) { int nr = x[0], nc = x[1]; if (grid[nr][nc] > 1) { seen.Add(grid[nr][nc]); } } int temp = 1; foreach (int k in seen) { temp += area[k]; } ans = Math.Max(ans, temp); } } } // return maximum possible length return ans;}// Driver codepublic static void Main(string[] args) { int[][] I = new int[2][] { new int[] { 1, 0 }, new int[] { 0, 1 } }; Console.WriteLine(largestPath(I));}} |
Javascript
// check if index is within rangefunction* neighbors(r, c, N) { const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]; for (const [dr, dc] of directions) { const nr = r + dr; const nc = c + dc; if (0 <= nr && nr < N && 0 <= nc && nc < N) { yield [nr, nc]; } }}// dfs to calculate length of pathfunction dfs(R, C, index, grid, N) { let ans = 1; grid[R][C] = index; for (const [nr, nc] of neighbors(R, C, N)) { if (grid[nr][nc] == 1) { ans += dfs(nr, nc, index, grid, N); } } return ans;}// function to return largest possible length of Pathfunction largestPath(grid) { const N = grid.length; const area = {}; let index = 2; for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) { if (grid[i][j] == 1) { area[index] = dfs(i, j, index, grid, N); index += 1; } } } let ans = Math.max(...Object.values(area), 0); for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) { if (grid[i][j] == 0) { const seen = new Set(); for (const [nr, nc] of neighbors(i, j, N)) { if (grid[nr][nc] > 1) { seen.add(grid[nr][nc]); } } ans = Math.max(ans, 1 + [...seen].reduce((acc, val) => acc + area[val], 0)); } } } // return maximum possible length return ans;}// Driver codeconst I = [[1, 0], [0, 1]];// Function call to print answerconsole.log(largestPath(I)); |
Output
3
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!