educative.io

Solution with only n squaring operations

Courses
, ,
#1

The provided solution performs some squaring operations twice.
This performs once.

    /**
     * Squaring sorted Array
     * time: O(n) space: O(n)
     * @param arr - Array of sorted ascending
     * @return array of each element squared, ascending
     */
    function make_squares(arr) {
      const n = arr.length;
      const squares = Array(n).fill(0);
      let i = n - 1;
      let l = 0;
      let r = n - 1;
      let leftSquare = arr[l] * arr[l];
      let rightSquare = arr[r] * arr[r];
      while (l <= r) {
        if (leftSquare > rightSquare) {
          squares[i] = leftSquare;
          l += 1;
          leftSquare = arr[l] * arr[l];
        } else {
          squares[i] = rightSquare;
          r -= 1;
          rightSquare = arr[r] * arr[r];
        }
        i -= 1;
      }
    
      return squares;
    }
#2

Yes, you are right, and we will look into it! Keep learning and improving.

At Educative, we highly appreciate your valuable feedback.

#3

in your original solution “highestSquareIdx” is un-necessary. you can use “right-left” instead

def makeSquares(arr):
length=len(arr)
pLeft=0
pRight=len(arr)-1
result=[0]*len(arr)
sqRight=arr[pRight]**2
sqLeft=arr[pLeft]**2
while pLeft<=pRight:
if sqRight>sqLeft:
result[pRight-pLeft]=sqRight
pRight-=1
sqRight=arr[pRight]**2
else:
result[pRight-pLeft]=sqLeft
pLeft+=1
sqLeft=arr[pLeft]**2
return result
print(makeSquares([-2, -1, 0, 2, 3]))

#4

The explanation part for two pointers ‘squares of sorted array’ needs further elaboration.
Would appreciate if more detailed explanation is added in the course on this section.

1 Like