Squares Of A Sorted Array Leetcode Problem 977 [Python Solution]

Squares Of A Sorted Array, although this problem is categorized as “Easy,” it comes with a bit of a twist that makes it quite engaging.

We’ll walk you through the problem statement, the constraints, the reasoning behind our approach, and provide you with both a brute-force and an efficient Python solution.

You can find the original problem on LeetCode here: Squares of a Sorted Array.

Let’s dive in and explore this intriguing coding challenge!

Problem Overview

Question: Given an integer array nums sorted in non-decreasing order, your task is to return an array of the squares of each number, sorted in non-decreasing order.

In simpler terms, we are provided with an array of integers, and we need to return a new array containing the squares of these numbers, arranged in ascending order.

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]

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums is sorted in non-decreasing order.

Now that we have a clear understanding of the problem, let’s explore the constraints in more detail.

Understanding the Constraints

The constraints provided in the problem statement are essential to consider when designing our solution.

Let’s break them down:

1. The length of the input array nums is between 1 and 104. This means we may have relatively small or large arrays to process.
2. The values in the array nums can range from -104 to 104. These values can be both positive and negative, and they are sorted in non-decreasing order.

The presence of negative values introduces complexity because squaring them can lead to rearranging the elements.

Given these constraints, we need to devise a solution that can efficiently handle various input scenarios.

Squares of a Sorted Array LeetCode Problem Solution

1. Bruteforce Approach

Let’s start by examining a straightforward approach to solving this problem.

We will iterate through the input array nums, square each number, and store the squared values in a new array.

Then, we will sort the new array in non-decreasing order.

def sortedSquares(nums):
    # Initialize an empty array to store squared values
    squared_nums = []
    
    # Iterate through the input array
    for num in nums:
        # Square the number and append it to the squared_nums array
        squared_nums.append(num * num)
    
    # Sort the squared_nums array in non-decreasing order
    squared_nums.sort()
    
    return squared_nums

This approach is relatively straightforward.

We iterate through the nums array once, square each element, and then sort the resulting array.

While this solution is correct, it has a time complexity of O(n log n) due to the sorting operation, where n is the length of the input array.

2. An Efficient Approach with Two-Pointers

Now, let’s explore a more efficient approach that leverages the sorted property of the input array.

The idea is to use a two-pointer approach to construct the sorted squared array in a single pass through the input array.

def sortedSquares(nums):
    # Initialize an array to store the result
    n = len(nums)
    result = [0] * n
    
    # Initialize pointers for the left and right ends of the input array
    left, right = 0, n - 1
    
    # Iterate from right to left, filling the result array with squared values
    while left <= right:
        # Get the absolute values of the elements at the left and right pointers
        left_value = abs(nums[left])
        right_value = abs(nums[right])
        
        # Compare the squared values and fill the result array accordingly
        if left_value > right_value:
            result[right - left] = left_value * left_value
            left += 1
        else:
            result[right - left] = right_value * right_value
            right -= 1
    
    return result

This efficient approach takes advantage of the two-pointer technique.

It starts by initializing two pointers, left at the beginning of the array and right at the end of the array.

We iterate from right to left, comparing the squared values of the elements pointed to by left and right.

The smaller squared value is placed in the result array, and the respective pointer is moved towards the center.

This process continues until the pointers meet, ensuring that we construct the squared array in the required non-decreasing order.

This approach has a time complexity of O(n), as it processes the input array in a single pass.

It is the most efficient way to solve the problem, given the constraints.

Python Code Solution

Now, let’s provide you with the Python code for the efficient approach.

You can use this code to solve the Squares Of A Sorted Array problem.

def sortedSquares(self, nums: List[int]) -> List[int]:
        # Initialize an array to store the result
        n = len(nums)
        result = [0] * n

        # Initialize pointers for the left and right ends of the input array
        left, right = 0, n - 1

        # Iterate from right to left, filling the result array with squared values
        while left <= right:
            # Get the absolute values of the elements at the left and right pointers
            left_value = abs(nums[left])
            right_value = abs(nums[right])

            # Compare the squared values and fill the result array accordingly
            if left_value > right_value:
                result[right - left] = left_value * left_value
                left += 1
            else:
                result[right - left] = right_value * right_value
                right -= 1

        return result

You can use this code to solve the problem, and it should work efficiently for various inputs.

Time and Space Complexity

Let’s briefly discuss the time and space complexity of our efficient solution.

• Time Complexity: The time complexity of our efficient approach is O(n), where n is the length of the input array nums.

This is because we iterate through the array once, comparing and squaring values in a single pass.

• Space Complexity: The space complexity is O(n) as well.

We create an additional array, result, to store the squared values, which has the same length as the input array.

Reasoning Behind Our Approach

Our approach leverages the sorted property of the input array, making it

possible to construct the sorted squared array in a single pass.

By using a two-pointer technique, we efficiently compare and square the elements, ensuring the output is arranged in non-decreasing order.

The core idea is to determine which squared value should be placed in the result array by comparing the absolute values of elements pointed to by the left and right pointers.

We construct the result array in reverse order, starting with the largest squared value and working our way to the smallest.

This approach optimizes both time and space complexity.

Related Interview Questions By Company:

• Word Pattern LeetCode
• Shift 2D Grid LeetCode
• Length Of Last Word LeetCode

Related Interview Questions By Difficulty:

• Search Insert Position LeetCode
• Find First And Last Position Of Element In Sorted Array LeetCode
• Guess Number Higher Or Lower LeetCode

Related Interview Questions By Category:

• Merge Two Binary Trees LeetCode
• Palindrome Number LeetCode
• Ugly Number LeetCode

Conclusion

In this blog post, we explored the Squares Of A Sorted Array LeetCode problem (Problem 977) and provided two Python solutions: a brute-force approach and an efficient approach using a two-pointer technique.

The efficient approach, with a time complexity of O(n), is the recommended solution for this problem, as it takes full advantage of the sorted input array.

We hope this post has been informative and helpful for your coding journey.

If you have any questions, suggestions, or comments, please feel free to share them.

You can also try solving the problem on LeetCode and see how your solution compares.

Happy coding!

Remember to like, engage, and share if you found this content useful, and encourage discussions and questions in the comments section to foster a learning community.

Happy coding, and stay curious!