> For the complete documentation index, see [llms.txt](https://leetcode.realtemirov.uz/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode.realtemirov.uz/problems/977.-squares-of-a-sorted-array.md).

# 977. Squares of a Sorted Array

🟩 Easy

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 <= 10^4`
* `-104 <= nums[i] <= 10^4`
* `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?

## Solution

My Solution

```go
func sortedSquares(nums []int) []int {
    l, r := 0, len(nums)-1
    resp := make([]int, 0, len(nums))

    for l <= r {
        if nums[l]*nums[l] >= nums[r]*nums[r] {
            resp = append(resp, nums[l]*nums[l])
            l++
        } else {
            resp = append(resp, nums[r]*nums[r])
            r--
        }
    }

    for i, j := 0, len(resp)-1; i < j; i, j = i+1, j-1 {
        resp[i], resp[j] = resp[j], resp[i]
    }

    return resp
}
```

Optimal Solution (Two Pointers)

```go
func sortedSquares(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    left, right := 0, n-1
    
    // Fill array from end to start
    for i := n-1; i >= 0; i-- {
        if abs(nums[left]) > abs(nums[right]) {
            result[i] = nums[left] * nums[left]
            left++
        } else {
            result[i] = nums[right] * nums[right]
            right--
        }
    }
    
    return result
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}
```

### Approach

This solution uses a two-pointer technique to build the sorted squared array:

1. Key Observation:
   * In a sorted array, largest squares will come from either:
     * Largest positive numbers (at the end)
     * Largest absolute negative numbers (at the start)
2. Two-Pointer Strategy:
   * Left pointer at start (for negative numbers)
   * Right pointer at end (for positive numbers)
   * Compare absolute values to decide which square is larger
3. Result Construction:
   * Build result array from end to start
   * Place larger squares first
   * Move pointers accordingly

### Complexity Analysis

#### Time Complexity: O(n)

* Single pass through the array
* Each element processed exactly once
* No sorting required
* All operations are O(1)

#### Space Complexity: O(n)

* Result array of size n
* Only constant extra space besides output:
  * Two pointers (left, right)
  * Loop counter
  * Temporary variables for calculations

### Why it works

* Array Properties:
  * Input array is sorted
  * Squares of numbers follow a U-shaped pattern
  * Largest squares are at the extremes
* Two-Pointer Benefits:
  * No need to sort after squaring
  * Directly builds sorted result
  * Handles both positive and negative numbers efficiently
* Optimization Details:
  * Pre-allocating result array avoids resizing
  * Building from end eliminates need for reversal
  * Absolute value comparison ensures correct ordering

![result](/files/wUQZMloLkTYBaffrDEPU)

Leetcode: [link](https://leetcode.com/problems/squares-of-a-sorted-array/description/)