Return sorted squares of a sorted array
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
You are given an integer array `nums` sorted in **non-decreasing** order. The array may contain negative numbers.
Return a new array containing the **square of each number**, also sorted in **non-decreasing** order.
## Input
- `nums`: an array of integers sorted in non-decreasing order.
## Output
- An array of integers representing the squares of `nums`, sorted in non-decreasing order.
## Constraints (typical interview scale)
- `1 <= nums.length <= 10^5`
- `-10^4 <= nums[i] <= 10^4`
## Examples
- Input: `nums = [-4, -1, 0, 3, 10]`
Output: `[0, 1, 9, 16, 100]`
- Input: `nums = [-7, -3, 2, 3, 11]`
Output: `[4, 9, 9, 49, 121]`
## Follow-up
Can you solve it in **O(n)** time (better than sorting after squaring)?
Quick Answer: This question evaluates array-processing and algorithmic optimization skills, including handling negative values, element-wise transformations, and preserving sorted order after mapping.
Return squares of a non-decreasing integer array in non-decreasing order in O(n) time.
Constraints
- Inputs are provided as Python literals matching the function signature.
- Return a deterministic exact-match result.
Examples
Input: ([-4,-1,0,3,10],)
Expected Output: [0, 1, 9, 16, 100]
Explanation: Prompt example 1.
Input: ([-7,-3,2,3,11],)
Expected Output: [4, 9, 9, 49, 121]
Explanation: Prompt example 2.
Input: ([0],)
Expected Output: [0]
Explanation: Single zero.
Hints
- Choose a representation that makes the core operation simple.
- Handle empty and boundary inputs before the main algorithm.