Grokking the Engineering Manager Coding Interview
Vote

0% completed

​

Solution: Squaring a Sorted Array

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

.....

.....

.....

Like the course? Get enrolled and start learning!
Mohammed Shahid

Mohammed Shahid

· 2 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) ?

wasim ahmed

wasim ahmed

· 5 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
wasim ahmed

wasim ahmed

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

· 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

Reading Progress

0%