# Squares of a Sorted Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/squares-of-a-sorted-array)
Canonical: https://scaleengineer.com/dsa/problems/squares-of-a-sorted-array
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda), [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [Ozon](https://scaleengineer.com/companies/ozon), [PayPal](https://scaleengineer.com/companies/paypal), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Instacart](https://scaleengineer.com/companies/instacart), [CrowdStrike](https://scaleengineer.com/companies/crowdstrike), [Whatnot](https://scaleengineer.com/companies/whatnot)
---
## 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 <= 104`
* `-104 <= nums[i] <= 104`
* `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?

# Approaches
## Brute Force: Square and Sort
The most straightforward approach is to first square every element in the input array and then sort the resulting array. This is simple to implement but not the most efficient.
**Time:** O(n log n), where n is the number of elements in the array. Squaring each element takes O(n) time, and sorting the resulting array takes O(n log n) time. The sorting step dominates the complexity. · **Space:** O(n) or O(log n). We need O(n) space for the new array to store the squares. The space complexity of `Arrays.sort()` in Java for primitives is O(log n) due to its dual-pivot quicksort implementation. Thus, the total space is dominated by the O(n) output array.
**Pros:** Simple to understand and implement.
**Cons:** Not the most efficient solution as it doesn't utilize the fact that the input array is already sorted.; The O(n log n) time complexity can be improved upon.
### Explanation
This method involves two main steps. First, we iterate through the input array `nums` from beginning to end. For each number, we calculate its square and store it in a new array, let's call it `result`. After this first pass, the `result` array will contain the squares of all elements from `nums`, but it will not be sorted. For example, if `nums` is `[-4, -1, 0, 3, 10]`, the `result` array will be `[16, 1, 0, 9, 100]`. The second step is to sort this `result` array in non-decreasing order. Standard sorting algorithms like Merge Sort or Quick Sort can be used, which typically have a time complexity of O(n log n). After sorting, `result` becomes `[0, 1, 9, 16, 100]`, which is the final answer.
### Algorithm
*   Create a new array `result` of the same size as `nums`.
*   Iterate through `nums` with an index `i` from 0 to `n-1`.
*   For each element `nums[i]`, calculate its square: `squared = nums[i] * nums[i]`.
*   Store the result in the new array: `result[i] = squared`.
*   After the loop, sort the `result` array using a standard sorting function.
*   Return the sorted `result` array.

```java
import java.util.Arrays;

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = nums[i] * nums[i];
        }
        Arrays.sort(result);
        return result;
    }
}
```

## Two-Pointer Approach
A more optimal approach uses two pointers to build the sorted result array in a single pass, achieving linear time complexity. This method leverages the sorted nature of the input array.
**Time:** O(n), where n is the number of elements in the array. The two pointers `left` and `right` traverse the array once, so the algorithm runs in linear time. · **Space:** O(n), for the output array. If the output array is not considered extra space, the complexity is O(1) as we only use a few variables as pointers.
**Pros:** Optimal time complexity of O(n).; Efficiently uses the sorted property of the input array in a single pass.
**Cons:** Slightly more complex to reason about and implement compared to the brute-force approach.
### Explanation
Since the input array `nums` is sorted, the numbers with the largest absolute values are at the ends of the array. Consequently, their squares will be the largest values in the final sorted array. We can use this property to our advantage.

We initialize two pointers, `left` at the start (index 0) and `right` at the end (index `n-1`) of the input array. We also create a `result` array of the same size. We'll fill the `result` array from right to left, starting with the largest square.

In each step, we compare the absolute values of `nums[left]` and `nums[right]`. The number with the larger absolute value will produce a larger square. We place this larger square at the current end of the `result` array (indicated by a third pointer, `p`), and then move the corresponding pointer (`left` or `right`) inward. We continue this process until the pointers meet or cross, at which point the `result` array will be completely filled with the squared values in sorted order.
### Algorithm
*   Initialize `n` as the length of the input array `nums`.
*   Create a new integer array `result` of size `n`.
*   Initialize a `left` pointer to 0 and a `right` pointer to `n-1`.
*   Iterate with a pointer `p` from `n-1` down to 0 (this will be the index for the `result` array).
*   Inside the loop, compare the absolute value of `nums[left]` and `nums[right]`.
*   If `abs(nums[left])` is greater than `abs(nums[right])`, the square of `nums[left]` is larger. Place this square at `result[p]` and increment `left`.
*   Otherwise, the square of `nums[right]` is greater or equal. Place its square at `result[p]` and decrement `right`.
*   Decrement `p` in each iteration.
*   After the loop finishes, return the `result` array.

```java
class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int left = 0;
        int right = n - 1;
        
        for (int p = n - 1; p >= 0; p--) {
            if (Math.abs(nums[left]) > Math.abs(nums[right])) {
                result[p] = nums[left] * nums[left];
                left++;
            } else {
                result[p] = nums[right] * nums[right];
                right--;
            }
        }
        return result;
    }
}
```

# Solutions
### Java

```java
class Solution {
public
  int[] sortedSquares(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    for (int i = 0, j = n - 1, k = n - 1; i <= j;) {
      if (nums[i] * nums[i] > nums[j] * nums[j]) {
        res[k--] = nums[i] * nums[i];
        ++i;
      } else {
        res[k--] = nums[j] * nums[j];
        --j;
      }
    }
    return res;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number[]} */ var sortedSquares =
  function (nums) {
    const n = nums.length;
    const res = new Array(n);
    for (let i = 0, j = n - 1, k = n - 1; i <= j; ) {
      if (nums[i] * nums[i] > nums[j] * nums[j]) {
        res[k--] = nums[i] * nums[i];
        ++i;
      } else {
        res[k--] = nums[j] * nums[j];
        --j;
      }
    }
    return res;
  };

```

### Python

```python
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]: n = len(nums) res = [0] * n i, j, k = 0, n - 1, n - 1 while i <= j: if nums[i] * nums[i] > nums[j] * nums[j]: res[k] = nums[i] * nums[i] i += 1 else: res[k] = nums[j] * nums[j] j -= 1 k -= 1 return res

```

### CPP

```cpp
class Solution {
public:
  vector<int> sortedSquares(vector<int> &nums) {
    int n = nums.size();
    vector<int> res(n);
    for (int i = 0, j = n - 1, k = n - 1; i <= j;) {
      if (nums[i] * nums[i] > nums[j] * nums[j]) {
        res[k--] = nums[i] * nums[i];
        ++i;
      } else {
        res[k--] = nums[j] * nums[j];
        --j;
      }
    }
    return res;
  }
};

```