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

Anonymous

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

       
A

Anonymous

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

Anonymous

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

Anonymous

· 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 2 replies
A

Anonymous

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

A

Anonymous

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

Anonymous

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

Anonymous

· 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

A

Anonymous

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

Anonymous

· 4 years ago

Can we replace the "

Show 1 reply

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Try it yourself