Sorted Squared Array

• Difficulty: Easy

Write a function that takes in a non-empty array of integers that are sorted in ascending order and returns a new array of the same length with the squares of the original integers also sorted in ascending order.

• Even though the initial array is sorted, squaring the elements can disturb the order because negative numbers become positive after squaring.

[-7, -3, -1, 4, 8]

Squares → [49, 9, 1, 16, 64]

• This is not sorted anymore, so we must handle ordering carefully.

Brute Force#

Square every element and then re-sort the resulting array. The sorting step is necessary because squaring a negative number can produce a value larger than adjacent positive squares, breaking the original order. This gives O(n log n) time — fast enough for most inputs, but it ignores the fact that the input is already sorted and wastes the opportunity to run in linear time.

• The simplest idea is:
  • Square every number in the array.
  • Since squaring might disturb the order, sort the squared values again.

#include <vector>
using namespace std;

vector<int> sortedSquaredArray(vector<int> array) {
  vector<int> result;
  for(auto num: array){
    result.push_back(num*num);
  }
  sort(result.begin(), result.end());
  return result;
}

Time Complexity: O(nlogn)

Space Complexity: O(n)

Optimal Approach#

The key insight is that in a sorted array, the largest squares must come from one of the two ends — either the most-negative left element or the most-positive right element will produce the largest absolute value. We fill the result array from right to left: compare abs(array[left]) and abs(array[right]), write the larger square at the current back position, and advance the corresponding pointer inward. This single pass avoids re-sorting entirely, reducing time to O(n) while still requiring O(n) space for the output array.

• Observation: In a sorted array, the largest square will always come from one of the ends.
• Use two pointers:
  • smallerIdx → start of array
  • largerIdx → end of array
• Compare the absolute values of the two ends.
• The larger absolute value produces the larger square.
• Place that square at the end of the result array.
• Move the corresponding pointer inwards.

#include <vector>
using namespace std;

vector<int> sortedSquaredArray(vector<int> array) {
  vector<int> resultArray(array.size(), 0);
  int smallerIdx = 0;
  int largerIdx = array.size()-1;

  for(int idx = array.size()-1; idx >= 0; idx--){
    int smallerVal = array[smallerIdx];
    int largerVal = array[largerIdx];

    if(abs(smallerVal) > abs(largerVal)){
      resultArray[idx] = smallerVal * smallerVal;
      smallerIdx++;
    }else{
      resultArray[idx] = largerVal * largerVal;
      largerIdx--;
    }
  }
  
  return resultArray;
}

Time Complexity: O(n)

Space Complexity: O(n)