We check whichever left or right square is largest and add it to the end of the result array.
Why dont we check the smallest square between the left and right and add to the beginning of result array?
What is the significance of starting insertion from greatest to lowest instead of lowest to greatest?
Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Squaring a Sorted Array (easy) - Grokking the Coding Interview: Patterns for Coding Questions
Hi @bee1,
Our function takes a sorted array as input, and the largest square element of a sorted array is always located at the endpoints. On the other hand, the smallest square element can be found at any index in an array. It becomes very difficult to locate the smallest square element in a sorted array. Consider the three circumstances presented below.
Example 1
Input_Array = [-5, -1, 0, 1, 2, 3]
Output_Array = [0,1, 1, 4, 9, 25]
Here the largest square element is 5, which is located at the left endpoint, and the smallest square element is 0, which is located at index = 2
Example 2
Input_Array = [0, 1, 2, 3]
Output_Array = [0,1, 4, 9]
Here the largest square element is 3, which is located at the right endpoint, and the smallest square element is 0, which is located at index = 0
Example 3
Input_Array = [-6, -5, -2, 0, 1]
Output_Array = [0, 1, 4, 25, 36]
Here the largest square element is -6, which is again located at the left endpoint, and the smallest square element is 0, which is located at index = 3
I hope this will help