FastPrepCount House Segments After Destruction
Problem · Union Find

Count House Segments After Destruction

Learn this problem
● MediumCapital One logoCapital OneFULLTIMEOA

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 destroyed in order. After each destroyed house, return the number of house segments remaining.

A house segment is one or more adjacent houses whose positions are consecutive integers and which do not have neighboring houses immediately outside the segment.

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 house segments are [1, 2, 3], [6, 7], and [9]. Removing the houses in query order leaves 3, 3, 2, 2, 1, and then 0 segments.

Example 2

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

After removing 5, the segments are [2], [4], and [6, 7]. After removing 6, the segments are [2], [4], and [7]. After removing 2, two segments remain.

Constraints

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

More Capital One 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