Given a sorted list of integers, square the elements and give the output in sorted order.
For example, given [-9, -2, 0, 2, 3], return [0, 4, 4, 9, 81].
Step 1: Simple Solution
This is a straightforward problem so we don’t have to spend too long breaking down the nuance of the solution.
A brute force method would be to simply square and sort the list, like so: sorted([x ** 2 for x in lst]). This would result in O(n log n) time.
Step 2: Optimizing
How can we begin optimizing this problem? One way to do so would be looking at the hints the question gives us, and implementing that into our solution. Our brute force solution is lacking because it doesn’t take advantage of the fact that our input list is sorted.
Working through examples by hand we notice a few things. The squares of the positive numbers, if sorted, would still remain sorted. The squares of the negative numbers, if sorted, would be reverse sorted. For example 3^2> 2^2 but -9^2>-3^2.
We can quickly notice that the value of the square depends on the absolute value of the number. Since the largest absolute value will be at the ends, we can start from there. Since we are comparing pairs in a sorted list, the Two Pointer Technique might come in handy.
We could do something like this:
At any given point, the largest absolute value will be found at either end. Therefore the largest square will be found on either end.
Compare the two values at the end, pick the bigger (absolute value). Add the square of that to our result, and move the corresponding pointer.
This will create a reverse sorted list. We want to reverse the list and return it.
The code will look like this:
def get_square(a):
if a is None:
return []
result = []
left, right = 0, len(a) - 1
while left <= right:
if abs(a[left]) > abs(a[right]):
square_ele = abs(a[left] * a[left])
result.append(square_ele)
left += 1
else:
square_ele = abs(a[right] * a[right])
result.append(square_ele)
right -=1
result.reverse()
return result
So far our time complexities look like this:
Time: O(n) (we loop through the list once, and we reverse it. Both linear time operations)
Space: O(n) (we have a list the same length as the original).
There are however some repeated instructions here. Since this is an easy problem, we want to be very careful and maximize every little thing. A better approach would be inserting the values at the start of the array. This way we can skip the reversing. To be extra efficient, we can also have a single insert, outside the conditional.
The code becomes:
def get_square(a):
if a is None:
return []
result = []
left, right = 0, len(a) - 1
while left <= right:
square_ele=0
if abs(a[left]) > abs(a[right]):
square_ele = abs(a[left] * a[left])
left += 1
else:
square_ele = abs(a[right] * a[right])
right -=1
result.insert(0,square_ele)
return result
Step 3: Testing
To prove your code works you will have to dry run some tests. Whenever you use pointers to indexes in an array, I recommend always testing with an array containing an odd number of elements and an array with an even number of elements. With your edge cases, and testing the examples given, that is generally sufficient. Make sure your examples have a mix of positive numbers, negative numbers, zeroes, and repeating numbers. This way you cover every case.
Closing +Note about the Difficulty Level
Being an easy question, the solution shouldn’t take you more than 20 minutes to create. Easy questions are good for familiarizing yourself with concepts and practicing a good volume of questions relatively quickly and learn from your mistakes. Unless you’re at an advanced level, you shouldn’t overlook them.
Bonuses/Promotion (Get Free Stuff)
To share interesting problems/solutions with me, reach out to me. Different social media of mine also have other content from me. Good problems and/or solutions receive a free shoutout + 2 months of the paid newsletter:
JavaTpoint offers free online tutorials for learning programming languages, including Java. It provides a structured learning path with topics ranging from basic concepts like variables and control statements to advanced subjects such as multi-threading, JDBC, and Java tutorial Collections. The site includes interactive code examples, allowing users to practice coding and understand how different concepts work in real-time. In addition to Java, JavaTpoint covers other languages like Python, C++, JavaScript, and more, along with web development and database topics.
JavaTpoint offers free online tutorials for learning programming languages, including Java. It provides a structured learning path with topics ranging from basic concepts like variables and control statements to advanced subjects such as multi-threading, JDBC, and Java tutorial Collections. The site includes interactive code examples, allowing users to practice coding and understand how different concepts work in real-time. In addition to Java, JavaTpoint covers other languages like Python, C++, JavaScript, and more, along with web development and database topics.