977. Squares of a Sorted Array

Problem Statement

link: LeetCode LeetCode.cn

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example:

Input: nums = [-4,-1,0,3,10] Output: [0,1,9,16,100]

Input: nums = [-7,-3,2,3,11] Output: [4,9,9,49,121]

Solution Approach

The algorithm uses a two-pointer approach to traverse the sorted array from both ends, comparing absolute values to square and place the larger value in the correct position of the result array, which is built in reverse order.

Algorithm

1. Two-Pointer Technique: The algorithm uses two pointers, one starting at the beginning (l) and one at the end (r) of the array, to efficiently compare and square the largest absolute values.
2. Reverse Filling: The result array res is filled from the end to the beginning to ensure that the largest squares are placed in their correct positions first, avoiding the need for a separate sorting step.
3. Optimal Time Complexity: This approach processes each element exactly once, achieving a linear time complexity of O(N), which is efficient for handling large input arrays.

Complexity

time complexity: O(n) space complexity: O(n)

Implement

    class Solution:
  def sortedSquares(self, nums: List[int]) -> List[int]:
      n = len(nums)
      res = [0] * n
      l, r = 0, n - 1
      p = n - 1
      while p >= 0:
          if abs(nums[r]) > abs(nums[l]):
              res[p] = nums[r] ** 2
              r -= 1
          else:
              res[p] = nums[l] ** 2
              l += 1
          p -= 1
      return res


      
 

    
    

Twitter  facebook  Email