Count Regions in a Binary Grid
Company: Illumio
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an `m x n` grid where `1` represents land and `0` represents water, count how many connected land regions exist. Two land cells belong to the same region if they are connected horizontally or vertically.
Write a function that returns the number of distinct regions. Also discuss the time and space complexity of your approach.
Quick Answer: This question evaluates understanding of grid-as-graph representations, identification of connected components, and competency in algorithmic problem-solving with attention to time and space complexity.
Given a binary grid, count four-directionally connected regions of 1 values.
Constraints
- Inputs are provided as Python literals compatible with the function signature.
- Return a deterministic value exactly matching the requested output.
Examples
Input: ([[1,0,1], [0,1,0], [1,0,1]],)
Expected Output: 5
Explanation: Diagonal contact does not connect.
Input: ([[1,1,0], [0,1,1], [0,0,1]],)
Expected Output: 1
Explanation: One bent region.
Input: ([],)
Expected Output: 0
Explanation: Empty grid.
Hints
- Start with a direct data structure representation.
- Handle edge cases before the main loop.