977 Squares of a Sorted Array

1. 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 \leq nums.length \leq 10^{4}\)
\(-10^{4} \leq nums[i] \leq 10^{4}\)
nums is sorted in non-decreasing order.

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

2. Solution

2.1. Understanding the problem

If \(e \geq 0, \forall e \in 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.

2.2. Algorithm

The basic algorithm following previous section is the following:

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.
Then we repeat the process until left_idx > right_idx.

2.3. Code

Listing 1: 977 Sauqres of a Sorted Array my solution

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)

Listing 2: 977 Sauqres of a Sorted Array my solution-results

True
True
True
True

2.3.1. Complexity

2.3.1.1. Time complexity:

O(n)

2.3.1.2. Space complexity:

O(n) for the resulting list.

2.4. Leetcode solution

nil. Same algorithm.

Listing 3: 977 Sauqres of a Sorted Array leetcode solution

<<imports for typing>>

Listing 4: 977 Sauqres of a Sorted Array leetcode solution-results

2.4.1. Time complexity:

2.4.2. Space complexity:

3. More analysis

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