The Leetcode problem: "Given an integer array 'nums' sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order."
First of all, why "non-decreasing"? Would it not be just as accurate - and less confusing - to just call it "ascending"? Is there something about "ascending" that I don't know?
So, my thinking - not anywhere near what Big-O would dictate - would be to do the obvious ... "return an array of squares of each number (element) sorted ... ascending" (there, I said it!)
So let's do that:
var sortedSquares = function(nums) {
return nums.map(x => x*x).sort((a,b) => a-b)
};
Here, I am mapping each element of the 'nums' array and returning an array of it's squares. Then I am sorting the output array numerically. Note: if you don't sort numerically, using the ((a,b) => a-b) sort parameters, you will sort "ascending, built upon converting the elements into strings, then comparing their sequences of UTF-16 code units values". Ah... there it is. The difference between "ascending" and "non-decreasing".
I thought this one-line solution was pretty slick and daisy-chaining prototype functions in the higher level of caliber. And ... it did give the proper result. But Leetcode is a little more picky than that. And it's great to aspire to the Leetcode level of achievement. It will get your further than making excuses like "who cares if the space and time complexities are above linear?" So, when Leetcode gives you feedback like ...
Squaring each element and sorting the new array is very trivial,
could you find an O(n) solution using a different approach?
...you feel about 10 feet less tall. But there are clues in their subversive backhanded compliment. "Can you find an O(n) solution". They want you to travel through the array no more than once. So let's see what we can come up with.
First, let's set up a loop to go through the array. But let's not loop through the whole ... wait a minute ...
I checked and re-submitted it later and got this result:
Runtime: 104 ms, faster than 96.77% of JavaScript online
submissions for Squares of a Sorted Array.
Memory Usage: 45.4 MB, less than 79.37% of JavaScript online
submissions for Squares of a Sorted Array.
So I guess my solution was good enough after all.
The lessons this week are
(1) to check your Leetcode submissions at all different times of the day. Check back later and you may get a better score than you did at first.
(2) there really is a difference between "ascending" and "non-decreasing" ... although "ascending" really could be corrected with just adding "numerically" ... which would still read easier. :)
Top comments (0)