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 theresult arrayat 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_indexas and index for adding new item toresult array. But two different conditional cases returned different outcomes. So I createdlast_indexvariable 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
Top comments (0)