Grokking the Coding Interview: Patterns for Coding Questions
Vote

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
. . . .
Shaurya Sood

Shaurya Sood

· 11 hours ago

Used the Arrays util class and just did a sort operation at the end- class Solution { public static int[] makeSquares(int[] arr) { int n = arr.length; int[] squares = new int[n]; // TODO: Write your code here

for(int i = 0; i < arr.length; i++){
  squares[i] = arr[i] * arr[i];
}

Arrays.sort(squares);

return squares;

} }

I know this is defeating the point of the exercise but technically it is correct?

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.

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Try it yourself