Squares of a Sorted Array

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given a sorted array - return their squares also in a sorted state
• Try to solve with $O(n)$ time and space complexity

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Given sorted array

Approach Taken

(Step-by-step logic or pseudocode before coding.)

• Use Two Pointers from both ends and put the bigger squared number at the end of result

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Two Pointers#1. Opposite Direction Pointers (Start–End)
• Array

Time & Space Complexity

• Time: O($N$) → Reason: Iterating through the array once
• Space: O($N$) → Reason: Just storing the results

Code

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        l, r = 0, len(nums) - 1
        result = []
        while l <= r:
            l_square = nums[l] ** 2
            r_square = nums[r] ** 2
            if l_square >= r_square:
                result.append(l_square)
                l += 1
            else:
                result.append(r_square)
                r -= 1
        result.reverse()
        return result

Common Mistakes / Things I Got Stuck On

• while l <= r: - I did l < r but here we NEED <= because we want the two pointers to meet