Boundary Length Calculator — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Recursion and solve the Boundary Length Calculator problem optimally.
O(m*n)O(1)Problem Description
You are given an m x n matrix grid of integers where each element is either 0 (empty) or 1 (filled). Treat each filled cell as a unit square aligned with the grid. Compute the total length of the boundary formed by all filled cells. An edge contributes 1 to the length if it is adjacent to a 0 cell or lies on the outer border of the grid. Return the sum of all such edges.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Boundary Length Calculator"
WHY DOES IT MATTER?
This pattern is essential for problems involving grid-based state, cellular automata, and image processing. It teaches the candidate to think in terms of local neighborhoods and how global properties (total boundary) can be derived from local interactions (adjacent cells). It is a stepping stone to more complex graph problems like flood fill, connected components, and shortest path in grids.
OPTIMIZATION CHALLENGE
The key optimization is recognizing that you do not need to trace the boundary path. You can simply sum up the contributions of each cell independently. This avoids the complexity of path tracing and potential errors in handling corners or disconnected components. The space complexity can be reduced to O(1) by not storing any additional data structures, just using a counter.
REAL-WORLD CONNECTION
This is directly applicable in computer vision for object segmentation, where the boundary of a detected object is needed for further analysis. It is also used in 3D modeling to calculate the surface area of voxel-based models, which is critical for physics simulations (e.g., drag, heat dissipation).
In an interview, explicitly state that you are using a 'local neighborhood' approach. Mention that this is a common pattern in grid problems and that it is robust to disconnected components. If the grid is very large, mention the sparse optimization using a hash set. This shows depth and awareness of scalability.
COMPLEXITY AT A GLANCE
O(m*n)O(1)Core Theory — Why This Approach?
The problem of calculating the boundary length of a set of filled cells in a grid is fundamentally a graph traversal and local neighborhood analysis task. Each filled cell (value 1) is a node in a grid graph, and its boundary contribution is determined by its four immediate neighbors (up, down, left, right). A cell contributes 4 to the total boundary if it is isolated, but each adjacent filled cell reduces the boundary count by 2 (one edge for the current cell and one for the neighbor). The naive approach of iterating through every cell and checking its four neighbors results in O(m*n) time complexity, which is optimal for this problem size. However, the theoretical underpinning lies in Eulerian characteristics of planar graphs: the total boundary is equivalent to the number of edges in the dual graph separating the '1' region from the '0' region or the exterior. This perspective is crucial for understanding why simple summation works without needing complex path tracing.
Interview Questions on This Problem
Q1At a fintech platform handling large-scale risk assessment grids, how would you optimize the boundary calculation if the grid was sparse (mostly 0s) and extremely large (10^6 x 10^6)?
For a sparse grid, iterating over all m*n cells is inefficient. Instead, maintain a hash set of coordinates for all '1' cells. Iterate only over the keys in the hash set. For each '1' cell, check its four neighbors in the hash set. If a neighbor is not in the set, it contributes to the boundary. This reduces the time complexity from O(m*n) to O(K), where K is the number of filled cells, which is significantly smaller in sparse scenarios.
Q2In a high-growth engineering startup building a map rendering engine, how does this boundary calculation relate to the concept of 'perimeter' in geographic information systems (GIS)?
This problem is a discrete approximation of calculating the perimeter of a polygon formed by union of squares. In GIS, this is used to calculate the length of coastlines or property boundaries. The key insight is that shared edges between adjacent filled cells are internal and do not contribute to the external perimeter. This is analogous to calculating the surface area of a 3D shape formed by unit cubes, where internal faces are hidden.
Q3At a global product company, if you were asked to extend this problem to calculate the 'wetted perimeter' of water cells (0s) adjacent to land (1s), how would you modify your approach?
The logic remains identical but the condition is inverted. Instead of counting edges of '1' cells that are adjacent to '0' or out-of-bounds, you count edges of '0' cells that are adjacent to '1' or out-of-bounds. However, note that the total boundary length of the '1' region is exactly equal to the total boundary length of the '0' region (excluding the outer border of the grid if we consider the grid as a closed system, or including it depending on definition). In practice, you would iterate through all cells, and for each '0' cell, check its four neighbors. If a neighbor is '1' or out-of-bounds, increment the count. This is also O(m*n).
Examples
Input
3 3\n1 0 1\n1 1 0\n0 1 1
Output
14
Explanation: The filled cells are at (0,0),(0,2),(1,0),(1,1),(2,1),(2,2). There are 5 shared edges between adjacent filled cells, reducing the total from 6*4=24 by 2*5=10, yielding a perimeter of 14.
Input
1 4\n1 1 0 1
Output
10
Explanation: Three filled cells, with one shared edge between the first two cells. Perimeter =3*4-2*1=10.
Input
2 2\n1 1\n1 1
Output
8
Explanation: Four filled cells forming a solid 2x2 block. There are 4 internal shared edges, so perimeter =4*4-2*4=8.
Constraints
- 1 <= m,n <= 1000
- grid[i][j] is either 0 or 1
- The algorithm should run in O(m*n) time and O(1) additional space beyond the input.
Optimal Approach & Strategy
The brute force approach is already optimal for dense grids in terms of time complexity O(m*n). The optimization lies in implementation efficiency: avoid function calls for boundary checks by using inline conditions, and for sparse grids, use a hash set to store only the coordinates of 1-cells, reducing time to O(K) where K is the number of 1-cells.
Brute Force Approach
Iterate through every cell in the grid. For each cell, if it is 1, check all four directions to see if the adjacent cell is 0 or out of bounds, and add 1 to the total for each such edge.
Code Solutions
/**
* Compute the total boundary length of filled cells (1s) in the grid.
* @param {number[][]} grid - 2D array of 0s and 1s
* @return {number} Total boundary length
*/
function boundaryLength(grid) {
if (!grid || grid.length === 0 || grid[0].length === 0) return 0;
const m = grid.length;
const n = grid[0].length;
let total = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
if (i === 0 || grid[i-1][j] === 0) total++;
if (i === m-1 || grid[i+1][j] === 0) total++;
if (j === 0 || grid[i][j-1] === 0) total++;
if (j === n-1 || grid[i][j+1] === 0) total++;
}
}
}
return total;
}
// Driver code
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
let lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
const [m, n] = lines[0].split(' ').map(Number);
const grid = [];
for (let i = 1; i <= m; i++) {
grid.push(lines[i].split(' ').map(Number));
}
console.log(boundaryLength(grid));
});#include <iostream>
#include <vector>
using namespace std;
int boundaryLength(vector<vector<int>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int m = grid.size();
int n = grid[0].size();
int total = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
// Check all 4 directions
if (i == 0 || grid[i-1][j] == 0) total++;
if (i == m-1 || grid[i+1][j] == 0) total++;
if (j == 0 || grid[i][j-1] == 0) total++;
if (j == n-1 || grid[i][j+1] == 0) total++;
}
}
}
return total;
}
int main() {
int m, n;
cin >> m >> n;
vector<vector<int>> grid(m, vector<int>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> grid[i][j];
}
}
cout << boundaryLength(grid) << endl;
return 0;
}import java.util.*;
public class Main {
// Function to compute the total boundary length of filled cells (1s) in the grid.
public static int boundaryLength(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
int m = grid.length;
int n = grid[0].length;
int total = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
if (i == 0 || grid[i-1][j] == 0) total++;
if (i == m-1 || grid[i+1][j] == 0) total++;
if (j == 0 || grid[i][j-1] == 0) total++;
if (j == n-1 || grid[i][j+1] == 0) total++;
}
}
}
return total;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int[][] grid = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = sc.nextInt();
}
}
System.out.println(boundaryLength(grid));
sc.close();
}
}def boundary_length(grid):
"""
Compute the total boundary length of filled cells (1s) in the grid.
Args:
grid: List of lists of integers (0 or 1)
Returns:
int: Total boundary length
"""
if not grid or not grid[0]:
return 0
m = len(grid)
n = len(grid[0])
total = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
if i == 0 or grid[i-1][j] == 0:
total += 1
if i == m-1 or grid[i+1][j] == 0:
total += 1
if j == 0 or grid[i][j-1] == 0:
total += 1
if j == n-1 or grid[i][j+1] == 0:
total += 1
return total
if __name__ == "__main__":
import sys
input = sys.stdin.read
data = input().split()
m = int(data[0])
n = int(data[1])
grid = []
idx = 2
for i in range(m):
row = []
for j in range(n):
row.append(int(data[idx]))
idx += 1
grid.append(row)
print(boundary_length(grid))/**
* Compute the total boundary length of filled cells (1s) in the grid.
* @param {number[][]} grid - 2D array of 0s and 1s
* @return {number} Total boundary length
*/
function boundaryLength(grid) {
if (!grid || grid.length === 0 || grid[0].length === 0) return 0;
const m = grid.length;
const n = grid[0].length;
let total = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
if (i === 0 || grid[i-1][j] === 0) total++;
if (i === m-1 || grid[i+1][j] === 0) total++;
if (j === 0 || grid[i][j-1] === 0) total++;
if (j === n-1 || grid[i][j+1] === 0) total++;
}
}
}
return total;
}
// Driver code
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
let lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
const [m, n] = lines[0].split(' ').map(Number);
const grid = [];
for (let i = 1; i <= m; i++) {
grid.push(lines[i].split(' ').map(Number));
}
console.log(boundaryLength(grid));
});Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.