Problem Brief

Counting Segments After House Removals

FULLTIMEOA

See Uber online assessment and hiring insights

You are given a list of house positions in a district, where each house is located at a distinct position along a straight line. Houses that are next to each other without any gaps between them are considered part of the same segment. Your task is to determine how many segments of consecutive houses remain after removing houses according to a series of queries.

Each query removes a house from the district, and after each removal, you need to calculate the number of segments of consecutive houses that remain.

Input:

houses: A list of integers representing the positions of the houses in the district.

queries: A list of integers representing the positions of the houses to be removed. Each query removes one house from the district.

Output:

For each query, return the number of segments of consecutive houses remaining after the corresponding house is removed.

ᯓᡣ𐭩spike is the G.O.A.T ᨒ ོ ☼

1Example 1

Input

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

Output

[3, 2, 2]

Explanation

Note - Example 1's output can potentially be wrong. Answer might be [3,3,3].

Initial Setup: Houses are at positions [1, 2, 3, 6, 7, 9], forming three segments: [1, 2, 3], [6, 7], and [9].

After removing house at position 6: Houses are [1, 2, 3, 7, 9], forming three segments: [1, 2, 3], [7], and [9]. Result = 3.

After removing house at position 3: Houses are [1, 2, 7, 9], forming two segments: [1, 2], [7], and [9]. Result = 2.

After removing house at position 1: Houses are [2, 7, 9], forming two segments: [2], [7], and [9]. Result = 2.

Thus, the output after each query is [3, 2, 2].

2Example 2

Input

houses = [1, 5, 6, 8, 10], queries = [5, 10, 1]

Output

[3, 3, 2]

Explanation

Caution - Example 2's output and explanation might be wrong. If you look at inital setup, they say there are 3 segments, but it might actually be 4.

Initial Setup: Houses are at positions [1, 5, 6, 8, 10], forming three segments: [1], [5, 6], and [8, 10].

After removing house at position 5: Houses are [1, 6, 8, 10], forming three segments: [1], [6], and [8, 10]. Result = 3.

After removing house at position 10: Houses are [1, 6, 8], forming three segments: [1], [6], and [8]. Result = 3.

After removing house at position 1: Houses are [6, 8], forming two segments: [6] and [8]. Result = 2.

Thus, the output after each query is [3, 3, 2].

Constraints

Limits and guarantees your solution can rely on.

The number of houses, n, is at most 10^5.

The number of queries, q, is at most 10^5.

All positions in the house list and queries list are distinct integers.