Imagine you have an array of numbers sorted in increasing order, but some numbers are negative. If you square each number, the result is not longer sorted because squaring a negative number makes it positive. Your task is to return a new array where the squares of the numbers are sorted in increasing order.
For example:
• Input: [-4, -1, 0, 3, 10]
• Squared: [16, 1, 0, 9, 100]
• Sorted: [0, 1, 9, 16, 100]
Brute Force Approach
import java.util.Arrays;
public class SortedSquares {
public int[] sortedSquares(int[] nums) {
// Step 1: Square each element
for (int i = 0; i < nums.length; i++) {
nums[i] = nums[i] * nums[i];
}
// Step 2: Sort the squared array
Arrays.sort(nums);
return nums;
}
}1. Square Each Element: Iterate through the array and replace each element with its square.
2. Sort the Array: Use a built-in sorting method (e.g., Arrays.sort()) to sort the squared values.
3. Time Complexity: O(n log n) due to the sorting step.
4. Space Complexity: O(1) additional space if sorting is done in-place
The Optimal Solution: Two-Pointer Technique
The key idea here is to use the two-pointer technique. Let’s break it down step by step.
1. Two Pointers at the Ends
• Start with two pointers:
• left pointing to the first element of the array.
• right pointing to the last element of the array.
2. Compare Absolute Values
• Compare the absolute values of the numbers at the left and right pointers. The larger absolute value will give the largest square, so that’s what we’ll place in the result array (starting from the end).
3. Move Pointers Inward
• After placing the larger square, move the corresponding pointer inward:
• If the left value was larger, move the left pointer to the right.
• Otherwise, move the right pointer to the left.
4. Repeat Until Done
• Keep comparing and placing squares into the result array until all elements are processed.
public class SortedSquares {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] result = new int[n];
int left = 0, right = n - 1;
for (int i = n - 1; i >= 0; i--) {
if (Math.abs(nums[left]) > Math.abs(nums[right])) {
result[i] = nums[left] * nums[left];
left++;
} else {
result[i] = nums[right] * nums[right];
right--;
}
}
return result;
}
}Line-By-Line Explanation
Step 1: Intialization
int n = nums.length;
int[] result = new int[n];
int left = 0, right = n - 1;• The result array stores the final output.
• The left and right pointers allow us to compare the absolute values of numbers at both ends, a key step in the two-pointer technique.
Step 2: Iterative Comparison and Placement
for (int i = n - 1; i >= 0; i--) {- Loops through the result array from the last index (n-1) to the first (0).
- The largest squares are computed first and placed in the largest available position in the result array.
- Traversing backwards avoids the need to shift elements later.
Step 3: Compare absolute values
if (Math.abs(nums[left]) > Math.abs(nums[right]))- Compares the absolute values of the numbers at the left and right pointers.
- Determines which end of the array contributes the larger square.
Step 4: Square values (left)
result[i] = nums[left] * nums[left]; left++;- Squares the value at nums[left], stores it in the current position i of the result array, and increments left to process the next value.
- Ensures the larger of the two squared values is placed in the correct position.
Step 5: Square values (right)
result[i] = nums[right] * nums[right]; right--;- Handles the case where the square of nums[right] is larger than or equal to nums[left].
Step 6: return
return result;- Returns the fully populated and sorted result array.
Conclusion
The two-pointer technique is a powerful tool for problems like this. By taking advantage of the sorted nature of the input, you can solve problems in linear time that would otherwise require sorting. With practice, you’ll find that this approach works for many other challenges too.
Now it’s your turn—try writing your own implementation, and don’t forget to test it with edge cases! 🚀
