[Arrays] Squares of a Sorted Array

Date: 2023.04.03 Updated: 2023.04.17

Categories: Arrays

📋 This is my note-taking from what I learned in LeetCode!

Problem

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 <= 10⁴ -10⁴ <= nums[i] <= 10⁴ 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?

Solution

Solution Link

Approach 1: Sort

Algorithm:

Initialize an empty result array to store the squared numbers in non-decreasing order.
Loop through each number in the input array:

a. Calculate the square of the current number.

b. Add the squared number to the result array.
Sort the result array in non-decreasing order.
Return the sorted result array.

def sorted_squares(nums):
    result = []
    for num in nums:
        result.append(num * num)
    result.sort()
    return result

print(sorted_squares([-4, -1, 0, 3, 10]))

Complexity Analysis

Time Complexity: O(N log⁡N), where N is the length of A.
Space complexity : O(N) or O(log⁡N)

Approach 2: Two Pointer

Algorithm:

Initialize three variables: n, result, and two pointers left and right.
n is assigned the length of the input array nums, result is assigned a list of n zeros, and left is set to 0 and right to n-1.
Iterate over the array nums in reverse order (from n-1 to 0) using the for loop and the index variable i.
Check if the absolute value of the left pointer element of nums is less than the absolute value of the right pointer element of nums.
If the absolute value of the left pointer element of nums is less than the absolute value of the right pointer element of nums, then the square of the right pointer element is appended to the result list and the right pointer is decremented by 1.
Otherwise, the square of the left pointer element of nums is appended to the result list and the left pointer is incremented by 1.
Finally, the function returns the result list.

def sorted_squares(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [0] * n
    left = 0
    right = n - 1

    for i in range(n - 1, -1, -1):
        if abs(nums[left]) < abs(nums[right]):
            square = nums[right]
            right -= 1
        else:
            square = nums[left]
            left += 1
        result[i] = square * square
    return result

print(sorted_squares([-4, -1, 0, 3, 10]))

Complexity Analysis

Time Complexity: O(N), where N is the length of A.
Space complexity : O(N) if you take output into account and O(1) otherwise.

For better understanding

1. abs

In Python, abs() is a built-in function that returns the absolute value of a number. The absolute value of a number is its distance from zero on the number line, without taking into account the direction (positive or negative).

For example:

abs(5) returns 5
abs(-5) returns 5
abs(0) returns 0

The abs() function can be used with various numeric types such as integers, floating-point numbers, and complex numbers. If a non-numeric argument is passed to abs(), a TypeError is raised.

Seyeon