977. Squares of a Sorted Array

leetcode.com/problems/squares-of-a-sorted-array/

3번으로 해야함.

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing 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 becomes [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.

Video Solution

Solution

Approach 1: Sort

Intuition and Algorithm

Create an array of the squares of each element, and sort them.

class Solution {
    public int[] sortedSquares(int[] A) {
        int N = A.length;
        int[] ans = new int[N];
        for (int i = 0; i < N; ++i)
            ans[i] = A[i] * A[i];

        Arrays.sort(ans);
        return ans;
    }
}

Complexity Analysis

Time Complexity: O(N \log N), where N is the length of A.
Space Complexity: O(N).

Approach 2: Two Pointer

Intuition

Since the array A is sorted, loosely speaking it has some negative elements with squares in decreasing order, then some non-negative elements with squares in increasing order.

For example, with [-3, -2, -1, 4, 5, 6], we have the negative part [-3, -2, -1] with squares [9, 4, 1], and the positive part [4, 5, 6] with squares [16, 25, 36]. Our strategy is to iterate over the negative part in reverse, and the positive part in the forward direction.

Algorithm

We can use two pointers to read the positive and negative parts of the array - one pointer j in the positive direction, and another i in the negative direction.

Now that we are reading two increasing arrays (the squares of the elements), we can merge these arrays together using a two-pointer technique.

class Solution {
    public int[] sortedSquares(int[] A) {
        int N = A.length;
        int j = 0;
        while (j < N && A[j] < 0)
            j++;
        int i = j-1;

        int[] ans = new int[N];
        int t = 0;

        while (i >= 0 && j < N) {
            if (A[i] * A[i] < A[j] * A[j]) {
                ans[t++] = A[i] * A[i];
                i--;
            } else {
                ans[t++] = A[j] * A[j];
                j++;
            }
        }

        while (i >= 0) {
            ans[t++] = A[i] * A[i];
            i--;
        }
        while (j < N) {
            ans[t++] = A[j] * A[j];
            j++;
        }

        return ans;
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the length of A.
Space Complexity: O(N) if you take output into account and O(1) otherwise.

이건 약간 옛날문제인지, 솔루션이 잘 업데이트 되있지 않다는 생각이 일단 들고, 아래의 양쪽에서 들어오는 투포인터가 제일 좋아보임.

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        
        int i = 0;
        int j = n-1;
        int[] ans = new int[n];
        int k = n-1;
        while(i <= j) {
            int sqrtI = nums[i] * nums[i];
            int sqrtJ = nums[j] * nums[j];
            
            if(sqrtI < sqrtJ) {
                ans[k--] = sqrtJ;
                j--;
            } else {
                ans[k--] = sqrtI;
                i++;
            }
        }
        return ans;
    }
}