How do you solve Squares of a Sorted Array on LeetCode?

Squares of a Sorted Array (LeetCode #977) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The input array is sorted, which allows for efficient squaring and placement using two pointers.

What is the brute force solution for Squares of a Sorted Array?

The brute force approach for Squares of a Sorted Array is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute force approach involves squaring each element in the array and then sorting the resulting array. This is straightforward but inefficient, as sorting can be time-consuming. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Squares of a Sorted Array?

Squares of a Sorted Array uses the following concepts: Array, Two Pointers, Sorting. The recommended patterns to study are: Two Pointers, Array.

What are the interview tips for Squares of a Sorted Array?

Always clarify if the input is sorted; this can lead to more efficient solutions. Think about edge cases, such as arrays with all negative numbers or all positive numbers. Practice explaining your thought process as you code; this helps interviewers follow your logic.

What are common mistakes when solving Squares of a Sorted Array?

Forgetting to sort the squared values in the brute force approach. Not considering the negative numbers and their squares in the optimal approach.

#977

Squares of a Sorted Array

Easy

ArrayTwo PointersSortingTwo PointersArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(n)

💡

Intuition

Time O(n)Space O(n)

Using a two-pointer technique allows us to efficiently square and sort the elements without needing to sort the entire array after squaring. This is possible because the original array is sorted.

⚙️

Algorithm

5 steps

1Step 1: Initialize two pointers, one at the beginning (left) and one at the end (right) of the array.
2Step 2: Create a result array of the same length as the input array.
3Step 3: Iterate from the end of the result array to the beginning, comparing the absolute values of the elements at the two pointers.
4Step 4: Square the larger absolute value and place it at the current position in the result array, then move the corresponding pointer inward.
5Step 5: Continue until all elements are processed.

solution.py12 lines

1def sortedSquares(nums):
2    left, right = 0, len(nums) - 1
3    result = [0] * len(nums)
4    for i in range(len(nums) - 1, -1, -1):
5        if abs(nums[left]) > abs(nums[right]):
6            result[i] = nums[left] * nums[left]
7            left += 1
8        else:
9            result[i] = nums[right] * nums[right]
10            right -= 1
11    return result
12print(sortedSquares([-4, -1, 0, 3, 10]))

ℹ

Complexity note: The time complexity is O(n) because we only traverse the array once with two pointers. The space complexity is O(n) for the result array.

1The input array is sorted, which allows for efficient squaring and placement using two pointers.
2The largest squares will always be at the ends of the sorted array.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.