Loading...
Linear-time techniques for subarray and pair-finding problems that naively look quadratic.
4 questions in Data Structures & Algorithms.
Every palindrome is fixed by its centre, and a string of length n has 2n minus 1 of them once the gaps between characters are counted. Expanding outwards from each is O(n squared) worst case in O(1) extra space, and the worst case is reached by a string of one repeated character, where the expansions from every centre run all the way to the boundary.
Maintain a sliding window with a map from character to its last seen index; when a duplicate appears inside the current window, jump the left boundary past that previous occurrence rather than shrinking one step at a time, giving a single-pass O(n) solution. It also connects two pointers to the point an interviewer is testing.
Sort the array, fix each element as an anchor, then converge two pointers inwards from both ends of the remaining range. The sort is asymptotically free against the O of n squared scan, and it is what lets you skip duplicate values positionally instead of deduplicating a set of results afterwards. It also connects sorting to the point an interviewer is testing.
Water above a bar is the smaller of the tallest bar to its left and the tallest to its right, minus its own height. Walking inwards from both ends and always advancing the shorter side works because that side's running maximum is the binding constraint there, whatever heights remain unseen in the middle.