LeetCode 2728 - Count Houses in a Circular Street

The problem asks us to determine the number of houses on a circular street where we can only interact with the street through the provided Street interface. Each house has a door that can either be open or closed.

leetcodeeasyarrayinteractive

LeetCode Problem 2728

Difficulty: 🟢 Easy
Topics: Array, Interactive

Solution

Problem Understanding

The problem asks us to determine the number of houses on a circular street where we can only interact with the street through the provided Street interface. Each house has a door that can either be open or closed. We are initially positioned in front of one house, but we do not know which one, and the street is circular, meaning moving right repeatedly eventually brings us back to the starting house.

The input consists of an object street implementing specific methods to open, close, check, and move between doors. We are also given a positive integer k, which serves as an upper bound for the number of houses; the actual number of houses n satisfies 1 <= n <= k <= 103.

The output is a single integer, ans, representing the exact number of houses on the street. Because the street is circular and doors may be initially open or closed, naive counting methods (like counting open doors only) will fail. Instead, we must rely on interaction patterns to identify the full cycle without ambiguity.

Important edge cases include a street with only one house, all doors initially open, all doors initially closed, and the maximum bound k being equal to n. The problem guarantees that the street has at least one house and that k is not smaller than the number of houses.

Approaches

The most straightforward approach is to attempt to traverse the street while marking visited houses using the door state. Since we can modify doors, we can use them as markers. For instance, we can open a door to mark it as visited and move right, counting houses until we reach a door we previously opened. Because the street is circular, this ensures that we eventually return to the starting point.

The key insight is that opening a door temporarily and returning to a previously opened door uniquely identifies the completion of one full cycle. This allows counting the number of houses without external memory or arrays. Once we have counted n houses, we restore the initial state to avoid side effects if required.

Approach Time Complexity Space Complexity Notes
Brute Force O(k²) O(k) Marking each house externally using a list or map and moving around until all houses are marked. Redundant moves make it inefficient.
Optimal O(n) O(1) Use the door states themselves to mark visited houses. Move in one direction until we encounter a previously marked door. Only requires constant extra space.

Algorithm Walkthrough

  1. Start at the current house. Record whether the door is initially open or closed. This allows restoring the original state at the end.
  2. If the door is closed, open it to mark this house as visited. If it is already open, temporarily close it to mark the starting point for traversal.
  3. Initialize a counter count to 1, representing the first house.
  4. Move to the next house to the right.
  5. Check the door state of the current house:
  • If the door is unmarked (different from the initial marking logic), increment the counter and mark it (open or close, opposite of initial state).
  • If the door is already marked (matches the marking pattern from step 2), we have completed one full cycle. Stop traversal.
  1. Restore the initial door state of all modified doors if required (optional depending on problem constraints).
  2. Return the counter count, which now represents the total number of houses on the street.

Why it works

By using the door state as a marker, we ensure that each house is counted exactly once. Because the street is circular, the traversal eventually returns to a previously marked door, guaranteeing that we have traversed all houses without needing extra space.

Python Solution

from typing import Optional

# Definition for a street.
# class Street:
#     def openDoor(self):
#         pass
#     def closeDoor(self):
#         pass
#     def isDoorOpen(self):
#         pass
#     def moveRight(self):
#         pass
#     def moveLeft(self):
#         pass

class Solution:
    def houseCount(self, street: Optional['Street'], k: int) -> int:
        if street is None:
            return 0

        # Check initial state
        initial_open = street.isDoorOpen()
        # Mark the starting house
        street.openDoor() if not initial_open else street.closeDoor()
        count = 1

        while True:
            street.moveRight()
            if street.isDoorOpen() != initial_open:
                # Unvisited house, mark it
                street.openDoor() if initial_open else street.closeDoor()
                count += 1
            else:
                # Back to starting house
                break

        # Restore starting house state
        if initial_open != street.isDoorOpen():
            street.openDoor() if initial_open else street.closeDoor()

        return count

Implementation Walkthrough

We first check the initial door state to remember whether it was open or closed. We then mark the starting house to signal it has been visited. Using a loop, we move right and mark unvisited houses, incrementing a counter. The loop terminates when we return to a house with the original marking pattern. Finally, we restore the initial state of the starting house.

Go Solution

/**
 * Definition for a street.
 * type Street interface {
 *     OpenDoor()
 *     CloseDoor()
 *     IsDoorOpen() bool
 *     MoveRight()
 *     MoveLeft()
 * }
 */
func houseCount(street Street, k int) int {
    if street == nil {
        return 0
    }

    initialOpen := street.IsDoorOpen()
    // Mark the starting house
    if !initialOpen {
        street.OpenDoor()
    } else {
        street.CloseDoor()
    }
    count := 1

    for {
        street.MoveRight()
        if street.IsDoorOpen() != initialOpen {
            // Unvisited house, mark it
            if initialOpen {
                street.CloseDoor()
            } else {
                street.OpenDoor()
            }
            count++
        } else {
            // Back to starting house
            break
        }
    }

    // Restore starting house state
    if street.IsDoorOpen() != initialOpen {
        if initialOpen {
            street.OpenDoor()
        } else {
            street.CloseDoor()
        }
    }

    return count
}

Go-specific Notes

Go implementation closely mirrors Python. The key difference is handling the interface nil check and explicit method calls on the Street interface. There are no concerns about Python’s Optional type, and state restoration uses simple boolean checks.

Worked Examples

Example 1: street = [0,0,0,0], k = 10

Initial house is closed. Open it (mark). Move right, see closed → mark → count = 2. Next house closed → mark → count = 3. Next house closed → mark → count = 4. Next house closed matches starting house → break. Result = 4.

Example 2: street = [1,0,1,1,0], k = 5

Initial house open → close to mark. Move right → closed → mark → count = 2. Next → open → mark → count = 3. Next → open → mark → count = 4. Next → closed → mark → count = 5. Next → back to starting house → break. Result = 5.

Step Current House Door State Count Action
0 0 closed 1 open (mark)
1 1 closed 2 open (mark)
2 2 closed 3 open (mark)
3 3 closed 4 open (mark)
4 0 closed 4 break

Complexity Analysis

Measure Complexity Explanation
Time O(n) We visit each house exactly once, moving right each time.
Space O(1) Only a few boolean variables and counters are used; no extra storage proportional to n.

Even though k is given, the algorithm only depends on the actual number of houses n, making it efficient for all allowed bounds.

Test Cases

# Provided examples
assert Solution().houseCount(Street([0,0,0,0]), 10) == 4  # all doors closed
assert Solution().houseCount(Street([1,0,1,1,0]), 5) == 5  # mixed doors

# Single house
assert Solution().houseCount(Street([0]), 1) == 1
assert Solution().houseCount(Street([1]), 1) == 1

# All doors open
assert Solution().houseCount(Street([1,1,1,1,1]), 10) == 5

# Maximum k
assert Solution().houseCount(Street([0]*103), 103) == 103

# Alternating doors
assert Solution().houseCount(Street([0,1,0,1,0,1]), 6) == 6
Test Why
[0,0,0,0] all closed doors, verifies marking works
[1,0,1,1,0] mixed state, checks traversal logic
[0] and [1] single house edge case
`[1,1,1,1