DEV Community

loading...
Cover image for LeetCode 977. Squares of a Sorted Array

LeetCode 977. Squares of a Sorted Array

cod3pineapple profile image codingpineapple ・1 min read

Description:

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Solution:

Time complexity : O(n)

// This solution uses a Two Pointer Technique
// We compare the square of the element at the right pointer
// with the element at the left pointer
// We add the max square value to the output array, 
// then we move that element's pointer closer to 
// the opposite side
// We repeat this process until the pointers are equal
// or one pointer has moved past the other
var sortedSquares = function(A) {
        const output = [];
        // define pointers
        let left = 0;
        let right = A.length - 1;
        // index in output array we will add values
        let i = right;
        while (left <= right) {
            // get squared values
            const leftVal = Math.pow(A[left], 2);
            const rightVal = Math.pow(A[right], 2);
            // compare squared values
            if(leftVal > rightVal) {
                // add element to output[i], then subtract 1 
                // from i
                // move pointer closer to the opposite side
                output[i--] = leftVal;
                left++;
            } else {
                output[i--] = rightVal;
                right--;
            }
        }
        return output;
};

Discussion (0)

pic
Editor guide