Square sorted array Editorial

Practice Problem Link: Square sorted array | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array of numbers, return an array that contains the squares of all the numbers in non-decreasing order.

Naive Approach

If we change all the elements in the array to their absolute value, this problem can be solved easily. All that needs to be done now is to take the smallest element of the array one by one, square it and insert it in a new array.

Analysis

• Time Complexity: O(n²)
• Space Complexity: O(n)

Implementation

C++

vector<int> getSquareSortedArray(vector<int> &arr) {
   int n = arr.size();
   for (int i = 0; i < n; i++) {
       arr[i] = abs (arr[i]);
   }
   vector<int> ans;
   for( int i = 0; i < n; i++) {
       int currentMinimum = INT_MAX;
       int indx;
       for (int j = 0; j < n ; j++) {
           if (arr[j] < currentMinimum) {
               currentMinimum = arr[j];
               indx = j;
           }
       }
       arr[indx] = INT_MAX;
       ans.push_back(currentMinimum * currentMinimum);
   }
   return ans;
}

Java

class Solution {
   int[] getSquareSortedArray (int[] arr) {
       int n = arr.length;
       for (int i = 0; i < n; i++) {
           arr[i] = Math.abs (arr[i]);
       }
       int[] ans = new int[n];
       for( int i = 0; i < n; i++) {
           int currentMinimum = Integer.MAX_VALUE;
           int indx = -1;
           for (int j = 0; j < n ; j++) {
               if (arr[j] < currentMinimum) {
                   currentMinimum = arr[j];
                   indx = j;
               }
           }
           arr[indx] = Integer.MAX_VALUE;
           ans[i] = (currentMinimum * currentMinimum);
       }
       return ans;
   }
}

Optimal Approach

In this problem, the optimal approach is pretty simple and straightforward. First, all elements of the array can be squared and then sorted.

Analysis

• Time Complexity: O(n * log(n))
• Space Complexity: O(1)

Implementation

C++

vector<int> getSquareSortedArray(vector<int> &arr) {
   for (int i = 0; i < arr.size(); i++) {
       arr[i] *= arr[i];
   }
   sort (arr.begin(), arr.end());
   return arr;
}

Java

class Solution {
   int[] getSquareSortedArray (int[] arr) {
       for (int i = 0; i < arr.length; i++) {
           arr[i] *= arr[i];
       }
       Arrays.sort(arr);
       return arr;
   }
}