Problem: Sorted Squares of an Array

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 elements, the array becomes [16, 1, 0, 9, 100]. Sorting this results in [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^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in non-decreasing order.

Follow-up:

Squaring each element and sorting the new array is trivial. Can you find an O(n) solution using a different approach?

Approach:

Since the array is already sorted in non-decreasing order, squaring the elements results in an array where the smallest absolute values are at the two ends of the array (negative and positive values). To efficiently create the sorted array of squares, we can use a two-pointer approach:

1. Left pointer (left): Points to the beginning of the array (smallest absolute value).
2. Right pointer (right): Points to the end of the array (largest absolute value).

We compare the square of the elements at the two pointers (left and right). The larger square is placed at the current position in the result array, and we move the corresponding pointer inward. This ensures that we fill the result array from the largest to the smallest square.

C Code:

#include <stdio.h>
#include <stdlib.h>

// Function to calculate the squares and store them in sorted order
void sortedSquares(int* nums, int numsSize, int* result) {
    int left = 0, right = numsSize - 1;
    int index = numsSize - 1; // Fill the result array from the back
    int leftSquare = 0, rightSquare = 0;
    
    // Process elements from both ends of the array
    while (left <= right) {
        leftSquare = nums[left] * nums[left];
        rightSquare = nums[right] * nums[right];
        
        // Place the larger square at the current index
        if (leftSquare > rightSquare) {
            result[index--] = leftSquare;
            left++;
        } else {
            result[index--] = rightSquare;
            right--;
        }
    }
}

int main() {
    int nums1[] = {-4, -1, 0, 3, 10};
    int numsSize1 = sizeof(nums1) / sizeof(nums1[0]);
    int result1[numsSize1];

    sortedSquares(nums1, numsSize1, result1);

    // Print the result array
    for (int i = 0; i < numsSize1; i++) {
        printf("%d ", result1[i]);
    }

    return 0;
}

Explanation of the Code:

1. sortedSquares function:

   • Two pointers: left starts at the beginning of the array and right starts at the end.
   • The squares of the elements at left and right are calculated. The larger square is placed in the result array, and the corresponding pointer (left or right) is moved inward.
   • The index starts from the last position of the result array and is decremented as we place values in the array.

2. Time complexity: The solution has a time complexity of O(n), where n is the number of elements in the array. Each element is processed once.

3. Space complexity: The space complexity is O(n) due to the result array used to store the squares.

Example Output:

Input:

nums = [-4, -1, 0, 3, 10]

Output:

0 1 9 16 100