Count Houses in a Circular Street

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.

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.

Examples

Example 1:

1
2
3
4


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:

1
2
3
4


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^3

Solution

Method 1 – Mark and Move (Simulation)

Intuition

Since the street is circular and we can move left/right, we can mark each house as visited by opening its door, then move right until we return to the starting house. We count how many unique houses we visit by marking them (e.g., opening the door if it was closed, or closing if it was open) and checking when we complete a full circle.

Approach

Record the initial state of the starting house’s door.
Mark the starting house (e.g., open the door if closed, or close if open).
Move right, marking each new house, and count how many unique houses we visit until we return to the starting house (detected by the door state matching the initial state and all doors have been visited).
Stop when we return to the starting house and its state matches the initial state.
Return the count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


/**
 * // This is the Street's API interface.
 * class Street {
 * public:
 *     void openDoor();
 *     void closeDoor();
 *     bool isDoorOpen();
 *     void moveRight();
 *     void moveLeft();
 * };
 */
class Solution {
public:
    int houseCount(Street* street, int k) {
        int cnt = 0;
        bool first = street->isDoorOpen();
        street->openDoor();
        cnt++;
        for (int i = 1; i < k; ++i) {
            street->moveRight();
            if (!street->isDoorOpen()) {
                street->openDoor();
                cnt++;
            }
            if (street->isDoorOpen() && i > 1 && street->isDoorOpen() == first) break;
        }
        return cnt;
    }
};

1

// Not applicable (interactive problem)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


/**
 * // This is the Street's API interface.
 * class Street {
 *     void openDoor();
 *     void closeDoor();
 *     boolean isDoorOpen();
 *     void moveRight();
 *     void moveLeft();
 * }
 */
class Solution {
    public int houseCount(Street street, int k) {
        int cnt = 0;
        boolean first = street.isDoorOpen();
        street.openDoor();
        cnt++;
        for (int i = 1; i < k; i++) {
            street.moveRight();
            if (!street.isDoorOpen()) {
                street.openDoor();
                cnt++;
            }
            if (street.isDoorOpen() && i > 1 && street.isDoorOpen() == first) break;
        }
        return cnt;
    }
}

1

// Not applicable (interactive problem)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


# This is the Street's API interface.
# class Street:
#     def openDoor(self):
#     def closeDoor(self):
#     def isDoorOpen(self) -> bool:
#     def moveRight(self):
#     def moveLeft(self):
class Solution:
    def houseCount(self, street: 'Street', k: int) -> int:
        cnt = 0
        first = street.isDoorOpen()
        street.openDoor()
        cnt += 1
        for i in range(1, k):
            street.moveRight()
            if not street.isDoorOpen():
                street.openDoor()
                cnt += 1
            if street.isDoorOpen() and i > 1 and street.isDoorOpen() == first:
                break
        return cnt

1

// Not applicable (interactive problem)

1

// Not applicable (interactive problem)

Complexity

⏰ Time complexity: O(n), where n is the number of houses, as we may visit each house once.
🧺 Space complexity: O(1), only a constant amount of space is used.

Problem#

Examples#

Solution#

Method 1 – Mark and Move (Simulation)#

Intuition#

Approach#

Code#

Complexity#