Consider the problem of finding, for a given input array, the longest subarray with at most two different values.
Input: [3,3,3,1,2,1,1,2,3,3,4] Ans = 5, the longest subarray would be [1,2,1,1,2]. Input: [1,2,3,2,2] Ans = 4, the longest subarray would be [2,3,2,2].
Below is dynamic programming solution to this problem (in Python, hopefully it's easy to read) using a sliding window that holds a "valid subarray" (the subarray of elements between indices
j always holds two values at most).
I read on e.g. LeetCode that this solution has a runtime complexity of $O(N)$ where $N$ is the length of the input array, but that's not immediately clear to me since we have two nested loops with $i$ and $j$ and $0\leq i\leq j\leq n$.
Why is the worst-case runtime complexity of this solution $O(N)$ and not $O(N^2)$?
Here's the DP solution in question with those nested loops holding a subarray between $i$ and $j$:
def longest_subarray_holding_two_diff_values (input_array): ans = i = 0 count = collections.Counter() for j, x in enumerate(input_array): count[x] += 1 while len(count) >= 3: count[input_array[i]] -= 1 if count[input_array[i]] == 0: del count[input_array[i]] i += 1 ans = max(ans, j - i + 1) return ans