Watch 10 video solutions for Count Houses in a Circular Street II, a hard level problem. This walkthrough by NeetCode has 427,736 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 (at least one is open).
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 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.Note that by circular street, we mean if you number the houses from 1 to n, then the right house of housei is housei+1 for i < n, and the right house of housen is house1.
Return ans which represents the number of houses on this street.
Example 1:
Input: street = [1,1,1,1], k = 10 Output: 4 Explanation: There are 4 houses, and all their doors are open. 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 <= 105street is circular by definition provided in the statement.Problem Overview: You are given access to a circular street through an API that lets you move left or right and check or modify whether a house door is open or closed. The total number of houses is unknown. The task is to determine exactly how many houses exist in the circular street.
Approach 1: Brute Force Circular Traversal with State Tracking (O(n^2) time, O(n) space)
A straightforward idea is to walk around the street and record the door state of every house you encounter. Because the street is circular and the total count is unknown, you continue moving until you detect that you have returned to the starting configuration. Store visited states in a set or list and compare configurations after each full traversal. This approach works conceptually but performs repeated checks and state comparisons, which increases the cost. It also requires extra memory to store previously observed states.
Approach 2: Door State Marking with Single Circular Walk (O(n) time, O(1) space)
The optimal strategy uses the door state as an in-place marker. Start at an arbitrary house and change its door state (for example, close it if it is open). Then move step by step around the street using the provided movement API. For each house visited, increment a counter and normalize its state so you can recognize when you have completed the loop. Once you return to the starting house and detect the modified state you created earlier, you know a full cycle has been completed. Because each house is processed exactly once during the traversal, the total work is linear.
This technique relies on careful simulation of the environment and controlled mutation of the door state. Instead of storing visited nodes externally, the algorithm encodes visitation directly in the system state. Problems like this often fall under simulation and environment traversal patterns commonly seen in graph traversal problems where the structure is implicit.
Recommended for interviews: The door-marking traversal is the expected solution. It demonstrates that you can reason about circular structures with unknown length and use constant-space marking instead of external storage. Mentioning the brute force approach first shows understanding of the circular detection challenge, but the O(n) simulation approach is what interviewers look for.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Circular Traversal with State Tracking | O(n^2) | O(n) | Conceptual baseline when detecting cycles by storing visited states |
| Door State Marking Traversal | O(n) | O(1) | Best approach when the environment allows modifying state to mark visited houses |