Posted on Apr 8, 2023

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; };