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.

Screen Shot 2020-08-06 at 9.01.31.png

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

Recommended Posts

Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm gymnastics 12
Algorithm gymnastics 10
Algorithm Gymnastics 24 Reverse a Linked List
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
A * algorithm (Python edition)
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
A comment on Boruta algorithm