Count House Segments After Sequential Demolitions

Problem

Distinct houses occupy integer positions on a number line. Houses at consecutive positions belong to the same segment. Remove houses in the given query order and return the number of remaining segments after each removal.

Function Contract

Implement segment_counts_after_removals(houses, queries) -> list[int].

Constraints

• 1 <= len(houses) <= 200000 and all positions are distinct.
• Every query position occurs in houses, and query positions are distinct.
• 1 <= len(queries) <= len(houses).
• House positions are integers in [-10^9, 10^9].

Examples

• houses = [1,2,3,6,7,9], queries = [6,3,7,2,9,1] returns [3,3,2,2,1,0].
• Removing the only house returns [0].

Hint: Inspect immediate neighbors

Removing one active house changes only the adjacency relationships with positions one less and one greater.

Hint: Or process in reverse

Adding queried houses back in reverse turns deletion into a union operation; remember that houses never queried remain active initially.

Edge Cases

• Removing an isolated house reduces the segment count by one.
• Removing the middle of a segment splits it into two and increases the count by one.
• Removing an endpoint leaves the number of segments unchanged unless it was a one-house segment.

Count House Segments After Sequential Demolitions

Hints

1. Removing one active house changes only its adjacency to positions one less and one greater.
2. Classify the removed house as a middle, endpoint, or isolated house from those two membership checks.

Approach

Store active positions in a hash set and count initial segments by counting active houses whose position minus one is absent. Removing one house can affect only its immediate neighbors. If both neighbors are active, one segment splits into two and the count increases by one. If neither is active, a singleton segment disappears and the count decreases by one. If exactly one neighbor is active, an endpoint is removed and the segment count is unchanged. Remove the position and append the updated count for every query.

• Time complexity: O(n + q) expected time for n houses and q removals.
• Space complexity: O(n) for the active-position set and result.