Problem Statement
Given a sorted array of integers, return an array of
the squares of each number sorted in non-decreasing
order.
Sample Test Case
Input
- Array: [-4, -1, 0, 3, 10]
Output
- Squared and sorted array: [0, 1, 9, 16, 100]
Approaches
Brute Force Approach
Idea
- Square all the elements of the array and then sort the squared elements.
Steps
- Square each element in the array.
- Sort the squared array.
Time Complexity
- O(n log n) due to the sorting step, where n is the number of elements in the array.
Space Complexity
- O(n) due to the additional array to store the squares.
Example Code (JavaScript)
Dry Run
- Input:
[-4, -1, 0, 3, 10]
- After squaring:
[16, 1, 0, 9, 100]
- After sorting:
[0, 1, 9, 16, 100]
Efficient Approach (Two-pointer Approach)
Idea
Use two pointers: one starting from the beginning (for the smallest values) and the other from the end (for the largest values). Compare the absolute values of the two pointers, square them, and insert the larger one at the correct position in the result array.
Steps
- Initialize two pointers:
left at the beginning and right at the end of the array.
- Compare the absolute values of the elements at these pointers.
- Place the larger square at the
end of the result array, and move the corresponding pointer (either left or right).
- Repeat until all elements are processed.
Time Complexity
- O(n), where n is the number of elements in the array.
Space Complexity
- O(1), Auxiliary space is not counted as space complexity
Example Code (JavaScript)
Dry Run
Input: [-4, -1, 0, 3, 10]
- Step 1: Compare
|arr[0]| = 4 and |arr[4]| = 10. Place 100 in result.
- Step 2: Compare
|arr[0]| = 4 and |arr[3]| = 3. Place 16 in result.
- Step 3: Compare
|arr[1]| = 1 and |arr[3]| = 3. Place 9 in result.
- Step 4: Compare
|arr[1]| = 1 and |arr[2]| = 0. Place 1 in result.
- Step 5: Place
0 in result.
Output: [0, 1, 9, 16, 100]
Example Test Case
Input: [-7, -3, 2, 3, 11]
Output: [4, 9, 9, 49, 121]
Complexity Analysis
Brute Force Approach:
- Time Complexity:
O(n log n) due to the sorting step.
- Space Complexity:
O(n) for storing the squared elements.
Efficient Approach (Two-pointer):
- Time Complexity:
O(n), as we only make one pass through the array.
- Space Complexity:
O(n), since we need an additional array to store the result.
Conclusion
The brute force approach is simple but less efficient due to the sorting step. The efficient two-pointer approach provides a faster solution, making it optimal for larger arrays.