LC: Shortest Distance to Target Color - spiralgo/algorithms GitHub Wiki

Shortest Distance to Target Color

The Essence:

The color indices are given to the program method at call time. This can be used to preprocess the indices. The preprocessing can be used to search through the indices in a sorted way, or to directly find which index is the closest.

Details:

For the searching, simple binary searches can be used.

At any index, the closest of each color is the minimum of the closest left and the closest right. This can be implemented in linear time by first looping through the colors array incrementally, then decrementally. After that, we have an array as a lookup table for all possible colors and indices that the query may offer. Each look up is thus done in constant time.

The code to both approaches can be found here.