Consider the problem of finding, for a given input array, the longest subarray with at most two different values.
For example:
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 i
and 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