FastPrep
Problem · Array

Count House Segments After Destruction

Learn this problem
● MediumMatroid logoMatroidINTERNOA

Problem statement

You are monitoring building density in a district of houses. The district is represented as a number line, and each 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 that will be destroyed, in destruction order.

After each house is destroyed, find the number of house segments that remain. A house segment is a maximal group of one or more houses at consecutive integer positions. In other words, there is no remaining house immediately before or immediately after a segment.

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

Function

solution(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]

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

Constraints

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

More Matroid problems

drafts saved locally
public int[] solution(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