Return to Answer

Given that we already know the size of the output array, we don't even need to scan for where the sign change happens, since we can fill it in in reverse. Simply init i & j to start and end, and do 2-way merge inward, emitting squares as you go. At some point the two indexes will locate where the sign change is, and then we're done.

Given that we already know the size of the output array, we don't even need to scan for where the sign change happens, since we can fill it in in reverse. Simply init i & j to start and end, and do 2-way merge inward, emitting squares as you go, in reverse order. At some point the two indexes will locate where the sign change is, and then we're done.

There are at most 10_000 elements, and their absolute values shall be at most 10_000. It's not hard to allocate a container of that size. Simply store absolute values of the inputs, and then read them out in sequence. No \$\log n\$ term involved at all. Is this cheating? Yes. Kind of. The key is to figure out the rules, and play within them.

Given that we already know the size of the output array, we don't even need to scan for where the sign change happens, since we can fill it in in reverse. Simply init i & j to start and end, and do 2-way merge inward, emitting squares as you go. At some point the two indexes will locate where the sign change is, and then we're done.

There are at most 10_000 elements, and their absolute values shall be at most 10_000. It's not hard to allocate a container of that size. Simply store absolute values of the inputs, and then read them out in sequence. No \$\log n\$ term involved at all. Is this cheating? Yes. Kind of. The key is to figure out the rules, and play within them. (And benchmark against the previous approach. Which this won't be competitive with, for most input sizes.)

The i and j indexes were great, but these two are terrible terrible identifiers. Pick a name that show what they mean, or at least offer a # comment to help out the Gentle Reader. The and k!=k1 conjunct suggests that you have some loop invariant in mind, but you didn't go to the trouble of telling us what it is, how it relates to the business problem at hand.

The if k < (n-1)//2: loop offers another fruitful opportunity to Extract Helper. Minimally you get to def foo() where "foo" usefully describes what's happening. Ideally you would add a """docstring""" that offers further details.

The i and j indexes were great, but these two are terrible terrible identifiers. Pick names that show what they mean, or at least offer a # comment to help out the Gentle Reader. The and k!=k1 conjunct suggests that you have some loop invariant in mind, but you didn't go to the trouble of telling us what it is, how it relates to the business problem at hand.

The if k < (n-1)//2: loop offers another fruitful opportunity to Extract Helper. Minimally you get to def foo() where "foo" usefully describes what's happening. Ideally you would add a """docstring""" that offers further details.

Recall that the bisect module stands at the ready to help with many of your binary search needs.