977. Squares of a Sorted Array

 一刷 06/2022

Version #2 Two Pointers from start and end - better[TODO]

Version #1 Two Pointers from the middle - not optimal

看了答案发现不需要先找到分界点，可以直接从最大square往最小的fill out，就是从array两端走向中间

Time O(N)

Space O(1)

Runtime: 2 ms, faster than 82.17% of Java online submissions for Squares of a Sorted Array.

Memory Usage: 55.3 MB, less than 70.05% of Java online submissions for Squares of a Sorted Array.

class Solution {

    public int[] sortedSquares(int[] nums) {

        int[] result = new int[nums.length];

        // Find the 1st index > 0

        int right = firstPositive(nums);

        int left = right - 1;

        int index = 0;

        while (right < nums.length && left >= 0) {

            if (nums[left] * nums[left] <= nums[right] * nums[right]) {

                result[index++] = nums[left] * nums[left];

                left--;

            } else {

                result[index++] = nums[right] * nums[right];

                right++;

            }

        }

        while (right < nums.length) {

            result[index++] = nums[right] * nums[right];

            right++;

        }

        while (left >= 0) {

            result[index++] = nums[left] * nums[left];

            left--;

        }

        return result;

    }

    private int firstPositive(int[] nums) {

        int start = 0, end = nums.length - 1;

        while (start < end) {

            int mid = start + (end - start) / 2;

            if (nums[mid] <= 0) {

                start = mid + 1;

            } else {

                end = mid;

            }

        }

        return nums[start] > 0 ? start : nums.length;

    }

}