Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Squaring a Sorted Array (easy)

Problem Statement

Try it yourself

Problem Statement

Given a sorted array, create a new array containing squares of all the numbers of the input array in the sorted order.

Example 1:

Input: [-2, -1, 0, 2, 3]
Output: [0, 1, 4, 4, 9]

Example 2:

Input: [-3, -1, 0, 1, 2]
Output: [0, 1, 1, 4, 9]

Constraints:

  • 1 <= arr.length <= 10<sup>4</sup>
  • -10<sup>4</sup> <= arr[i] <= 10<sup>4</sup>
  • arr is sorted in non-decreasing order.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
Mark as Completed
I

Idan

· 4 years ago

Hi there.

I believe you may have a mistake in the description of the first solution. For the squares array to be sorted in a non-descending order, you'd have to add the smaller square each time, not the bigger one.,

Show 2 replies
Vini Neto

Vini Neto

· 3 years ago

Please, I request the person in charge of the course to fix the first solution proposed, because it is wrong.

BTW, this solution is not represented on the code examples. It tells us to add the bigger square to the array. In fact, as the solution suggests we to iterate from the lowest non-negative number to the right, and from the highest negative number to the left, we must add the smallest square, not the larger one.

Please, fix the text. See attached image. Image

Show 5 replies
C

Charlie Jiang

· 4 years ago

can I just go through the array and do i**2 and then use the python sort() function? Wouldn't this be easier than the two pointer approach?

Show 2 replies
D

Daniel Snider

· 4 years ago

I think using absolute value can give a simpler solution. Four less lines of code in python:

def square_sorted_array(arr): squares = [] left_idx = 0 right_idx = len(arr) - 1

while left_idx arr[right_idx]: squares.insert(0, arr[left_idx] * arr[left_idx]) left_idx += 1

else: squares.insert(0, arr[right_idx] * arr[right_idx]) right_idx -= 1

return squares

K

Kaven Tan

· 4 years ago

Dumb question. But why wouldn’t I just sort the output array after inserting all the values. Less there’s some restrictions. Then if there are it should be mentioned.

Show 1 reply
P

Paul Montleau

· 4 years ago

I suggest changing leftSquare = arr[left] * arr[left] to leftSquare = arr[left] ** 2 for readability.

Show 1 reply
K

klden

· 4 years ago

Can we replace the "

Show 1 reply
S

Suyog Jain

· 4 years ago

Is there a O(1) space complexity solution for this problem?

Show 4 replies
J

JOD Developer

· 3 years ago

So the solution is making use of a lot of space but using in-place the space becomes O(1) if i am not mistaking something.

Arturo Calderón

Arturo Calderón

· 3 years ago

For Python specifically, we can get away with simpler expressions if we take into account that inserting elements in a list is a O(1) operation. This makes the code easier to read IMO.

def SquareSortedArrayV2(nums):
    idxLeft = 0
    idxRight = len(nums) - 1
    sortedSquares = []
    
    while idxLeft <= idxRight:
        valLeft = nums[idxLeft] ** 2
        valRigth = nums[idxRight] ** 2
        if valRigth > valLeft:
            sortedSquares.insert(0, valRigth)
            idxRight -= 1
        else:
            sortedSquares.insert(0, valLeft)
            idxLeft += 1

    return sortedSquares
Show 3 replies

On This Page

Problem Statement

Try it yourself