Quick 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.

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

Given an integer array nums in nondecreasing order, return a new array containing the square of each value in nondecreasing order. Preserve duplicate squares. Seek a linear-time solution rather than sorting the squares. For example, [-5,-2,0,3] becomes [0,4,9,25].

Constraints

  • nums is already in nondecreasing order.
  • 1 <= nums.length <= 10000.
  • Each value is between -10000 and 10000, inclusive.
  • Return a new array and preserve duplicate squares.

Examples

Input: ([-5, -2, 0, 3],)

Expected Output: [0, 4, 9, 25]

Explanation: The published mixed-sign example.

Input: ([0],)

Expected Output: [0]

Explanation: The minimum length with zero.

Hints

  1. The most negative remaining number can have the largest square.
  2. Fill the result from its largest end.

Loading coding console...

Show the approach

Approach

The largest absolute value among the remaining sorted input lies at one of its endpoints, so its square belongs at the rightmost unfilled output position. Compare the endpoints, write the larger square, and shrink that side. The invariant leaves the unprocessed input between the two pointers and fills the output suffix in sorted order. After n placements, every square appears once, including duplicates.

Time complexity:
O(n)
Space complexity:
O(n) for the returned array