Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Squaring a Sorted Array

Problem Statement

Why this is a Two Pointers problem

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.

Why this is a Two Pointers problem

What the question saysThe signal it matches
"Given a sorted array", and the constraint "arr is sorted in non-decreasing order"the input is sorted
the constraint allows negative values, and squaring turns the most negative into the largestthe biggest results sit at both ends, which is what a pointer at each end reaches first
the output must hold the squares "in the sorted order"you are asked to build a sorted sequence, which the two ends can feed

Both pointers move inward while the answer is filled from the back, which is the converging variant.

The closest alternative. This question signals the pattern more weakly than the rest of the chapter. Square every number and then sort. That answer is correct and costs O(N log N).

Two pointers is chosen to reach O(N). The simple approach does not fail. The negative values are the deciding detail. Without them the array would already be in order after squaring, and no pointers would be needed.

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

Let's trace the second approach on [-2, -1, 0, 2, 3]. Move through the steps one at a time:

mediaLink

Step 1. The input [-2, -1, 0, 2, 3] is sorted, but squaring breaks that order: (-2) squared is 4, which is larger than 0 squared and 2 squared. The one thing squaring cannot break is this: the largest square must come from either the leftmost number or the rightmost one, because those are the two furthest from zero. That is why a pointer at each end is enough, and why the answer is filled from its last cell backwards.

1 of 7

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).

Mohammed Shahid

Mohammed Shahid

· 3 months ago

Regarding the Space complexity

IMO, since the question itself if asking for to return new array, then why is the space complexity considered as O(N) ?

Show 1 reply
wasim ahmed

wasim ahmed

· 6 months ago

I was disctracted while reading the explanation thinking I need to find the lowest peak and start from mid with left and right. I just went through the code to understand we have to start form extreme ends of left and right.

class Solution:
  def makeSquares(self, arr):
    n = len(arr)
    squares = [0 for x in range(n)]
    heap_store = []
    # TODO: Write your code here
    l, r = 0, n-1
    i = n-1
    while l <= r:
      l_square = arr[l] ** 2
      r_square = arr[r] ** 2
      if l_square >= r_square:
        squares[i] = l_square
        l += 1
      else:
        squares[i] = r_square
        r -= 1
      i -= 1

    return squares
Show 1 reply
wasim ahmed

wasim ahmed

· 6 months ago

import heapq
class Solution:
  def makeSquares(self, arr):
    n = len(arr)
    squares = [0 for x in range(n)]
    heap_store = []
    # TODO: Write your code here
    for num in arr:
      square = num * num
      heapq.heappush(heap_store, square)
    i = 0
    while n:
      squares[i] = heapq.heappop(heap_store)
      n -= 1
      i += 1
    return squares
Show 1 reply
Christopher Guy Slater

Christopher Guy Slater

· 2 years ago

class Solution:
  def makeSquares(self, arr):
    n = len(arr)
    squares = [0 for x in range(n)]
    # TODO: Write your code here
    i = 0 
    j = len(arr) - 1 
    # add an index for the `squares` array
    ctr = -1 
    # check the absolute value of the extreme elements:
    while i <= j:
      if abs(arr[i]) > abs(arr[j]):
        squares[ctr] = arr[i] ** 2 
        i += 1 
      else:
        squares[ctr] = arr[j] ** 2 
        j -= 1 
      ctr -= 1 
    return squares
Show 1 reply
Abdullah AlKheshen

Abdullah AlKheshen

· 2 years ago

Sure, here are the three approaches without the main function, focusing solely on the core algorithms:

 

Approach 1: Using slow_ptr and fast_ptr with Initialization of slow_ptr to 1

 


class Solution {

public:

    static int removeDuplicates(vector<int> &arr) {

        int slow_ptr = 1;

        for (int fast_ptr = 1; fast_ptr < arr.size(); fast_ptr++) {

            if (arr[slow_ptr - 1] != arr[fast_ptr]) {

                arr[slow_ptr] = arr[fast_ptr];

                slow_ptr++;

            }

        }

        return slow_ptr;

    }

};

 

Approach 2: Using slow_ptr and fast_ptr with Initialization of slow_ptr to 0

 


class Solution {

public:

    static int removeDuplicates(vector<int> &nums) {

        int slow_ptr = 0;

       
J

John O'Neill

· 3 years ago

I didn't want to recalculate the squares. :)

class Solution:
  def makeSquares(self, arr):
    n = len(arr)
    squares = [0] * n
    left, right, i = 0, n - 1, n - 1
    sq_left = arr[left]**2
    sq_right = arr[right]**2
    while i >= 0:
      if sq_left > sq_right:
        squares[i] = sq_left
        left += 1
        sq_left = arr[left]**2
      else:
        squares[i] = sq_right
        right -= 1
        sq_right = arr[right]**2
      i -= 1

    return squares
Show 1 reply
T

Thai Minh

· 3 years ago

class Solution:
  def makeSquares(self, arr):
    n = len(arr)
    squares = [0 for x in range(n)]
    # TODO: Write your code here
    # front and back pointer, square both up and compare which one bigger will be appened left first and 
    # increament/decreament appropriately
    if len(arr) < 2:
      return [arr[0]**2]
    f_ptr, b_ptr = 0, len(arr) - 1
    curr_pos = len(squares) - 1
    while f_ptr <= b_ptr:
      f_value = arr[f_ptr]**2
      b_value = arr[b_ptr]**2
      if f_value >= b_value:
        squares[curr_pos] = f_value
        f_ptr += 1
      else:
        squares[curr_pos] = b_value
        b_ptr -= 1
      curr_pos -= 1
    return squares
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
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.

Vini Neto

Vini Neto

· 4 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

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Why this is a Two Pointers problem

Solution

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity