Count Houses in a Circular Street II solution and explanation
2 more videos on this problem
leetcode 2728. Count Houses in a Circular Street - method call and loopCode-Yao · 9:04 · 234 views
Day 606 - Teaching Kids Programming - Algorithms to Count Houses in a Circular StreetDoctor Lai · 12:26 · 221 views
#LeetCode 2728 | Count Houses in a Circular Street #JavaSleepy Cracker · 2:18 · 19 views
The problem
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(): Returnstrueif the door of the current house is open andfalseotherwise.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 <= 105streetis circular by definition provided in the statement.- The input is generated such that at least one of the doors is open.
Approach overview
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.
Solution
# Definition for a street.
# class Street:
# def closeDoor(self):
# pass
# def isDoorOpen(self):
# pass
# def moveRight(self):
# pass
class Solution:
def houseCount(self, street: Optional["Street"], k: int) -> int:
while not street.isDoorOpen():
street.moveRight()
for i in range(1, k + 1):
street.moveRight()
if street.isDoorOpen():
ans = i
street.closeDoor()
return ans/**
* Definition for a street.
* class Street {
* public Street(int[] doors);
* public void closeDoor();
* public boolean isDoorOpen();
* public void moveRight();
* }
*/
class Solution {
public int houseCount(Street street, int k) {
while (!street.isDoorOpen()) {
street.moveRight();
}
int ans = 0;
for (int i = 1; i <= k; ++i) {
street.moveRight();
if (street.isDoorOpen()) {
ans = i;
street.closeDoor();
}
}
return ans;
}
}/**
* Definition for a street.
* class Street {
* public:
* Street(vector<int> doors);
* void closeDoor();
* bool isDoorOpen();
* void moveRight();
* };
*/
class Solution {
public:
int houseCount(Street* street, int k) {
while (!street->isDoorOpen()) {
street->moveRight();
}
int ans = 0;
for (int i = 1; i <= k; ++i) {
street->moveRight();
if (street->isDoorOpen()) {
ans = i;
street->closeDoor();
}
}
return ans;
}
};/**
* Definition for a street.
* class Street {
* constructor(doors: number[]);
* public closeDoor(): void;
* public isDoorOpen(): boolean;
* public moveRight(): void;
* }
*/
function houseCount(street: Street | null, k: number): number {
while (!street.isDoorOpen()) {
street.moveRight();
}
let ans = 0;
for (let i = 1; i <= k; ++i) {
street.moveRight();
if (street.isDoorOpen()) {
ans = i;
street.closeDoor();
}
}
return ans;
}/**
* Definition for a street.
* type Street interface {
* CloseDoor()
* IsDoorOpen() bool
* MoveRight()
* }
*/
func houseCount(street Street, k int) (ans int) {
for !street.IsDoorOpen() {
street.MoveRight()
}
for i := 1; i <= k; i++ {
street.MoveRight()
if street.IsDoorOpen() {
ans = i
street.CloseDoor()
}
}
return
}Complexity analysis
| 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 |
Frequently asked questions
Is Count Houses in a Circular Street II easy or hard?
The problem is classified as Hard because the street size is unknown and the structure is circular. The challenge is recognizing that you can modify the door state to mark the starting point and detect when a full loop is completed without using extra memory.
Count Houses in a Circular Street II Python/Java solution
Implement the traversal using the provided street API. Modify the starting door state, move through the circular street while counting houses, and stop when the starting configuration is detected again. The same logic works in Python, Java, C++, Go, and TypeScript because the algorithm relies only on API calls and simple counters.
How to solve Count Houses in a Circular Street II in O(n)?
Start at an arbitrary house and change its door state to create a unique marker. Move around the circular street one house at a time while counting visits and normalizing states. When the traversal returns to the marked house, the counter equals the total number of houses, giving an O(n) solution with constant memory.
What is the best approach for Count Houses in a Circular Street II?
The most efficient solution uses door state marking while traversing the circular street once. Modify the starting house's door state, walk house by house, and count steps until you encounter the modified state again. This approach runs in O(n) time and uses O(1) extra space.
Is Count Houses in a Circular Street II asked at Google/Amazon/Meta?
Problems involving hidden environments and circular traversal patterns are common in interviews at companies like Google and Amazon. Variants test your ability to detect cycles, simulate movement through an API, and mark visited nodes without additional memory.
What data structure is used in Count Houses in a Circular Street II?
The optimal solution does not rely on external data structures. Instead, it uses the door state of each house as an in-place marker during traversal. Conceptually, the problem resembles graph traversal or simulation over an implicit circular structure.
What is the time complexity of Count Houses in a Circular Street II?
The optimal algorithm runs in O(n) time where n is the number of houses in the circular street. Each house is visited exactly once during the traversal. The space complexity is O(1) because the door state itself is used as the visitation marker.