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.

Description Hints 3 Solution Video 9:04

2728. Count Houses in a Circular Street

Easy86.1% acceptance1 companyPremium elsewhere, free here

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 <= 10³

Asked at 1 company

Google

Topics

Array Interactive

Hints open one at a time

Hint 1

Close the door of k houses moving in one direction.

Hint 2

Open the door of the current house.

Hint 3

Move in one direction and count until you reach the house with the open door.

9:04

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[0,0,0,0]
10

Input

[1,0,1,1,0]
5

Your code is saved on this device.Solution