Lets Code Them Up!

Squares of a Sorted Array

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]

Note:

  1. 1 <= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. A is sorted in non-decreasing order.

Solution

The straightforward solution that comes to mind after reading the problem statement is –

  1. Loop through the array and replace each number by its square.
  2. Sort the resulting array.

The space complexity of O(1) as we are using the same array and no extra space. But the time complexity is O(n log n) ie the complexity of sorting.

/**
 * SquareSortedArray.java
 * Purpose: Squares of a Sorted Array
 *
 * @author Megha Rastogi
 * @version 1.0 08/09/2020
 */
class SquareSortedArray {
   /**
     * Find Squares of a Sorted Array
     *
     * @param Array, A
     * @return Array, A
     */
    public int[] sortedSquares(int[] A) {
    
        // loop through the array and replace each element
        // by it's square
        for(int i = 0; i < A.length; i++){
            A[i] = A[i] * A[i];
        }
        
        // Sort the squared array
        Arrays.sort(A);
        
        // return the sorted array
        return A;
    }
}

Optimized Solution

Another solution is using the two pointer technique. Since array is sorted and it has negative and positive elements, the squares of negative will be in decreasing order and that of positive will be in increasing order. We can use this information and compare the start element with end element and put the larger element at the end position.

  1. Initialize two pointers start and end pointing to start and end indices of the array. Also initialize another pointer (index) to keep track of current index of result array.
  2. Loop until start <= end
    1. Find the square of the start (powStart) and end (powEnd) elements.
    2. If powStart > powEnd, result[index] becomes powStart, increment index, increment start.
    3. if powEnd > powStart, result[index] becomes powEnd, increment index, decrement end.

Here the time complexity becomes O(n) and space complexity is also O(n)

/**
 * SquareSortedArrayOptimized.java
 * Purpose: Squares of a Sorted Array
 *
 * @author Megha Rastogi
 * @version 1.0 08/09/2020
 */
class SquareSortedArrayOptimized {
   /**
     * Find Squares of a Sorted Array
     *
     * @param Array, A
     * @return Array, ans
     */
    public int[] sortedSquares(int[] A) {
    
        // return null if array is null
        if (A == null) return null;
        
        // initialize the result array
        int [] ans = new int[A.length];
     
        // initialize start and end pointers to start and end index of array
        int start = 0, end = A.length - 1;
       
        int i = end; // insert position.
       
        // Loop until start is less than equal to end
        while (start <= end) { 
            
            // finding square of start and end element
            int pow1 = A[start] * A[start];
            int pow2 = A[end] * A[end];
           
            // if power of start is bigger, 
            // ith element must be start element
            // increment start as we placed first negative number
            // else ith element will be end element
            if (pow1 > pow2) {
                ans[i--] = pow1;
                start++;
            } else {
                ans[i--] = pow2;
                end--;
            }
        }
       
        // return the result array
        return ans;
    }
}

Source – leetcode

Code – SquareSortedArray.java, SquareSortedArrayOptimized.java

Megha

,