Problem statement

Sorted Squared Array - You are given an array of Integers in which each subsequent value is not less than the previous value. Write a function that takes this array as an input and returns a new array with the squares of each number sorted in ascending order.

Solution

Brute force

The brute force solution is to square each element and then sort the array. This would take O(nlogn) time and O(n) space.

Optimized

The optimized solution is to use two pointers, one at the beginning and one at the end of the array. Compare the squares of the two pointers and add the larger one to the result array. Then move the pointer of the larger value towards the center of the array. Repeat this process until the two pointers meet. This would take O(n) time and O(n) space.

Code

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

vector<int> sort_squared_slow(vector<int> arr) {

  int len = arr.size();
  vector<int> newArr(len, 0);

  for (int i = 0; i < len; i++) {
    newArr[i] = arr[i] * arr[i];
  }
  sort(newArr.begin(), newArr.end());
  return newArr;
}

vector<int> sort_squared(vector<int> arr) {
  int len = arr.size();
  vector<int> newArr(len, 0);
  for (int i = 0; i < len; i++) {
    arr[i] = arr[i] * arr[i];
  }

  int newArrIdx = len - 1;
  int startPtr = 0;
  int endPtr = len - 1;

  while (startPtr <= endPtr && newArrIdx > -1) {
    if (arr[startPtr] < arr[endPtr]) {
      newArr[newArrIdx] = arr[endPtr];
      endPtr = endPtr - 1;
    } else {
      newArr[newArrIdx] = arr[startPtr];
      startPtr = startPtr + 1;
    }
    newArrIdx = newArrIdx - 1;
  }
  return newArr;
}

int main() {
  // initalize an array of accending integers

  vector<int> arr{-10, -8, -7, -7, -6, -4, -3, -1, 0, 4, 5, 6, 7, 8, 12, 19};

  // vector<int> newArr = sort_squared_slow(arr);
  vector<int> newArrFast = sort_squared(arr);

  for (int i = 0; i < newArrFast.size(); i++) {
    printf("%d ", newArrFast[i]);
  }
  printf("\n");
  return 0;
}