FastPrep
Problem · Array

Count House Segments After Sequential Destruction

Learn this problem
● MediumByteDance logoByteDanceNEW GRADOA

Problem statement

Given an array houses of distinct integer house locations and an array queries of distinct locations that all appear in houses, destroy the queried houses in order.

A house segment is a maximal group of remaining houses at consecutive integer locations. After each destruction, record the number of remaining segments.

Return one segment count for every query, in query order.

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 two segments. Removing 6 preserves the segment count, and removing 2 leaves two segments.

Constraints

  • 1 <= houses.length <= 100000
  • 1 <= queries.length <= houses.length
  • -10^9 <= houses[i] <= 10^9
  • All values in houses are distinct.
  • Every value in queries appears in houses.
  • All values in queries are distinct.

More ByteDance 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