Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Squaring a Sorted Array

Problem Statement

Solution

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity

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.

Solution

We can use a brute-force approach to iterate the input array and calculate the square of each number. We can store these squares in a new array and then sort the resulting array using any sorting algorithm like Quicksort or Mergesort. Because of the sorting, this approach has a time complexity of O(N*logN), where N is the length of the input array. Here is a Python solution for this approach:

  def sorted_squares(nums):
    return sorted([num**2 for num in nums])

Can we do better than this? Can we avoid sorting? Is it possible to generate the output in sorted order?

The tricky part is that we can have negative numbers in the input array, which makes it harder to generate the output array with squares in sorted order.

One easier approach could be to first locate the index of the first positive number in the input array. After that, we can utilize the Two Pointers technique to iterate over the array, with one pointer moving forward to scan positive numbers, and the other pointer moving backward to scan negative numbers. At each step, we can compare the squares of the numbers pointed by both pointers and append the smaller square to the output array.

For the above-mentioned Example-1, we will do something like this:

Image

Since the numbers at both ends can give us the largest square, an alternate approach could be to use two pointers starting at both ends of the input array. At any step, whichever pointer gives us the bigger square, we add it to the result array and move to the next/previous number. Please note that we will be appending the bigger square (as opposed to the previous approach) because the two pointers are moving from larger squares to smaller squares. For that, we will be inserting the squares at the end of the output array.

For the above-mentioned Example-1, we will do something like this:

Image

Here's a detailed walkthrough of the algorithm:

  1. We start by obtaining the length of the input array, arr, which we store in variable n. Then, we create a new array, squares, of the same length to hold the squared values. We also create a variable highestSquareIdx and set it to n - 1, the last index of squares, which will help us populate the squares array from the highest (rightmost) index towards the lowest (leftmost).

  2. We initialize two pointers, left and right, to 0 and n - 1, respectively. These pointers represent the indices of the elements at the start (lowest) and end (highest) of the array.

  3. We enter a loop that continues as long as left is less than or equal to right.

  4. In each iteration, we calculate the squares of the elements at the left and right indices, storing them in leftSquare and rightSquare respectively.

  5. We then compare leftSquare with rightSquare. The larger of these two squares is inserted at the position of highestSquareIdx in the squares array, and highestSquareIdx is decremented.

  6. If leftSquare was larger, we increment left to move towards the higher numbers in the array. If rightSquare was larger or equal, we decrement right to move towards the lower numbers in the array. We're comparing absolute square values, so even if numbers in the array are negative, we're dealing with their positive square.

  7. This process repeats, filling up the squares array from right to left, until left and right meet or cross each other.

  8. At this point, the squares array is filled with the squares of the numbers in the input array, sorted in ascending order. This array is then returned as the result.

Algorithm Walkthrough

Example Input: [-2, -1, 0, 2, 3]

  1. Initialization:

    • squares = [0, 0, 0, 0, 0]
    • left = 0, right = 4, highestSquareIdx = 4

  2. Iteration:

    • First Iteration:
      • leftSquare = (-2)^2 = 4
      • rightSquare = 3^2 = 9
      • rightSquare > leftSquare
      • squares[4] = 9
      • Move right to 3, decrement highestSquareIdx to 3
    • Second Iteration:
      • leftSquare = 4
      • rightSquare = 2^2 = 4
      • rightSquare >= leftSquare
      • squares[3] = 4
      • Move right to 2, decrement highestSquareIdx to 2
    • Third Iteration:
      • leftSquare = 4
      • rightSquare = 0^2 = 0
      • leftSquare > rightSquare
      • squares[2] = 4
      • Move left to 1, decrement highestSquareIdx to 1
    • Fourth Iteration:
      • leftSquare = (-1)^2 = 1
      • rightSquare = 0
      • leftSquare > rightSquare
      • squares[1] = 1
      • Move left to 2, decrement highestSquareIdx to 0
    • Fifth Iteration:
      • leftSquare = 0
      • rightSquare = 0
      • squares[0] = 0
      • Move right to 1, decrement highestSquareIdx to -1

  3. Result:

    • squares = [0, 1, 4, 4, 9]
Image

Code

Here is the code for the second approach discussed above:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Two-pointer traversal: The algorithm uses two pointers (left and right) to iterate over the input array from both ends. Each element is processed exactly once, and the pointers move toward each other until they meet.
  • Constant-time operations: For each iteration, the algorithm computes the square of the element at each pointer and performs a comparison to decide where to place the squared value in the squares array. These operations are constant time, O(1).
  • The loop runs N times, where N is the number of elements in the array.

Overall time complexity: O(N).

Space Complexity

  • Output array: The algorithm uses an additional array squares of size N to store the squared values of the input array, resulting in a space complexity of O(N).
  • In-place modification: No additional dynamic data structures are used except for the extra squares array. The other variables such as left, right, and highestSquareIdx require constant space, O(1).

Overall space complexity: O(N).

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

Solution

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity