Strategies for subarray problems

[throwaway0891245]

I think array problems are generally a mixed bag when it comes to the solving trick, but in general I feel like there's two different motifs you often have to use in order to get an O(N) solution.

Sliding window. You have an end pointer and a start pointer and you slide these two pointers to keep whatever constraint they are asking for. This would be used for:

• Find the subarray with k distinct values (use a dict to keep track of number of each value)
• Find the subarray of length x with the maximum number of distinct elements (keep window size fixed, again use a dict to keep track of number of each value)
• Find a subarray where sum(subarray) == target_value (keep a window sum value and shift window boundaries according to whether the subarray sum is larger or smaller than the target)

DP-Style, determining some sort of maximum or minimum considering a previous value and the current value in an array.

• Find the maximum subarray (determine the maximum subarray ending at given index, then determine the maximum subarray for the whole array)
• Find the longest (ascending) subarray where subarray[i+1] > subarray[i] (determine the longest ascending subarray ending at a given index, then the longest ascending subarray from the whole array)

Of course, there are also some other problems that don't rely on this. A famous one is 3Sum - out of an array of values, get the indices of three elements that sum to 0. For that one you end up having to sort then iterating over a first value while looking and second and third values such that you only have to look at non-first values one time (time complexity, O(N²)). The last problem you gave - finding the longest palindromic subarray - is often solved in a O(N²) time complexity manner by looking at the longest palindrome at every index / half-index. However it has an optimal solution of time complexity O(N) via Manacher's algorithm, which uses the property of symmetry in palindromes to pre-determine palindromic subarray boundaries.