## Round 1 - Coding ## Problem Given an `M x N` grid of integers, find the largest connected region where all cells share the same value. Connectivity is 4-directional (up, down, left, right). Return the size and value of that region. ```python def largest_shape(grid: list[list[int]]) -> tuple[int, int]: # returns (size, value) ... ``` ## Example ``` grid = [ [1, 1, 2, 3], [1, 2, 2, 3], [4, 2, 2, 3], [4, 4, 1, 1], ] largest_shape(grid) -> (4, 2) # The 2s form a connected region of size 4 (positions (0,2),(1,1),(1,2),(2,1),(2,2)) -> actually 5 # Trace carefully: (0,2),(1,1),(1,2),(2,1),(2,2) = size 5 largest_shape(grid) -> (5, 2) ``` ## Approach BFS/DFS from each unvisited cell, tracking region size and value. Keep a visited set to avoid double-counting. ## Follow-ups 1. How does your solution change if you also allow diagonal connectivity (8-directional)? 2. If the grid is very large (10,000 x 10,000), how do you handle memory constraints? 3. Return all regions sorted by size descending — what is the overall time and space complexity? 4. How would you extend this to count the perimeter of the largest shape?

InterviewDB Question

Largest Shape: Find the Largest Connected Region of the Same Value in a 2D Grid

phone

Question Details

Round 1 - Coding Problem Given an M x N grid of integers, find the largest connected region where all cells share the same value. Connectivity is 4-directional (up, down, left, right). Return the size and value of that region. Example Approach BFS/DFS from each unvisited cell, tracking region size and value. Keep a visited set to avoid double-counting. Follow-ups How does your solution change if you also allow diagonal connectivity (8-directional)? If the grid is very large (10,000 x 10,000), ho…

Full Details

🔒

Unlock all Glean questions

Full insider details, leaked discussions, and candidate experiences.

Get full access — $100 a year, unlimited access

About This Question

This is a reported interview question from a glean interview during the phone round.

It covers the following topics: Phone, Graph, Coding, Onsite, Matrix .

Topics

Phone Graph Coding Onsite Matrix

Largest Shape: Find the Largest Connected Region of the Same Value in a 2D Grid

Question Details

Full Details

About This Question

Topics

More Glean Interview Questions