Skip to main content
Talentd

Count Houses in a Circular Street II - Solution & Explanation

HardPremiumFree on FleetCode9 min read
Practice this problem

Problem Statement

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 houses
  • 1 <= n <= k <= 105
  • street is 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.

Approach 1: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 2: Brain Teaser

We notice that there is at least one door open in the problem. We can first find one of the open doors.

Then, we skip this open door and move to the right. Each time we move, we increment a counter by one. If we encounter an open door, we close it. The answer is the value of the counter the last time we encounter an open door.

The time complexity is O(k), and the space complexity is O(1).

Related problem:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Default Approach—
Brain Teaser—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Circular Traversal with State TrackingO(n^2)O(n)Conceptual baseline when detecting cycles by storing visited states
Door State Marking TraversalO(n)O(1)Best approach when the environment allows modifying state to mark visited houses

Video Solution

How to EASILY solve LeetCode problems • NeetCode • 427,736 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Count Houses in a Circular Street II with our built-in code editor and test cases.

Practice on FleetCode