Leetcode-977-Squares of a Sorted Array

Squares of a Sorted Array

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

Description:

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

Idea:

solution1: Brute Force

traverse the nums and square each element, than sort the nums

Code:

class Solution {
    public int[] sortedSquares(int[] nums) {
//      get square of each element
        for(int i=0; i<nums.length; i++){
            nums[i] = nums[i]*nums[i];
        }
//      sort array
        Arrays.sort(nums);
        return nums;
        
    }
}

solution 2: two pointers

Step1: create new array to store the sorted square value

Step2: set two pointer(one for start, one for end), because only square of negative may larger than last positive one and one index for new array, and store it from the end to keep the sort of the array.

Step3: if the square of start larger than the square of the end one, then store teh bigger one to the new array. at the same time, just increase the first index to compare the next element with the element that the second pointer pointed. Otherwise, do the opposite operations.

Code:

class Solution {
    public int[] sortedSquares(int[] nums) {
//      create new array to store the sorted square value
        int[] result = new int[nums.length];
//      set two pointer(one for start, one for end), because only square of negative may larger than last positive one
//      and one index for new array, and store it from the end to keep the sort of the array
        int first = 0;
        int second  = nums.length-1;
        int index = result.length-1;
        while(first <= second){
//          if the square of start larger than the square of the end one, then store teh bigger one to the new array. at the same time, just increase the first index to compare the next element with the element that the second pointer pointed
            if(nums[first]*nums[first] > nums[second]*nums[second]){
                result[index--] = nums[first]*nums[first];
                first++;
            }
//          the opposite situation
            else{
                result[index--] = nums[second]*nums[second];
                second--;
            }
        }
        return result;
    }
}