Leetcode 977: Squares of a Sorted Array
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each element, sorted in non-decreasing order.
Problem
Approach
Steps
Complexity
Input: An integer array nums sorted in non-decreasing order.
Example: nums = [-6, -3, 0, 2, 8]
Constraints:
• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in non-decreasing order.
Output: An array containing the squares of each number from nums, sorted in non-decreasing order.
Example: [0, 9, 36, 64, 81]
Constraints:
• The output should be sorted in non-decreasing order.
Goal: Square each element and sort the resulting array.
Steps:
• Square each element of the array.
• Use a two-pointer approach to combine the negative and positive elements efficiently, leveraging their positions in the sorted array.
Goal: Ensure inputs adhere to the problem's constraints.
Steps:
• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in non-decreasing order.
Assumptions:
• The array nums is already sorted in non-decreasing order.
• Input: nums = [-6, -3, 0, 2, 8]
• Explanation: Squaring each element results in [36, 9, 0, 4, 64]. After sorting, we get [0, 9, 36, 64, 81].
• Input: nums = [-10, -5, 1, 4, 7]
• Explanation: Squaring each element results in [100, 25, 1, 16, 49]. After sorting, we get [1, 16, 25, 49, 100].
Approach: Use a two-pointer technique to process the squares of the sorted array efficiently in O(n) time.
Observations:
• The array is already sorted, so we can efficiently merge the positive and negative squares using a two-pointer approach.
• We can avoid sorting by directly placing the largest squares at the correct positions from the end of the result array.
Steps:
• Initialize two pointers: one at the beginning (left) and one at the end (right) of the array.
• Compare the squares of the elements at the two pointers and place the larger square at the correct position in the result array (starting from the last position).
• Move the pointer (either left or right) accordingly to continue processing the array.
• Return the result array once the two pointers have processed all elements.
Empty Inputs:
• An empty input array, which should return an empty result.
Large Inputs:
• A large input array, ensuring that the solution handles up to the maximum input size efficiently.
Special Values:
• All elements being zero.
Constraints:
• The array must be sorted in non-decreasing order.
vector<int> sortedSquares(vector<int>& nums) {
vector<int> ans(nums.size());
int l = 0, r = nums.size() - 1;
int ll, rr;
for(int i = nums.size() - 1; i >= 0; i--) {
ll = nums[l] * nums[l];
rr = nums[r] * nums[r];
if(ll < rr) ans[i] = rr, r--;
else ans[i] = ll, l++;
}
return ans;
}
1 : Function Definition
vector<int> sortedSquares(vector<int>& nums) {
Defines the function `sortedSquares`, which takes a reference to a vector of integers `nums` and returns a vector of integers containing the squares of each element in sorted order.
2 : Initialize Answer Vector
vector<int> ans(nums.size());
Initializes a vector `ans` with the same size as `nums` to store the squared values of the elements in sorted order.
3 : Initialize Pointers
int l = 0, r = nums.size() - 1;
Initializes two pointers `l` and `r` to point to the beginning and end of the `nums` array, respectively.
4 : Variable Declarations
int ll, rr;
Declares two integer variables `ll` and `rr` to store the squared values of the elements at the `l` and `r` pointers.
5 : Loop Over Array
for(int i = nums.size() - 1; i >= 0; i--) {
Starts a loop to iterate from the end of the `ans` array towards the beginning. The loop continues as long as there are elements left to process.
6 : Calculate Square of Left Element
ll = nums[l] * nums[l];
Calculates the square of the element at the `l` pointer and stores it in `ll`.
7 : Calculate Square of Right Element
rr = nums[r] * nums[r];
Calculates the square of the element at the `r` pointer and stores it in `rr`.
8 : Choose Larger Square
if(ll < rr) ans[i] = rr, r--;
Compares the squares `ll` and `rr`. If `ll` is smaller, assigns `rr` to `ans[i]` and moves the `r` pointer one step left.
9 : Choose Smaller Square
else ans[i] = ll, l++;
If `ll` is greater than or equal to `rr`, assigns `ll` to `ans[i]` and moves the `l` pointer one step right.
10 : Return Statement
return ans;
Returns the sorted `ans` array, which contains the squares of the elements in `nums` sorted in non-decreasing order.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The two-pointer approach processes each element once, leading to a time complexity of O(n).
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the result array.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus