You're doing reduce(...) // reduce(...) for i in range(...), that's a nested loop, hence O(n^2).

You should post your solution in a comment so it could be reviewed. Maybe you're missing something, and your algorithm is not actually linear.

Your second approach is correct, but the overall algorithm is bad. You have to make it fully linear.