Watch 4 video solutions for Count Houses in a Circular Street, a easy level problem involving Array, Interactive. This walkthrough by Code-Yao has 274 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an object street of class Street that represents a circular street and a positive integer k which represents a maximum bound for the number of houses in that street (in other words, the number of houses is less than or equal to k). Houses' doors could be open or closed initially.
Initially, you are standing in front of a door to a house on this street. Your task is to count the number of houses in the street.
The class Street contains the following functions which may help you:
void openDoor(): Open the door of the house you are in front of.void closeDoor(): Close the door of the house you are in front of.boolean isDoorOpen(): Returns true if the door of the current house is open and false otherwise.void moveRight(): Move to the right house.void moveLeft(): Move to the left house.Return ans which represents the number of houses on this street.
Example 1:
Input: street = [0,0,0,0], k = 10 Output: 4 Explanation: There are 4 houses, and all their doors are closed. The number of houses is less than k, which is 10.
Example 2:
Input: street = [1,0,1,1,0], k = 5 Output: 5 Explanation: There are 5 houses, and the doors of the 1st, 3rd, and 4th house (moving in the right direction) are open, and the rest are closed. The number of houses is equal to k, which is 5.
Constraints:
n == number of houses1 <= n <= k <= 103Problem Overview: You interact with a circular street where each house has a door that is initially open. The API lets you check if the current door is open, close it, and move left or right. The task is to determine how many houses exist in the circle without knowing the size beforehand.
Approach 1: Simulation with Door Marking (O(n) time, O(1) space)
The key idea is to use the door state as a visitation marker. Since every door starts open, you can close a door when you first visit that house. Begin at the current house, check if the door is open, then closeDoor() to mark it as visited and move right using moveRight(). Keep a counter for each house you process.
Eventually you return to the starting house because the street is circular. When that happens, the door will already be closed, which signals that you have completed a full loop. The counter at that moment equals the number of houses in the street.
This approach works because the door state provides persistent information across moves. Instead of storing visited indices in memory, you mutate the environment itself. The algorithm performs exactly one traversal of the circle, so the runtime is O(n) where n is the number of houses, and it uses O(1) extra space.
Conceptually this is a classic interactive simulation problem. You repeatedly query the environment (isDoorOpen()) and update it (closeDoor()) while navigating the structure using pointer-like moves. The circular structure means termination depends on detecting a previously visited node rather than reaching an end. Problems with similar patterns often appear under array traversal and interactive problem categories.
Recommended for interviews: The door-marking simulation is the expected solution. A brute-force strategy would require external memory to track visited houses, but interviewers prefer the O(1) space solution that leverages the door state itself. It demonstrates awareness of how to encode state directly in the system you are traversing.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation with External Visited Tracking | O(n) | O(n) | Conceptual approach if door states cannot be modified |
| Simulation with Door Marking (Optimal) | O(n) | O(1) | Best approach when the API allows modifying door state to mark visited houses |