# #3 Sorted Squared Array

###### tags:`Array` `Easy`

## Problem
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.
[#leetcode 977](https://leetcode.com/problems/squares-of-a-sorted-array/)

### Sample Input

array = [1, 2, 3, 5, 6, 8, 9]

### Sample Output

[1, 4, 9, 25, 36, 64, 81]

<br>

:::spoiler **Optimal Space & Time Complexity**

O(n) time | O(n) space - where n is the length of the input array

:::

<br>

<hr/>

## Solutions

### Official

### 1. Brute Force 暴力解法
1.Loop through the given array, and return the squared element.
2.Use sort() method to sort the transformed array in-place in ascending order.
#### O(nlogn) time | O(n) space - where n is the length of the input array

function sortedSquaredArray(array) {
    const sortedSquares = new Array(array.length).fill(0);
    for (let idx = 0; idx < array.length; idx++){
        const value = array[idx];
        sortedSquares[idx] = value * value;
    }
    sortedSquares.sort((a, b) => a-b );
  return sortedSquares;
}

<br>

### 2. Two-Pointers 雙指針法
One from the start and one from the end.
#### O(n) time | O(n) space - where n is the length of the input array

function sortedSquaredArray(array) {
    const sortedSquares = new Array(array.length).fill(0);
    let smallerValueIdx = 0;
    let largerValueIdx = array.length - 1;
    
for (let idx = array.length - 1 ; idx >= 0 ; idx--){
    const smallerValue = array[smallerValueIdx];
    const largerValue = array[largerValueIdx];
    
    if (Math.abs(smallerValue) > Math.abs(largerValue)){
        sortedSquares[idx] = smallerValue * smallerValue;
        smallerValueIdx++;
    }else{
        sortedSquares[idx] = largerValue * largerValue;
        largerValueIdx--;
    }
}
    
  return sortedSquares;
}

---

## Everyone's

### Brute Force
:::spoiler Raiy

var sortedSquares = function(nums) {
    
    function compareNumbers(a, b) {
        return a - b;
    }
    
    let powArr = nums.map(num=>Math.pow(num, 2))
    powArr.sort(compareNumbers)
    
    return powArr
};

:::

<br>

:::spoiler Becky 1&2

//Solution 1
function sortedSquaredArray(array) {
    let arr = array.map(function(n){
      return Math.pow(n, 2)
    })
    let arrSort = arr.sort((a,b) => {
      return a-b;
    })
  return arrSort;
};


//Solution 2
function sortedSquaredArray(array) {
  let n = array.length;
  let arr = new Array(n);
    for (let i=0; i< n; i++){
        arr[i] = array[i]*array[i];
    };

    let arrSort = arr.sort((a,b) => {
      return a-b;
    })
  return arrSort;
}

:::

<br>

:::spoiler Hao

function sortedSquaredArray(array) {
  /**
   * O(nlogn) time | O(n) space
   */
  return array.map((value) => Math.pow(value, 2)).sort((a, b) => a - b);
}

:::

<br>

:::spoiler SOL

var sortedSquares = function (array) {
  return array.map((num) => num * num).sort((a, b) => a - b);
};

:::

<br>

### Two-Pointers

:::spoiler 月

// O(n) time | O(n) space
var sortedSquares = function(nums) {
    let leftIndex = 0;
    let rightIndex = nums.length-1;
    const resultArr = [];
    while(leftIndex <= rightIndex){
        if(nums[leftIndex]*nums[leftIndex] >= nums[rightIndex]*nums[rightIndex] ){
            resultArr.unshift(nums[leftIndex]*nums[leftIndex]);
            leftIndex++;
        }else{
            resultArr.unshift(nums[rightIndex]*nums[rightIndex]);
            rightIndex--;
        }
    }
    return resultArr
};

:::

<br>

:::spoiler Becky 3

//Solution 3
function sortedSquaredArray(array) {
    let n = nums.length;
    let left = 0;
    let right = n-1;
    let flag = n-1;
    let arr = new Array(n);
while( right >= left ){
    let left_square = nums[left]*nums[left];
    let right_square = nums[right]*nums[right];
    if(left_square > right_square){
        left++;
        arr[flag] = left_square;
    }else{
        right--;
         arr[flag] = right_square;
    }
    flag--
}
return arr;
};

:::

<br>

:::spoiler 東

function sortedSquaredArray(array) {
    
    // Time O(n) | Space O(n) where n is the length of array

  // find the first positive integer index
  let firstPositiveNumIdx = -1;
  for (let i = 0; i < array.length; i++) {
    if (array[i] > 0) {
      firstPositiveNumIdx = i;
      break;
    }
  }
  
  // make a array sorted with absolute value
  let sortedAbsValArr = [];
  
  if (firstPositiveNumIdx === 0) {
    sortedAbsValArr = [...array]
  } else if (firstPositiveNumIdx === -1) {
      sortedAbsValArr = array.reverse();
  } else {
    let left = firstPositiveNumIdx - 1;
    let right = firstPositiveNumIdx;
    while (left >= 0 && right < array.length) {
      if (array[left] * (-1) < array[right]){
        sortedAbsValArr.push(array[left]*(-1))
        left --;
      } else {
        sortedAbsValArr.push(array[right])
        right ++;
      }
    }
  
    if (left === -1) {
      for(let i = right; i < array.length; i++){
        sortedAbsValArr.push(array[i])
      }
    } else if (right === array.length ){
      for(let i = left; i >=0; i--){
        sortedAbsValArr.push(array[i]*(-1))
      }
    }
  }

  // square array sorted with absolute value
  return sortedAbsValArr.map((num) => num*num);  
}

:::

<br>

:::spoiler YC

/*time：O(n) 
space：O(n)*/
    const len = nums.length;
    let left = 0, right = len - 1;
    const res = [];
    for (let i = 0; i < len; i++) {
        if (Math.abs(nums[left]) > Math.abs(nums[right])) {
            res.unshift(nums[left] * nums[left]);
            left++;
        } else {
            res.unshift(nums[right] * nums[right]);
            right--;
        }
    }
    return res;

:::

<br>

---

## Supplement / Discussion
### Two Pointer 雙指針法

設置兩個指針以解決演算法問題。一般較常用於解決Array（陣列/數組）、Linked list（鏈結串列/鏈表）類的問題。可以有效的將時間複雜度降低。
分為 **左右指針** 以及 **快慢指針**。

### 左右指針
通常需要一個有序的陣列，左右兩個指針就是一個在開頭，一個在結尾。

<br>

範例：(本題)[977. Squares of a Sorted Array](https://leetcode.com/problems/squares-of-a-sorted-array/)

<br>

### 快慢指針
設置一快一慢兩個指針fast和slow，指向陣列或鏈表的開頭。

<br>

範例：[27. Remove Element](https://leetcode.com/problems/remove-element/)
#### Remove Element
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

給你一個陣列 nums 和一個值 val，你需要原地移除所有數值等於 val 的元素，並返回移除後陣列的新長度。
不要使用額外的陣列空間，你必須僅使用 O(1) 的空間複雜度。
元素的順序可以改變。你不需要考慮陣列中超出新長度後面的元素。
#### Example:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]

#### Solution:

var removeElement = (nums, val) => {
    let k = 0;
    for(let i = 0;i < nums.length;i++){
        if(nums[i] != val){
            nums[k++] = nums[i]
        }
    }
    return k;
};