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.
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
Recommended Posts