Katkat
Back

Count House Segments After Sequential Demolitions

ByteDanceSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Track the number of consecutive house segments after each requested demolition on an integer line. Each removal can eliminate an isolated segment, trim an endpoint, or split a run, so the solution must update the count efficiently across many distinct positions.

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].

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.

Hints

Hint 1

Inspect immediate neighbors: Removing one active house changes only the adjacency relationships with positions one less and one greater.

Hint 2

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