O(n) -> O(k)

[WenchaoD]

For this hunk:

if i - maxIdx.first! + 1 == k {
      maxIdx.removeFirst()
}

Same as:

if maxIdx.last! - maxIdx.first! + 1 == k {
      maxIdx.removeFirst()
}

As maxIdx.last! - maxIdx.first! + 1 is always less than or equal to maxIdx.count, and will poll the first element when it reachesk.
Such that : maxIdx.count is always less than or equal to k.

=> The space complexity is O(k), rather than O(n).

[soapyigu]

I get your point, but this is linear, so that I use "n" represents it

[WenchaoD]

Time is linear , which is correct as O(n), but space is O(k).

[WenchaoD]

O. I get what u mean. Thanks.