https://leetcode.com/problems/squares-of-a-sorted-array/

Problem Statement

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decrMeasing order.

Example 1:

Input: [-4,-1,0,3,10]

Output: [0,1,9,16,100]

Example 2:

Input: [-7,-3,2,3,11]

Output: [4,9,9,49,121]

Problem Analysis

The input of this problem is an 1-D array. Also please notice that the input array is sorted and non-decreasing. Usually when you see an input is sorted, you will always use this nature to resolve the problem. Also we are required to return the result in a sorted non-decreasing order. Since we are required to return a sorted result, I started to wonder whether the time complexity is O(N * lgN) since this is usually the minimal time complexity of algorithms that involve sorting. However, the nature of input array being sorted might also help us to improve the time complexity as well. Let’s think about this problem with all these questions in mind.

Thinking Process

We are given a sorted array A as input. We have to find the square of each elements in A and return the result of such an array in a sorted order. If all the elements in A are greater or equal to 0, we can just simply square every element and return the result. This will bring us the O(N) solution.

However, the exception is that the input list is not guaranteed to be positive. There could be negative numbers. Some negative numbers could have higher integer than some positive numbers. If we simply keep the original order of the input array and square every number up, then as the last step, sort the array and return it, we will get a O(N * lgN) time complexity answer. Let’s see how that’s implemented.

First Solution

1
2
3
4
5

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        for i in range(len(A)):
            A[i] *= A[i]
        return sorted(A)

or to be more pythonic (with worse space complexity):

1
2
3

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        return sorted([i * i for i in A])