Shortest Distance to Character (Queue)

To solve the Shortest Distance to Character problem efficiently, I would first clarify that we need an O(N) solution since Netflix handles massive datasets. A naive approach checking every character against every occurrence of C would be O(N*K), which is inefficient. Instead, I propose a Two-Pass Linear Scan method. First, I initialize an answer array with infinity. In the forward pass, I track the most recent index of C encountered. For each position, the distance is simply the current index minus that stored index. If no C has been seen yet, the distance remains infinity. Next, I perform a backward pass. I reset the tracker to the end of the string and move backwards, updating the distance by taking the minimum of the current value and the distance from the nearest C found in this reverse direction. This ensures every element holds the shortest distance to either the previous or next C. For example, given 'love' and 'o', the forward pass sets distances based on 'o', and the backward pass corrects any remaining large values. This approach guarantees O(N) time and O(1) extra space excluding the output array, aligning perfectly with the performance standards expected at Netflix.