This post is completed by 3 users
|Add to List|
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.
[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
- This problem can be seen as the number of disconnected components in a given graph
- 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.
- 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.
Number of parking areas: 3
- All elements appears thrice and one element appears once. Find that element in O(n) time and O(1) space Hard