💬 Discord
Sign In
NeetCode #185LC-977EasyTwo Pointers
← Back to All Problems

#185 · #977 · Squares of a Sorted Array(有序数组的平方)

📌 Problem Statement & Constraints

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number, also sorted in non-decreasing order. Constraints: 1 <= nums.length <= 10^4, -10^4 <= nums[i] <= 10^4.

💡 Core Algorithmic Approaches

  1. Squaring destroys the sorted order because negative numbers become positive. But the largest square is always at one of the two ends.
  2. Use two pointers at the ends and fill the result from the back, always placing the larger square.
  3. This avoids re-sorting, giving O(n) instead of O(n log n).
  4. The approach exploits the fact that the absolute values form a unimodal (V-shaped) sequence.

💻 Benchmark Python3 Implementation

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [0] * n
        l, r = 0, n - 1
        for k in range(n - 1, -1, -1):   # fill from the largest square down
            if abs(nums[l]) > abs(nums[r]):
                res[k] = nums[l] * nums[l]
                l += 1
            else:
                res[k] = nums[r] * nums[r]
                r -= 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass, no sorting.
💾 Space Complexity
O(n) for the result (unavoidable), O(1) extra.

⚠️ Interview Pitfalls & Follow-ups

  • Squaring and then sorting: O(n log n) and misses the two-pointer insight.
  • Filling the result from the front: you would be placing the smallest squares first, but the smallest is in the middle -- filling from the back is what makes the greedy work.
  • Comparing nums[l] > nums[r] instead of the absolute values: negative numbers break the comparison.
  • Using abs() on every iteration: fine, but comparing squared values avoids the function call; both are O(1).