Solution For Squares Of A Sorted Array
The Squares of a Sorted Array problem on LeetCode is a relatively simple problem that can be solved in O(n) time complexity.
Problem Description:
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Example 1:
Input: nums = [-4,-1,0,3,10] Output: [0,1,9,16,100] Explanation: After squaring, the array becomes [16,1,0,9,100]. Sorting the array returns [0,1,9,16,100].
Example 2:
Input: nums = [-7,-3,2,3,11] Output: [4,9,9,49,121]
Solution:
One approach is to take the absolute values of each element of the input array and then square the absolute values. After that, we sort the squared array in non-decreasing order and return it.
Here is the implementation of the above approach:
“`python
def sortedSquares(nums: List[int]) -> List[int]:
# Initialize left index and right index
left = 0
right = len(nums) – 1
result = [0] * len(nums)
index = len(nums) – 1
# Loop from the right end of the array to the left end of the array
# and fill the result array in non-decreasing order
while index >= 0:
if abs(nums[left]) > abs(nums[right]):
result[index] = nums[left] * nums[left]
left += 1
else:
result[index] = nums[right] * nums[right]
right -= 1
index -= 1
return result
“`
In this solution, we use two-pointers to iterate over the input array from both ends. The two pointers are left and right indices initialized as 0 and len(nums)-1, respectively. We also initialize another array called ‘result’. The result array is initialized as an array of zeros of the same length as the input array.
After initializing the indices and the result array, we use a while loop to iterate from the right end of the array to the left end of the array. Inside the while loop, we square the value of the element that has a larger absolute value and store it in the result array in non-decreasing order. If the absolute value of the element at the left pointer is greater than that of the right pointer, then we square the element at the left pointer and increment the left pointer. Otherwise, we square the element at the right pointer and decrement the right pointer. We keep decrementing the index until all values are filled in the result array.
Finally, we return the result array as an output.
The time complexity of this solution is O(n) and the space complexity is also O(n) where n is the length of the input array.
Step by Step Implementation For Squares Of A Sorted Array
class Solution {
public int[] sortedSquares(int[] A) {
//edge case
if(A == null || A.length == 0){
return A;
}
//initialize result array
int[] result = new int[A.length];
//two pointers
int left = 0;
int right = A.length - 1;
//index for result array
int index = A.length - 1;
//while left pointer is less than right pointer
while(left <= right){
//if absolute value of left element is greater than absolute value of right element
if(Math.abs(A[left]) > Math.abs(A[right])){
//add square of right element to result array
result[index] = A[right] * A[right];
//decrement right pointer
right--;
}
//if absolute value of left element is less than absolute value of right element
else{
//add square of left element to result array
result[index] = A[left] * A[left];
//increment left pointer
left++;
}
//decrement index
index--;
}
//return result array
return result;
}
}def sortedSquares(self, A: List[int]) -> List[int]:
#edge case if the list is empty
if not A:
return []
#initialize 2 pointers, one at the beginning and one at the end of the list
left = 0
right = len(A) - 1
#create a new list to store the sorted squares
squares = []
#while the pointers have not met in the middle
while left <= right:
#if the left pointer has a smaller absolute value, append it to the list and move the pointer to the right
if abs(A[left]) <= abs(A[right]):
squares.append(A[left] * A[left])
left += 1
#if the right pointer has a smaller absolute value, append it to the list and move the pointer to the left
else:
squares.append(A[right] * A[right])
right -= 1
#return the list of sorted squares
return squaresvar sortedSquares = function(A) {
// this function will take in an array of unsorted integers
// and return an array of the same integers, sorted in
// ascending order
// we can do this in O(n) time and O(1) space
// by keeping track of the current index of the
// smallest unsorted integer (i), and the current
// index of the largest unsorted integer (j)
// as we iterate through the array, we'll keep track
// of the current index of the largest sorted integer
// (k)
// we can sort the array in place by swapping the
// unsorted integers at indices i and j with the sorted
// integer at index k
let i = 0;
let j = A.length - 1;
let k = A.length - 1;
while (i <= j) {
// if the unsorted integer at index i is larger than
// the unsorted integer at index j, it should come after
// j in the sorted array
if (A[i] >= A[j]) {
// so we swap A[i] and A[k]
[A[i], A[k]] = [A[k], A[i]];
// and decrement k
k--;
// and decrement j
j--;
} else {
// otherwise, the unsorted integer at index j should
// come after i in the sorted array
// so we swap A[j] and A[k]
[A[j], A[k]] = [A[k], A[j]];
// and decrement k
k--;
// and increment i
i++;
}
}
// now that the array is sorted, we need to square each
// integer
for (let l = 0; l < A.length; l++) {
// we can square each integer in place
A[l] = A[l] * A[l];
}
return A;
};vectorsortedSquares(vector & A) { int n = A.size(); vector res(n); int i = 0, j = n - 1; for (int p = n - 1; p >= 0; p--) { if (abs(A[i]) > abs(A[j])) { res[p] = A[i] * A[i]; i++; } else { res[p] = A[j] * A[j]; j--; } } return res; }
public class Solution {
public int[] SortedSquares(int[] A) {
for(int i = 0; i < A.Length; i++) {
A[i] = A[i] * A[i];
}
Array.Sort(A);
return A;
}
}