977. Squares of a Sorted Array
Model: qwen2.5-coder:14b
Topics: Array,Two Pointers
FAANG asked: 1
Acceptance rate: 71.8%
Problem Breakdown
The problem requires us to take an integer array nums that is sorted in non-decreasing order, square each element of the array, and then return the squared elements sorted in non-decreasing order. The input is a list of integers, and the output should also be a list of integers. The key constraints are that the input array can contain negative numbers, zeros, and positive numbers, and it is already sorted.
Intuition
A brute-force approach would involve squaring each element of the array and then sorting the resulting array. This approach has a time complexity of (O(n \log n)) due to the sorting step, which is not optimal given that we need an (O(n)) solution.
The key insight is to use a two-pointer technique. Since the input array is sorted, the largest possible square will come from either the smallest or the largest element in the array (considering negative numbers). We can initialize two pointers: one at the start of the array and another at the end. By comparing the absolute values of the elements pointed to by these two pointers, we can determine which squared value is larger and place it at the beginning of a new result array. This way, we build the result array from largest to smallest square, and then reverse it to get the final sorted order.
Approach
- Initialize two pointers:
leftat the start of the array andrightat the end. - Create an empty result array of the same length as the input array.
- Use a while loop to iterate until
leftis less than or equal toright. - Compare the absolute values of
nums[left]andnums[right]. - Place the larger square at the end of the result array and move the corresponding pointer (
leftorright) inward. - After the loop, reverse the result array to get the final sorted order.
Complexity Analysis
- Time Complexity: (O(n)), where (n) is the length of the input array. We iterate through the array once with two pointers.
- Space Complexity: (O(n)) for storing the result array.
Solution
def sortedSquares(nums):
n = len(nums)
left, right = 0, n - 1
result = [0] * n
while left <= right:
if abs(nums[left]) > abs(nums[right]):
result[right - left] = nums[left] ** 2
left += 1
else:
result[right - left] = nums[right] ** 2
right -= 1
return result[::-1]
Edge Cases Handled
- All negative numbers: The two-pointer approach naturally handles this case by always choosing the larger square from the ends of the array.
- All positive numbers: Similarly, the approach works as it will always choose the largest square from the end.
- Mixed negative and positive numbers: The approach correctly identifies that the largest squares can come from either end of the array.
- Single element array: The algorithm handles this by simply squaring the single element.
- Empty array: While not explicitly mentioned in the constraints, if the input is an empty array, the function will return an empty array as expected.