I'll never understand why beginners try to shoehorn cs101 everywhere. Changing data types doesn't affect Big-O complexity. And trying to speed up things based on general rules without benchmarking just leads to complex and slow code.
Yes, memory allocations take time, but when you are using python, everything takes time. It's a very slow language. Keeping the no. of interpreted steps to a minimum will often outspeed lower memory allocations.
Here's a fun exercise. Try benchmarking my solution and yours.

ok, so, as usual, this is context dependent...

I'm curious to know why it would be so..........