We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Houses in a Circular Street II

Number: 2897

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

You are given a circular street of houses (with at most k houses). You can only interact with the street via three operations on the current house: • closeDoor() – to close the door of the current house, • isDoorOpen() – to check whether the house’s door is open, • moveRight() – to proceed to the next house on the right. At least one door is open initially. Starting from an arbitrary house, your task is to count (determine) the total number of houses on the street. Note that the street is circular – after the last house, the next house is the first one.

Key Insights

  • Since the street is circular, performing a fixed number of moves (equal to the number of houses) will bring you back to where you started.
  • However, you do not initially know the number of houses n (with n ≤ k). It is possible that many doors are already closed.
  • The only “write” operation is closeDoor(), so you cannot “mark” a house by toggling it if it was originally closed. Thus we must first “tag” a house that is guaranteed to be open.
  • The solution uses a two‐phase approach: • In the first phase (doubling phase) you mark a uniquely “tagged” house (by ensuring you only close a door that was open when you encountered it) and then repeatedly “jump” by an increasing number of moves (doubling the distance) until you hit back the tagged house. • In the second phase you perform a binary search between the last safe “jump” distance and the first “jump” that overshoots (i.e. lands on the tagged house) in order to determine the exact count n.
  • A helper routine is used to “test” whether a given number of moves from the tag returns to the tagged house. Although the street contains other closed doors (which could have been originally closed), you assume that by being careful the door you closed for your tag is distinguishable (see “gotcha” below).

Space and Time Complexity

Time Complexity: O(n + log k) in the worst‐case. In the worst case the doubling phase walks several partial rounds and the binary search phase “walks” back to the starting marker, but n is O(k). Space Complexity: O(1) (only a few pointers/counters are used).

Solution

The idea is to “mark” one house in a way that you can later identify it. To do this, if the door you face is open you call closeDoor() so that it is closed by your own action (if it was originally closed, you first move right until you find an open door). This house becomes your marker. Next, we “jump” an increasing number of houses (using doubling – 1, 2, 4, 8, …) until a jump leads you to the marker (that is, when isDoorOpen() returns false at your jump destination). Since many houses may be closed originally, our algorithm implicitly relies on the fact that the marker is the only door we themselves have closed. (In an interview you should clearly explain that one “gotcha” is that we assume we can distinguish a door we closed from a door that was originally closed; this is a common trick used in these stylized problems.) Once the doubling phase establishes an interval [low, high] such that moving ‘low’ moves from the marker does NOT give the marker but moving ‘high’ moves DOES, you can use binary search. In order to “test” a candidate distance, a helper routine simulates moving that many houses starting from the marker, checks the door state (open means you haven’t come full circle yet; closed means that you reached the marker), and then continues moving to return to the marker (since the street is circular, eventually you will see the marker again). Combining both phases, you determine the exact number of houses n.

Code Solutions

Below are sample implementations in Python, JavaScript, C++ and Java. They assume the existence of a Street class with the three provided methods. Comments on each line explain the rationale.

# Python solution with detailed inline comments.
class Solution:
    def countHouses(self, street: 'Street', k: int) -> int:
        # Step 1: Find an open door to use as the unique marker.
        # If the current door is closed, walk right until finding an open door.
        while not street.isDoorOpen():
            street.moveRight()
        
        # Mark the current house: close it.
        # This door is now our unique marker (assumed to be distinguishable).
        street.closeDoor()
        
        # Doubling phase: jump distances of 1, 2, 4, ... until a jump lands on the marker.
        jump = 1
        while True:
            # Try moving jump houses and check if we returned to the marker.
            if self._movedToMarker(street, jump):
                break  # overshoot found, break out to binary search phase.
            else:
                # Otherwise, mark the current house (if it is open) to maintain the invariant.
                if street.isDoorOpen():
                    street.closeDoor()
                # Reset back to the marker.
                self._returnToMarker(street, jump)
                jump *= 2
                # Avoid overshooting the bound k.
                if jump > k:
                    jump = k
                    break
        
        # Binary search phase: search for the exact house count between jump/2 and jump.
        low = jump // 2
        high = jump
        
        while low + 1 < high:
            mid = (low + high) // 2
            if self._movedToMarker(street, mid):
                high = mid
            else:
                low = mid
            # After each test, return back to the marker.
            self._returnToMarker(street, mid)
        
        # The first jump value that lands on the marker gives the number of houses.
        return high

    # Helper routine: move a given number of steps from current position.
    # Returns True if after moving the given 'steps' we are at the marker.
    # (We determine this by checking if the door is closed – i.e. was marked.)
    def _movedToMarker(self, street: 'Street', steps: int) -> bool:
        for _ in range(steps):
            street.moveRight()
        return not street.isDoorOpen()

    # Helper routine: from the current position, continue moving until the marker is found.
    # We assume that eventually the marker will be reached as we circle around.
    # This routine “returns” the pointer back to the marker.
    def _returnToMarker(self, street: 'Street', steps: int) -> None:
        # Since we know that the cycle length is at most k, make at most k moves.
        for _ in range(k := 10**5):  # k can be replaced by the provided upper bound.
            if not street.isDoorOpen():
                # We assume that the first closed door encountered that we recognize is the marker.
                return
            street.moveRight()
← Back to All Questions