So, I am currently learning about closest pair algorithms and found this problem in a text book: Assume you have a sorrted Array of length n that contains one Dimensional points (integers) and are coloured. Now you want to find the closest pair of two points of different colours (either red or blue). How would you do that in O(n)? Since the closest pair of points problem is usually using a divide and conquer algorithm I was wondering whether someone has an idea on how to solve this?
I found a solution using two pointers, but no d&C solution.
You mentioned in a comment that there are only two colours, red and blue.
If we could use a divide-and-conquer approach, it would give a O(logn) solution. I don't think it is possible. However, there is a rather simple O(n) solution. We just have to memorize the value/index of last blue and red samples.
It the last read element is blue (resp. red), we calculate its distance from the last red (resp. blue) element. We then compare the result with the previous minimum distance.
Note: if the number of colours were higher, there is still a simple O(n) approach by using a stack. I originally prepared such a solution, before knowing there are only two colours.