Square a Sorted Array in Linear Time
Company: Instacart
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given integers already in nondecreasing order, return their squares in nondecreasing order. Seek a linear-time solution instead of sorting the squares.
### Constraints and Clarifications
The report explicitly identifies problem 977. Its [official reference](https://leetcode.com/problems/squares-of-a-sorted-array/description/) supplies the practice bounds: 1 <= n <= 10000 and each value is between -10000 and 10000. These are reference-context bounds, not separately recalled interview constraints. Return a new array and preserve duplicate squares.
### Example
For [-5,-2,0,3], return [0,4,9,25].
### What a Strong Answer Covers
Explain why the largest remaining square is at one of the two ends of the unsquared range, fill the output from right to left, and establish linear time and output-space usage.
### Follow-up Questions
- How does the algorithm behave when every input is negative?
- Why does simply squaring left to right fail to preserve order?
Overview: Produce sorted squares from a sorted integer array using two pointers. Explain endpoint selection, duplicate preservation, the loop invariant, and why the algorithm runs in linear time.
Read the full Instacart Machine Learning Engineer interview experience this question came from