Frontend School

Bigbasket Delivery Zone Analysis

DSA
medium

Bigbasket Delivery Zone Analysis

Medium
Graph
BFS
DFS
Matrix

Overview

Bigbasket optimizes delivery routes by grouping houses into "delivery zones". A delivery zone is a cluster of houses that are reachable from each other, allowing a single delivery executive to cover them efficiently. However, some areas might be temporarily restricted (e.g., due to roadwork, construction) and cannot be traversed. We need to identify and count the number of independent delivery zones given a city map.

What you need to do / Task

Given a 2D grid representing a city's layout, where '1' denotes a house requiring delivery, '0' denotes an empty lot, and 'R' denotes a restricted area, find the total number of distinct delivery zones. A delivery zone is defined as a group of '1's where every '1' in the group is reachable from every other '1' in the same group by only moving horizontally or vertically through other '1's or '0's. Movement through 'R' cells is strictly forbidden.

Input & output

Input:

  • grid: A m x n array of characters, where grid[i][j] can be '1' (house), '0' (empty lot), or 'R' (restricted area).

Output:

  • An integer representing the total number of distinct delivery zones.

Clarifications

  • Houses are considered part of the same delivery zone if they are connected (directly adjacent or through a path of '1's or '0's).
  • Movement is restricted to 4 directions: up, down, left, right.
  • You cannot move into or through 'R' cells.
  • An individual '1' that is not connected to any other '1's (other than itself) still counts as one delivery zone.
  • The grid will not be empty.

Examples

1

Example 1

Input:

grid = [["1","1","0","R"],["0","1","0","1"],["1","0","R","1"]]

Output:

1

Note:

All '1's are reachable from each other by traversing through '1's and '0's, avoiding 'R' cells. For instance, the house at (0,0) can reach the house at (1,3) via a path like (0,0)->(0,1)->(0,2)->(1,2)->(1,3). All houses form a single large delivery zone.

2

Example 2

Input:

grid = [["1","0","0"],["0","R","0"],["0","0","1"]]

Output:

1

Note:

The house at (0,0) can reach the house at (2,2) by moving through the '0' cells, navigating around the 'R' cell at (1,1). Thus, they form a single delivery zone.

3

Example 3

Input:

grid = [["1","1","1"],["1","1","1"],["1","1","1"]]

Output:

1

Note:

All '1's are connected and can reach each other, forming a single large delivery zone.

Constraints

Constraints & assumptions

  • m is the number of rows, n is the number of columns in the grid.
  • 1 <= m, n <= 300
  • grid[i][j] will be either '1', '0', or 'R'.
  • The grid will always contain at least one row and one column.

What interviewers evaluate

  • Correctness of Algorithm: The solution correctly identifies and counts all distinct delivery zones according to the problem definition.
  • Graph Traversal Implementation: Effective use of BFS or DFS for exploring connected components in a grid.
  • Edge Case Handling: Proper handling of grid boundaries, restricted areas ('R'), and isolated houses ('1').
  • Time and Space Complexity: An efficient solution with optimal time and space complexity (O(M*N) for both).

Loading editor...