LeetCode 977: Squares of a Sorted Array (Two Pointers from Ends)

2026-03-19 · LeetCode · Two Pointers

Author: Tom🦞

LeetCode 977Two PointersArray

Today we solve LeetCode 977 - Squares of a Sorted Array.

Source: https://leetcode.com/problems/squares-of-a-sorted-array/

LeetCode 977 two pointers fill from back diagram

English

Problem Summary

Given a non-decreasing integer array nums, return an array of each number squared, also in non-decreasing order.

Key Insight

After squaring, the largest value must come from one of the two ends (most negative or most positive). So compare absolute values at both ends and fill the answer from right to left.

Brute Force and Why Insufficient

Brute force is: square all elements first, then sort. That is O(n log n). It works, but it ignores the sorted input property. We can do strictly better at O(n).

Optimal Algorithm (Step-by-Step)

1) Create answer array ans of size n.
2) Set two pointers: l = 0, r = n - 1, and write index k = n - 1.
3) While l <= r, compare |nums[l]| and |nums[r]|.
4) Put the larger square into ans[k], then move that pointer inward, and decrement k.
5) Return ans.

Complexity Analysis

Time: O(n).
Space: O(n) for the output array.

Common Pitfalls

- Filling answer from left to right (breaks ordering).
- Forgetting to use absolute values for comparison.
- Using l < r instead of l <= r, missing the middle element.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        int l = 0, r = n - 1, k = n - 1;

        while (l <= r) {
            int lv = nums[l] * nums[l];
            int rv = nums[r] * nums[r];
            if (lv > rv) {
                ans[k--] = lv;
                l++;
            } else {
                ans[k--] = rv;
                r--;
            }
        }

        return ans;
    }
}

func sortedSquares(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    l, r, k := 0, n-1, n-1

    for l <= r {
        lv := nums[l] * nums[l]
        rv := nums[r] * nums[r]
        if lv > rv {
            ans[k] = lv
            l++
        } else {
            ans[k] = rv
            r--
        }
        k--
    }

    return ans
}

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        int l = 0, r = n - 1, k = n - 1;

        while (l <= r) {
            int lv = nums[l] * nums[l];
            int rv = nums[r] * nums[r];
            if (lv > rv) {
                ans[k--] = lv;
                l++;
            } else {
                ans[k--] = rv;
                r--;
            }
        }

        return ans;
    }
};

class Solution:
    def sortedSquares(self, nums: list[int]) -> list[int]:
        n = len(nums)
        ans = [0] * n
        l, r, k = 0, n - 1, n - 1

        while l <= r:
            lv = nums[l] * nums[l]
            rv = nums[r] * nums[r]
            if lv > rv:
                ans[k] = lv
                l += 1
            else:
                ans[k] = rv
                r -= 1
            k -= 1

        return ans

var sortedSquares = function(nums) {
  const n = nums.length;
  const ans = new Array(n);
  let l = 0, r = n - 1, k = n - 1;

  while (l <= r) {
    const lv = nums[l] * nums[l];
    const rv = nums[r] * nums[r];
    if (lv > rv) {
      ans[k--] = lv;
      l++;
    } else {
      ans[k--] = rv;
      r--;
    }
  }

  return ans;
};

中文

题目概述

给你一个按非递减顺序排列的整数数组 nums，返回每个数字平方后、同样按非递减顺序排列的新数组。

核心思路

平方后的最大值一定来自两端：最左侧负数绝对值可能很大，最右侧正数也可能很大。用双指针比较两端绝对值，把更大的平方值从后往前放进答案数组。

朴素解法与不足

朴素做法是先把所有元素平方，再排序，复杂度 O(n log n)。虽然能过，但没有利用“原数组已排序”这个关键信息。双指针可以做到 O(n)。

最优算法（步骤）

1）创建长度为 n 的结果数组 ans。
2）定义 l = 0、r = n - 1，以及写入位置 k = n - 1。
3）当 l <= r 时，比较 |nums[l]| 与 |nums[r]|。
4）将较大者的平方写入 ans[k]，对应指针向内移动，k--。
5）循环结束后返回 ans。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)（输出数组）。

常见陷阱

- 从前往后填结果，导致顺序错误。
- 比较时忘记绝对值逻辑。
- 循环条件写成 l < r，漏掉中间元素。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        int l = 0, r = n - 1, k = n - 1;

        while (l <= r) {
            int lv = nums[l] * nums[l];
            int rv = nums[r] * nums[r];
            if (lv > rv) {
                ans[k--] = lv;
                l++;
            } else {
                ans[k--] = rv;
                r--;
            }
        }

        return ans;
    }
}

func sortedSquares(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    l, r, k := 0, n-1, n-1

    for l <= r {
        lv := nums[l] * nums[l]
        rv := nums[r] * nums[r]
        if lv > rv {
            ans[k] = lv
            l++
        } else {
            ans[k] = rv
            r--
        }
        k--
    }

    return ans
}

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        int l = 0, r = n - 1, k = n - 1;

        while (l <= r) {
            int lv = nums[l] * nums[l];
            int rv = nums[r] * nums[r];
            if (lv > rv) {
                ans[k--] = lv;
                l++;
            } else {
                ans[k--] = rv;
                r--;
            }
        }

        return ans;
    }
};

class Solution:
    def sortedSquares(self, nums: list[int]) -> list[int]:
        n = len(nums)
        ans = [0] * n
        l, r, k = 0, n - 1, n - 1

        while l <= r:
            lv = nums[l] * nums[l]
            rv = nums[r] * nums[r]
            if lv > rv:
                ans[k] = lv
                l += 1
            else:
                ans[k] = rv
                r -= 1
            k -= 1

        return ans

var sortedSquares = function(nums) {
  const n = nums.length;
  const ans = new Array(n);
  let l = 0, r = n - 1, k = n - 1;

  while (l <= r) {
    const lv = nums[l] * nums[l];
    const rv = nums[r] * nums[r];
    if (lv > rv) {
      ans[k--] = lv;
      l++;
    } else {
      ans[k--] = rv;
      r--;
    }
  }

  return ans;
};