I recently just encountered a leetcode style programming problem and I was wondering what the most optimal way to solve it is. The question goes like this:
Given an array of houses like houses = [1,2,3,7,8,10,11] and an array of queries like q=[2,10,8], return an array of how many segments exist after each query. Each query indicates the house that will be destroyed and the queries are executed in order.
A segment refers to a consecutive group of houses. There can technically be one house in a segment if there are no other house that are consecutive to it(it doesn't have neighbors), however it is still one segment.
Ex. houses->[None,house,house,house,None,None,None,house,house,None,house,house]
As can be seen the house indexes match up. Before any queries there are 3 segments(they are bolded) After the first query, the house at index 2 will be destroyed.
[None,house,None,house,None,None,None,house,house,None,house,house]
Now there are 4 segments, which means res=[4]
After the next query, house 10 is destroyed.
[None,house,None,house,None,None,None,house,house,None,None,house]
There are still 4 segments which. means res=[4,4]
After the last query, house 8 is destroyed.
[None,house,None,house,None,None,None,house,None,None,None,house]
There are still 4 segments which mean res=[4,4,4]
The array returned from this is [4,4,4]
I was wondering what the most optimal way to approach this problem is. My take was to construct a boolean array from 0 to maximum element in houses and make the indices that have a house on them True and the indices which don't have a house False. After this for each query we can just check that index and check how many neighbors it has. If it has 0 neighbors, then the number of segments decreases by 1, if it has 1 neighbor, then it stays the same, and if it has 2 then the number of segment increases by one. This approach allows me to process queries in O(1) but it is not very space efficient since we could have a house that lies at a very large index, Ex. houses=[1,1000000]. Is there a better approach to this problem? Thank you in advance.
Your solution is right but your problem of using enormous amount of space for finding in O(1) can be solved with HashMap
Make a HashMap between the house number to the Index within the array and for each query ask if the HashMap contains the number of the query, if it does just ask for the index and use your neighbor logic on the original array instead of the boolean array.
If you have multiple houses with the same number in the array use HashMap between the numer to a list of indexes with the same logic, just iterate on the list instead of the single house.
this solution has O(|houses| + |queries|) time complexity and O(|houses|) space complexity