This post is completed by 3 users

  • 1
 Add to List
Medium

509. Find the Number of Contiguous Parking Areas

Problem: Given a building with parking slots. If a spot is free then it is marked by 1 and if the spot is taken by a vehicle then it is marked by 0. Write a program to find the number of free contiguous parking areas in the building. One free parking area can have one or more parking spots.

Example:

[1, 1, 0, 0]
[0, 0, 0, 0]
[0, 0, 1, 1]
[0, 0, 0, 1]
Output: 2

[1, 1, 0, 0]
[0, 0, 0, 0]
[1, 0, 1, 1]
[1, 0, 0, 0]
Output: 3

Approach: Depth-First Search

  1. This problem can be seen as the number of disconnected components in a given graph
  2. So the idea is to run the Depth-First Search (DFS) in the grid. If the grid is fully connected then it will be visited in one iteration.
  3. Else the number of times we need to run DFS, will be the number of connected components, which is equal to our answer - number of free parking areas.

Output:

Number of parking areas: 3

Related Problems: