FastPrep
Problem · Array

Count House Segments After Destruction

Learn this problem
● MediumTiktok logoTiktokINTERNOA
See Tiktok hiring insights

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

drafts saved locally
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