2022-01-30-210803-977_squares_of_a_sorted_array.org

977 Squares of a Sorted Array

Description

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

Constraints:

1. $1 \leq nums.length \leq 10⁴$
2. $-10⁴ \leq nums[i] \leq 10⁴$
3. nums is sorted in non-decreasing order.

Examples:

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].

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

Solution

Understanding the problem

If $e \geq 0, ∀ e ∈ nums$, then the problem is trivial as we only need to square each element and the resulting array is already sorted.

We need to consider the case where negative integers are present.

I think the basic idea is that we can start from both ends of the squared list, and move towards the center of the list. For example, we have the following list [-2, -1, 0, 3, 10], and its squared list num_sq = [4, 1, 0, 9, 100]. In general, we don’t know if num_sq[0] > num_sq[-1] or the other way around, but we do know that num_sq is first non-increasing and then non-decreasing.

Algorithm

The basic algorithm following previous section is the following:

1. We start with left_idx = 0 and right_idx = len(num_sq)-1 and get num_sq[left_idx] and num_sq[right_idx] and compare them.
   1. if num_sq[left_idx] <= num_sq[right_idx], then we put num_sq[left_idx] in the result list, and left_idx += 1.
   2. else we do the opposite.
2. Then we repeat the process until left_idx > right_idx.

Code

def sortedSquares(nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    ret = []
    left_idx, right_idx = 0, len(nums) - 1

    while left_idx <= right_idx:
        left_val = nums[left_idx] ** 2
        right_val = nums[right_idx] ** 2

        if left_val > right_val:
            ret.append(left_val)
            left_idx += 1
        else:
            ret.append(right_val)
            right_idx -= 1
    # we use append so the order is reversed, i.e. order is non-increasing
    # therefore need to reverse the list
    return ret[::-1]


# tests
nums = [0]
result = [0]
print(sortedSquares([0]) == [0])


nums = [0, 1]
result = [0, 1]
print(sortedSquares(nums) == result)


nums = [-1, 0, 1]
result = [0, 1, 1]
print(sortedSquares(nums) == result)



nums = [-2, -1, 0, 1]
result = [0, 1, 1, 4]
print(sortedSquares(nums) == result)

Complexity

Time complexity:

O(n)

Space complexity:

O(n) for the resulting list.

Leetcode solution

nil. Same algorithm.

<<imports for typing>>

Time complexity:

Space complexity:

More analysis

General thoughts

This is not too hard a question for someone who’s never seen it before. I guess with Leetcode there’s some clue as it’s categorised as a Two Pointer question. So naturally one would think about starting from both ends of the list.

Related problems

Log time