Back to Problem
Official 1765 views

Editorial: Squares of a Sorted Array

by admin ·

6

1 Intuition

The largest square is always at one of the two ends.

2 Approach

Use two pointers at both ends and fill the result from the back with the larger square.

3 Complexity Analysis

Time O(n), Space O(n).

4 Solution Code 

class Solution:
    def sortedSquares(self, nums: list[int]) -> list[int]:
        n = len(nums)
        out = [0] * n
        lo, hi = 0, n - 1
        for k in range(n - 1, -1, -1):
            if abs(nums[lo]) > abs(nums[hi]):
                out[k] = nums[lo] * nums[lo]
                lo += 1
            else:
                out[k] = nums[hi] * nums[hi]
                hi -= 1
        return out

5 Code Walkthrough

The reference solution below implements the approach step by step.