Skip to main content
Talentd

Count Houses in a Circular Street - Solution & Explanation

EasyPremiumFree on FleetCodeArrayInteractive5 min readAsked at: Google
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.

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 houses
  • 1 <= n <= k <= 103

Approach Overview

Problem 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.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulation with External Visited TrackingO(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

Video Solution

leetcode 2728. Count Houses in a Circular Street - method call and loop • Code-Yao • 281 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Count Houses in a Circular Street easy or hard?
Count Houses in a Circular Street is classified as an Easy problem on LeetCode with a high acceptance rate. The challenge is recognizing that the door state can act as a visited marker, allowing a single circular traversal without extra memory.
Count Houses in a Circular Street Python/Java solution
Both Python and Java implementations follow the same logic: check if the current door is open, close it, increment a counter, and move right. Repeat until a closed door is encountered. The algorithm remains O(n) time and O(1) space regardless of language.
How to solve Count Houses in a Circular Street in O(n)?
Start at the current house and check if the door is open. Close the door to mark the house as visited, increment a counter, and move right. Continue this process until you encounter a door that is already closed, which indicates you have returned to the starting house. The counter represents the total number of houses.
What is the best approach for Count Houses in a Circular Street?
The optimal approach is a simulation that marks visited houses by closing their doors. Since every door starts open, you close the door when you first visit a house and move right. When you encounter a closed door again, you know you completed one full circle. This runs in O(n) time with O(1) extra space.
Is Count Houses in a Circular Street asked at Google/Amazon/Meta?
Interactive traversal and environment-simulation problems appear in interviews at companies like Google and Meta, especially when testing reasoning about unknown-sized structures. While this exact problem is from LeetCode, the pattern of marking visited nodes during traversal is common in real interview questions.
What data structure is used in Count Houses in a Circular Street?
The solution does not rely on a traditional external data structure. Instead, it uses the environment's door state as a marker to track visited houses. Conceptually it behaves like traversing a circular array or linked structure while modifying node state.
What is the time complexity of Count Houses in a Circular Street?
The optimal solution runs in O(n) time where n is the number of houses. Each house is visited exactly once before the traversal returns to the starting point. The space complexity is O(1) because the algorithm uses the door state itself instead of external memory.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays