Squares of Sorted Array - LeetCode Daily Challenge

Problem Statement

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]

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] answer = new int[nums.length];
        int left = 0, right = nums.length - 1, i = nums.length - 1;

        while(left <= right) {
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];
            if(leftSquare < rightSquare) {
                answer[i--] = rightSquare;
                right -= 1;
            } else {
                answer[i--] = leftSquare;
                left += 1;
            }
        }

        return answer;
    }
}

C++ Code

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> answer(n);
        int left = 0, right = n - 1, i = n - 1;

        while (left <= right) {
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];
            if (leftSquare < rightSquare) {
                answer[i--] = rightSquare;
                right -= 1;
            } else {
                answer[i--] = leftSquare;
                left += 1;
            }
        }

        return answer;
    }
};

Python Code

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [0] * n
        left, right, i = 0, n - 1, n - 1

        while left <= right:
            leftSquare = nums[left] * nums[left]
            rightSquare = nums[right] * nums[right]
            if leftSquare < rightSquare:
                answer[i] = rightSquare
                right -= 1
            else:
                answer[i] = leftSquare
                left += 1
            i -= 1

        return answer

Javascript Code

var sortedSquares = function(nums) {
    const n = nums.length;
    const answer = new Array(n);
    let left = 0, right = n - 1, i = n - 1;

    while (left <= right) {
        const leftSquare = nums[left] * nums[left];
        const rightSquare = nums[right] * nums[right];
        if (leftSquare < rightSquare) {
            answer[i--] = rightSquare;
            right--;
        } else {
            answer[i--] = leftSquare;
            left++;
        }
    }

    return answer;
};

Go Code

func sortedSquares(nums []int) []int {
    n := len(nums)
    answer := make([]int, n)
    left, right, i := 0, n-1, n-1

    for left <= right {
        leftSquare := nums[left] * nums[left]
        rightSquare := nums[right] * nums[right]
        if leftSquare < rightSquare {
            answer[i] = rightSquare
            right--
        } else {
            answer[i] = leftSquare
            left++
        }
        i--
    }

    return answer
}

Complexity Analysis

Time Complexity: O(N), we are iterating over each element.
Space Complexity: O(N), for answer array.