Leetcode – Squares of a Sorted Array Solution in Python

Spread the love

One of the common array-based problems on Leetcode is the “Squares of a Sorted Array” problem. In this article, we’ll break down the problem, discuss potential solutions, and implement them in Python.

Table of Contents

  1. Problem Statement
  2. Brute Force Solution
  3. Optimal Two-Pointer Solution
  4. Analyzing Time and Space Complexity
  5. Conclusion

1. Problem Statement

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example:

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].

2. Brute Force Solution

The simplest approach is to square each element and then sort the resultant array.

Python Implementation:

def sortedSquares(nums):
    return sorted([x*x for x in nums])

While this solution works, it is not the most efficient.

3. Optimal Two-Pointer Solution

Since the input array is already sorted, we can utilize a two-pointer technique to optimize our solution.

  1. Place one pointer at the beginning of the array and another at the end.
  2. Compare the absolute values of the elements at both pointers.
  3. The larger absolute value gets squared and placed at the current position of the output array.
  4. Repeat the process until the two pointers meet.

Python Implementation:

def sortedSquares(nums):
    n = len(nums)
    # Create an output array of the same length as nums initialized with zeros
    result = [0] * n
    # Initialize two pointers: left at the start and right at the end
    left, right = 0, n-1
    # Position to place the square in the result array
    pos = n-1

    while left <= right:
        left_square = nums[left] ** 2
        right_square = nums[right] ** 2
        
        # Compare the squares and place the larger one in the correct position
        if left_square > right_square:
            result[pos] = left_square
            left += 1
        else:
            result[pos] = right_square
            right -= 1
        
        pos -= 1

    return result

4. Analyzing Time and Space Complexity

  • Brute Force Solution:
    • Time Complexity: O(nlog⁡n) due to the sorting.
    • Space Complexity: O(n) as we create a new array to store squared numbers.
  • Two-Pointer Solution:
    • Time Complexity: O(n) as each element is processed once.
    • Space Complexity: O(n) for the resultant array.

The two-pointer solution is clearly more efficient in terms of time complexity.

5. Conclusion

Leetcode problems like “Squares of a Sorted Array” offer an excellent opportunity for programmers to hone their problem-solving skills and deepen their understanding of algorithmic techniques. By exploring both brute force and optimized solutions, we gain a better appreciation for algorithmic efficiency and the power of effective problem-solving strategies like the two-pointer technique.

Leave a Reply