Editorial for The New Kid


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: Plasmatic

For the purpose of this editorial, houses that contain people Jagdeep doesn't like will be known as 'bad houses'

First, note that for each empty house, the only bad houses that matter are the ones that are the closest to them.

We can sort the list of bad houses and then binary search for the location of each empty house. This gets the index to the first bad house with a location greater than that of said house. We can then just subtract the index by one to get the other closest bad house.

Now, finding the empty house furthest away from a bad house is now easy, we just need to find the one with the maximum distance away from its closest bad houses.

Note: for the binary search, you will have to account for cases where the binary search returns the first or last index.

Time Complexity: \mathcal O(NlogN)


Comments

There are no comments at the moment.