You are given a square binary grid. A grid is considered binary if every value in the grid is either 1 or 0. You can change at most one cell in the grid from 0 to 1. You need to find the largest group of connected 1’s. Two cells are said to be connected if both are adjacent to each other and both have the same value.
Examples :
Input: grid = [1, 1]
[0, 1]
Output: 4
Explanation: By changing cell (2,1), we can obtain a connected group of 4 1's
[1, 1]
[1, 1]
Input: grid = [1, 0, 1]
[1, 0, 1] [1, 0, 1] Output: 7 Explanation: By changing cell (3,2), we can obtain a connected group of 7 1's [1, 0, 1]
[1, 0, 1] [1, 1, 1]
Expected Time Complexity: O(n2)
Expected Auxiliary Space: O(n2)
Constraints:
1 <= size of the grid<= 500
0 <= grid[i][j] <= 1
Approach 01:
-
C++
-
Python
#include <vector>
#include <stack>
#include <set>
#include <algorithm>
using namespace std;
class Solution {
public:
int MaxConnection(vector<vector<int>>& grid) {
int n = grid.size();
vector<vector<int>> component(n, vector<int>(n, 0));
vector<int> component_sizes(1, 0); // Initialize with zero to make component_sizes 1-based
int component_index = 1;
auto dfs = [&](int x, int y, int comp_index) {
stack<pair<int, int>> st;
st.push({x, y});
component[x][y] = comp_index;
int component_size = 0;
while (!st.empty()) {
pair<int, int> p = st.top();
int i = p.first, j = p.second;
st.pop();
component_size++;
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (const auto& dir : directions) {
int ni = i + dir.first, nj = j + dir.second;
if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] == 1 && component[ni][nj] == 0) {
st.push({ni, nj});
component[ni][nj] = comp_index;
}
}
}
return component_size;
};
// Find all components of 1's using DFS
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && component[i][j] == 0) {
int size = dfs(i, j, component_index);
component_sizes.push_back(size);
component_index++;
}
}
}
int max_connection = *max_element(component_sizes.begin(), component_sizes.end());
// Evaluate each 0 in the grid
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
set<int> neighboring_components;
int potential_connection_size = 1; // Changing this 0 to 1
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (const auto& dir : directions) {
int ni = i + dir.first, nj = j + dir.second;
if (ni >= 0 && ni < n && nj >= 0 && nj < n && component[ni][nj] != 0) {
neighboring_components.insert(component[ni][nj]);
}
}
for (int comp : neighboring_components) {
potential_connection_size += component_sizes[comp];
}
max_connection = max(max_connection, potential_connection_size);
}
}
}
return max_connection;
}
};
from typing import List
from collections import deque
class Solution:
def maxConnection(self, grid: List[List[int]]) -> int:
n = len(grid)
component = [[0] * n for _ in range(n)]
component_sizes = [0] # Initialize with zero to make component_sizes 1-based
component_index = 1
def dfs(x, y, comp_index):
stack = [(x, y)]
component[x][y] = comp_index
component_size = 0
while stack:
i, j = stack.pop()
component_size += 1
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for dx, dy in directions:
ni, nj = i + dx, j + dy
if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == 1 and component[ni][nj] == 0:
stack.append((ni, nj))
component[ni][nj] = comp_index
return component_size
# Find all components of 1's using DFS
for i in range(n):
for j in range(n):
if grid[i][j] == 1 and component[i][j] == 0:
size = dfs(i, j, component_index)
component_sizes.append(size)
component_index += 1
max_connection = max(component_sizes)
# Evaluate each 0 in the grid
for i in range(n):
for j in range(n):
if grid[i][j] == 0:
neighboring_components = set()
potential_connection_size = 1 # Changing this 0 to 1
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for dx, dy in directions:
ni, nj = i + dx, j + dy
if 0 <= ni < n and 0 <= nj < n and component[ni][nj] != 0:
neighboring_components.add(component[ni][nj])
for comp in neighboring_components:
potential_connection_size += component_sizes[comp]
max_connection = max(max_connection, potential_connection_size)
return max_connection
Time Complexity
- DFS for Components:
The DFS traversal to find and label all components takes \(O(n^2)\) time in the worst case because each cell is visited once. For each cell, we explore its four possible directions (up, down, left, right).
- Processing Each Cell:
For each cell, we perform operations that involve constant-time lookups and a bounded number of operations (at most 4 neighboring cells). This step also takes \(O(n^2)\) time in the worst case.
- Overall Time Complexity:
The overall time complexity is \(O(n^2)\) because both the DFS traversal and the subsequent processing of each cell are \(O(n^2)\).
Space Complexity
- Component Matrix:
The `component` matrix is used to store the component index of each cell, requiring \(O(n^2)\) space.
- Component Sizes:
The `component_sizes` vector stores the sizes of the components, which in the worst case can have up to \(O(n^2)\) components, each requiring constant space. Thus, it requires \(O(n^2)\) space.
- Stack for DFS:
The stack used in DFS traversal has a maximum depth of \(O(n^2)\) in the worst case.
- Additional Space:
Other auxiliary data structures such as sets and vectors require \(O(n^2)\) space in the worst case.
- Overall Space Complexity:
The overall space complexity is \(O(n^2)\) due to the storage requirements of the component matrix and the component sizes vector.