Squares of a Sorted Array

Problem Statement

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

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]

Approach

A straightforward approach would be to square each element of the array and then sort the array. This approach would take $O(n \cdot \log n)$ time complexity.

However, we can do better than that. Since the array is already sorted, we can use two pointers to solve this problem in $O(n)$ time complexity.

1. Initialize two pointers left and right at the start and end of the array, respectively.
2. Compare the absolute values of the elements at the pointers.
3. If the absolute value of the element at the left pointer is greater than the absolute value of the element at the right pointer, square the element at the left pointer and move the left pointer to the right.
4. Otherwise, square the element at the right pointer and move the right pointer to the left.
5. Continue this process until the left pointer is greater than the right pointer.

Implementation

Here is a Java implementation of the above approach:

public int[] sortedSquares(int[] nums) {
    int start = 0;
    int end = nums.length - 1;

    int[] result = new int[nums.length];
    int index = nums.length - 1;

    while(start <= end){
        if(Math.abs(nums[start]) < Math.abs(nums[end])){
            result[index] = nums[end]*nums[end];
            end--;
        }else{
            result[index] = nums[start]*nums[start];
            start++;
        }
        index--;
    }
    
    return result;
}

Complexity Analysis

The time complexity for this approach is $O(n)$, where $n$ is the length of the input array nums. Also as we are using an additional array to store the result, the space complexity is $O(n)$.