#977

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Squares of a Sorted Array

The problem involves squaring elements of a sorted array and returning the squares in non-decreasing order.

Problem Statement

Given a sorted integer array, nums, return an array of the squares of each number in non-decreasing order. The solution should minimize extra space usage and avoid unnecessary sorting.

The key challenge is optimizing the process of squaring and sorting the elements without directly sorting the array after squaring, as the input array is already sorted.

Examples

Example 1

Input: nums = [-4,-1,0,3,10]

Output: [0,1,9,16,100]

After squaring, the array becomes [16,1,0,9,100]. After sorting, it becomes [0,1,9,16,100].

Example 2

Input: nums = [-7,-3,2,3,11]

Output: [4,9,9,49,121]

Example details omitted.

Constraints

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in non-decreasing order.

Solution Approach

Two-Pointer Approach

Start by initializing two pointers, one at the beginning and one at the end of the array. Compare the absolute values of the numbers at both ends, square the larger number, and place the square in the result array. Move the pointers inward, repeating the process until all elements are processed.

Merging the Results

As you square the elements from both ends of the array, fill the result array from the back (largest index), ensuring that the resulting array is filled in non-decreasing order without the need for a separate sorting step.

Time and Space Complexity Considerations

This approach ensures a time complexity of O(n) where n is the length of the array. Space complexity can be O(n) if an additional result array is used, or O(1) if the input array is modified in place.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The two-pointer approach works in linear time, O(n), because each element is processed exactly once. Space complexity is O(n) for the result array, but can be optimized to O(1) if we modify the input array in place.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Two Pointers

Since the array $nums$ is already sorted in non-decreasing order, the square values of the negative numbers in the array are decreasing, and the square values of the positive numbers are increasing. We can use two pointers, each pointing to the ends of the array. Each time we compare the square values of the elements pointed to by the two pointers, we put the larger square value at the end of the result array.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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]

Continue Practicing

#969 pancake sorting #948 bag of tokens #923 3sum with multiplicity