[PYTHON] Algorithm Gymnastics 22 Squaring a Sorted Array

Squaring a Sorted Array

Takes the sorted array as an argument and returns a new array containing the squares of all the numbers in the array in ascending order.

Input: [-2, -1, 0, 2, 3] Output: [0, 1, 4, 4, 9]

Input: [-3, -1, 0, 1, 2] Output: [0 1 1 4 9]

Solution Since the array passed as an argument is sorted, you can get the maximum and minimum numbers at both ends, so you can use two pointers starting at both ends of the array. After that, compare the squared values and add the larger value from the right end.

Implementation

def make_squares(arr):
  # Time Complexity -> O(n)
  # Space Complexity -> O(n)
  squares = [0 for _ in range(len(arr))]
  left_pointer, right_pointer = 0, len(arr) - 1
  highestValIndex = len(arr) -1
  while left_pointer <= right_pointer:
    left_val = arr[left_pointer]**2
    right_val = arr[right_pointer]**2
    if left_val <= right_val:
      squares[highestValIndex] = right_val
      right_pointer -= 1
    else:
      squares[highestValIndex] = left_val
      left_pointer += 1
    highestValIndex -= 1
  return squares