Squares Of A Sorted Array

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 squares
var 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;
};
vector sortedSquares(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;
    }
}


Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]