FastPrepCount House Segments After Destruction

Count House Segments After Destruction

TikTok logoTikTok● MediumINTERNNEW GRADOA
Learn

Problem statement

You are monitoring building density in a district represented as a number line. Every house is located at an integer position.

You are given houses, an array containing the initial locations of all houses, and queries, an array containing the locations of houses destroyed in order. After each destruction, count the house segments that remain.

A house segment is one or more houses at consecutive integer positions, with no house immediately before or immediately after the segment.

Return an array whose i-th value is the number of remaining house segments after destroying the house at queries[i].

Function

countHouseSegmentsAfterDestruction(houses: int[], queries: int[]) → int[]

Examples

Example 1

houses = [1,2,3,6,7,9]queries = [6,3,7,2,9,1]return = [3,3,2,2,1,0]

Initially the segments are [1,2,3], [6,7], and [9]. Removing the houses in query order leaves 3, 3, 2, 2, 1, and finally 0 segments.

Example 2

houses = [2,4,5,6,7]queries = [5,6,2]return = [3,3,2]

Removing 5 splits [4,5,6,7] into [4] and [6,7], so three segments remain together with [2]. Removing 6 keeps three segments, and removing 2 leaves two.

Example 3

houses = [-1,0,1,5]queries = [0,5]return = [3,2]

Destroying the middle house at 0 splits [-1,0,1] into two single-house segments while [5] remains, giving 3. Removing 5 then leaves the two single-house segments.

Constraints

  • All values in houses are distinct.
  • Every value in queries appears in houses.
  • All values in queries are distinct.

More TikTok problems

See TikTok hiring insights
public int[] countHouseSegmentsAfterDestruction(int[] houses, int[] queries) {
    // Write your code here.
}
houses[1,2,3,6,7,9]
queries[6,3,7,2,9,1]
expected[3,3,2,2,1,0]
Checking account…