Squares of a Sorted Array

---

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreaing order.

• Example 1:
  

	Input: nums = [-4, -1, 0, 3, 10]
	Output: [0, 1, 9, 16, 100]
	Explanation: After squaring, the array becomes [16, 1, 0, 9, 100].
	After sorting, it becoms [0, 1, 9, 16, 100].

• Example 2:

	Input: nums = [-7, -3, 2, 3, 11]
    Output: [4, 9, 9, 49, 121]

• Constraints:

	1 <= nums.length <= 104
	-104 <= nums[i] <= 104
	nums is sorted in non-decreasing order.

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

Answer

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        
        int left = 0;
        int right = nums.length -1;
        int index = nums.length -1;
        
        while (left <= right) {
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];
            
            if (leftSquare > rightSquare) {
                result[index] = leftSquare;
                left++;
            } else {
                result[index] = rightSquare;
                right--;
            }
            
            index--;
        }
        
        return result;
    }
}

---

1. The variables left, right, and index are pointer variables used to traverse the array and fill the new result array.

   위 코드에서 사용된 left, right, index는 배열을 순회하고 새로운 배열을 채우는데 사용되는 포인터 변수입니다.

2. Initially, left and right point to the beginning and end of the array, respectively, and index is initialized to the last index of the result array.

   처음에 left와 right는 각각 배열의 시작과 끝을 가리키고, index는 결과 배열의 마지막 인덱스를 가리키도록 초기화됩니다.

3. Then, the algorithm enters the while loop and continues until left and right pointers meet.

   그리고 while 루프에서 left와 right가 서로 만나기 전까지 반복합니다.

4. In each iteration of the loop, the algorithm compares the squares of numbers pointed by left and right, and stores the larger square value in the result array. After storing the value, the corresponding pointer is moved accordingly.

   각 루프 반복에서 left와 right 포인터가 가리키는 숫자들의 제곱 값을 비교하고, 더 큰 값을 결과 배열 result에 저장합니다. 저장한 후에 해당 포인터를 이동시킵니다.

5. By using this approach, the algorithm calculates the squares of numbers in an already sorted array and stores them in the new array efficiently with an O(n) time complexity.

   이 방법을 사용하면 이미 정렬된 배열에서 제곱 값만 계산하여 새로운 배열에 저장하므로, 간단하면서도 효율적인 O(n) 시간 복잡도로 문제를 해결할 수 있습니다.

---

더 쉽게 그림을 그려가면서 이해를 해보자!

1. nums에 [-4,-3,-2,1,3,5] 라는 값이 들어있다고 가정을 해보자. left, right, index를 각각 초기화해주고 (right, index는 nums.lengh-1 이라서 5(6-1)가 들어간다!)

2. while문으로 left와 right가 만날 때까지 반복을 해줄건데 leftSquare는 nums[left] * nums[left]; 인데 a번째에선 nums 배열의 '0번째 요소 x 0번째 요소' 라는 뜻이다. right도 마찬가지

3. if문으로 들어가서 a번째 연산을 진행해보자. leftSquare는 배열의 0번째 요소인 (-4) x (-4)를 해서 16이고 rightSquare은 5번째 요소인 5x5를 해서 25다. 이 경우엔 leftSquare < rightSquare라서 else로 넘어간다. rightSquare에 있는 값을 result[index]에 넣어주면 result=[0,0,0,0,0,25] 가 들어간 상태이며 right의 포인터는 한칸 왼쪽으로 이동한다. (다음 루트부터는 5번째 요소가 아니라 4번째 요소를 비교한다)! 그리고 index도 하나 감소를 한다.

4. 이 과정을 b,c ... n번째 반복을 하면 result에 [1,4,9,9,16,25] 라는 값이 채워진다! 이렇게해서 바로 문제에서 원했던 입력 배열의 각 원소를 제곱하여 비내림차순으로 정렬된 값 을 완성할 수 있다!!!