What is the two-pointer approach in the Squares of a Sorted Array problem?

The two-pointer approach involves using two pointers, one at the start and one at the end of the sorted array. You square the larger number at both ends and place the square at the correct position in the result array.

Why is the time complexity O(n) for the two-pointer solution?

Each element of the array is processed once, either by moving the left or right pointer, ensuring a linear time complexity of O(n).

Can we solve the Squares of a Sorted Array problem without extra space?

Yes, it is possible to solve the problem in-place by modifying the input array to hold the squared elements in non-decreasing order.

How does the solution handle arrays with negative numbers?

The two-pointer technique works by comparing the absolute values of the numbers, so it efficiently handles arrays with both negative and positive numbers.

What are common mistakes when solving this problem?

Common mistakes include failing to use the two-pointer technique correctly, sorting the array after squaring, and not handling edge cases like arrays with one element.

#977

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

有序数组的平方

给你一个按非递减顺序排序的整数数组 nums ，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。示例 1：输入： nums = [-4,-1,0,3,10] 输出： [0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100] 排序后，数组变为 [0,…

数组双指针排序

题目描述

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

1 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums 已按 非递减顺序 排序

进阶：

请你设计时间复杂度为 O(n) 的算法解决本问题

lightbulb

解题思路

方法一：双指针

由于数组 $nums$ 已经按照非递减顺序排好序，所以数组中负数的平方值是递减的，正数的平方值是递增的。我们可以使用双指针，分别指向数组的两端，每次比较两个指针指向的元素的平方值，将较大的平方值放入结果数组的末尾。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $nums$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        ans = []
        i, j = 0, len(nums) - 1
        while i <= j:
            a = nums[i] * nums[i]
            b = nums[j] * nums[j]
            if a > b:
                ans.append(a)
                i += 1
            else:
                ans.append(b)
                j -= 1
        return ans[::-1]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for clarity in how the candidate explains the two-pointer method and its impact on the algorithm's time complexity.
question_mark
The ability to optimize space usage while maintaining linear time is crucial.
question_mark
Pay attention to how well the candidate understands the failure mode of directly sorting the squared elements.

warning

常见陷阱

外企场景

error
Failing to maintain the two-pointer invariant, which may lead to incorrect results or inefficient solutions.
error
Incorrectly using extra space for sorting the squared numbers, which can lead to an O(n log n) time complexity.
error
Not handling edge cases, such as arrays with a single element or all non-negative numbers.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the approach to work in-place without using extra space for a result array.
arrow_right_alt
Handle arrays with both positive and negative numbers, ensuring that the squares are correctly placed in non-decreasing order.
arrow_right_alt
Adapt the solution to work with larger inputs by considering more efficient memory management.

help

常见问题

外企场景

继续练习

#969 煎饼排序 #948 令牌放置 #923 三数之和的多种可能