# 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/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode.realtemirov.uz/problems/977.-squares-of-a-sorted-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.