Day 2 - Two pointers O(n)

Question: 977. 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-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?

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]

First attempt: using bubble sort

• My initial thought was 'do I have to sort this before or after squaring each number? which sort method would be efficient?'
• To make it less than O(N2), it seemed like I have use heap sort. But heap sort still is not O(N), which follow-up question prefers. It is O(n*logn).
• For here, though I knew that bubble sort is O(N2), I just wanted to practice bubble sort, which is one of the simple sorts we usually first learn.

Second attempt: using two pointers and aim O(N)

• It seemed like I can take an advantage of non-decreasing order.
• I tried to think of ways, asking how to move a negative number or its squared value to the correct position?
• It seemed like I had to compare the value of square(positive num) vs. square(negative num)
• I also referred to this post at the end to refine my solution.
• In this solution, it adds bigger squared(value) to a beginning of result array. And then reverse the result array at the end to make it *non-decreasing order.
• In my solution, I started adding squared(value) from the end of result array. And then make it to its index 0.
• Here, I first thought I can use upper_index as and index for adding new item to result array. But two different conditional cases returned different outcomes. So I created last_index variable to be clear and working for both cases.

Psuedo code

var sortedSquares = function(nums) {
    // 2. O(n) with two pointers
    // #1. if all nums are positive, just return simple squared result.

    // #2. if there's negative nums, we need two pointers leftmost, rightmost
    // similar to binary search two pointers.
    // compare two pointers' squared values
    // and add bigger number to the end of the list, aka at upper_bound index.
    let lower_bound = 0;
    let upper_bound = nums.length - 1;
    let reordered_arr = [];
    while(lower_bound <= upper_bound) {
        // if lower val is bigger than upper val
        // add lower(bigger) val to upper index of new arr
        // move lower index + 1

        // if upper val is bigger than lower val
        // add upper(bigger) val to upper index of new arr
        // move upper index - 1

    }
    return reordered_arr;

};

Final code

var sortedSquares = function(nums) {
    // 2. O(n) with two pointers
    // #1. if all nums are positive, just return simple squared result.
    let has_negative = false;
    for(let i = 0; i < nums.length; i++) {
       if(nums[i] < 0) {
           has_negative = true;
           break;
       }
    }
    if(!has_negative) {
        let squared_arr = [];
        for(let i = 0; i < nums.length; i++) {
            squared_arr.push(nums[i]*nums[i]);
        }
        return squared_arr;
    }
    // #2. if there's negative nums, we need two pointers leftmost, rightmost
    let lower_bound = 0;
    let upper_bound = nums.length - 1;
    let reordered_arr = [];
    let last_index = upper_bound;
    while(lower_bound <= upper_bound) {
        if(nums[lower_bound]*nums[lower_bound] >= nums[upper_bound]*nums[upper_bound]) {
            reordered_arr[last_index] = nums[lower_bound]*nums[lower_bound];
            lower_bound += 1;
        } else if(nums[upper_bound]*nums[upper_bound] > nums[lower_bound]*nums[lower_bound]) {
            reordered_arr[last_index] = nums[upper_bound]*nums[upper_bound];
            upper_bound -= 1;
        }
        last_index -= 1;
        // i initially put the squared num to [upper_bound] index, but it messes the insertion.
        // using last_index is more clear
    }
    return reordered_arr;
};

Similar algorithm problems

• 88. Merge Sorted Array
• 360. Sort Transformed Array