Skip to content

1019. Squares Of A Sorted Array

Array Two Pointers Sorting

Problem - Squares Of A Sorted Array

Easy

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 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:

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

 

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums is sorted in non-decreasing order.

 

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        # for i, num in enumerate(nums):
        #     nums[i] = num ** 2

        # return sorted(nums)

        result = []
        i, j = 0, len(nums) - 1
        while j >= i:
            cantidate1 = nums[i] ** 2
            cantidate2 = nums[j] ** 2
            if cantidate1 > cantidate2:
                result.append(cantidate1)
                i += 1
            else:
                result.append(cantidate2)
                j -= 1

        return result[::-1]

Submission Stats:

  • Runtime: 11 ms (52.19%)
  • Memory: 19.6 MB (36.13%)