What about lazy evaluation though? That could get the functions 2*A memory down to just A while still keeping the time O(n)¹ Of course, maybe the author just c

What about lazy evaluation though? That could get the functions 2*A memory down to just A while still keeping the time O(n)¹ Of course, maybe the author just chose to limit this blog post to this one solution, but it wouldn't have hurt to at least mention some further optimizations :) ¹ And some O(1) data like the min and max values of the Array