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.

LeetCode Links

Squares of a Sorted Array

Constraints

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums is sorted in non-decreasing order.

Examples

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]

Different Approaches

1️⃣ Brute Force Approach

Intuition:

Just square each number, then sort the result

Approach:

1. Traverse the array and square every element.
2. Sort the resultant array.

Code:

vector<int> sortedSquares(vector<int>& nums) {
    for (int& num : nums)
        num *= num;
    sort(nums.begin(), nums.end());
    return nums;
}

Complexity Analysis:

• Time Complexity:O(n log n)
  • Squaring: O(n)
  • Sorting: O(n log n)
  • Overall: O(n log n)
• Space Complexity:O(1)
  • In-place, no extra space needed.

2️⃣ Two Pointers (Optimal)

Intuition:

Negative numbers become large positives when squared.

Since the input is sorted, the largest square must be either at the beginning or end. Use two pointers to compare absolute values and build the result array from back to front.

Approach:

1. Initialize two pointers, left = 0, right = n-1.
2. Create a result array of size n, fill from the end.
3. Compare abs(nums[left]) and abs(nums[right]), insert the larger square at the current index.

Code:

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size(); // Get the number of elements in the input array

        // Create a result vector of the same size to store squared values
        // No need to initialize with 0s since we'll fill all positions
        vector<int> result(n);

        int left = 0;         // Pointer starting from the beginning of the array
        int right = n - 1;    // Pointer starting from the end of the array

        // We will fill the result array from the back to the front
        for (int i = n - 1; i >= 0; --i) {
            // Compare absolute values of the elements at left and right pointers
            // because negative numbers can have larger squares than positive ones
            if (abs(nums[left]) > abs(nums[right])) {
                // If the left value is larger (in absolute), square it and place it in the result
                result[i] = nums[left] * nums[left];
                ++left; // Move left pointer to the right
            } else {
                // If the right value is larger (or equal), square it and place it in the result
                result[i] = nums[right] * nums[right];
                --right; // Move right pointer to the left
            }
        }

        // Now the result array is filled with squares in sorted (non-decreasing) order
        return result;
    }
};

Complexity Analysis:

• Time Complexity:O(n)
  • We doing it in a single pass
• Space Complexity:O(1)