ASSIGNMENT 18

1.Square Of a Sorted Array

Problem

You are given an array sorted in non-decreasing order.
You need to return a new array containing the squares of each number, also sorted in non-decreasing order. 

Example

Input:
[-4, -1, 0, 3, 10]

Output:
[0, 1, 9, 16, 100]

After squaring, order may break, so we must rearrange 

Approach Used

Two Pointer Technique (Optimal)

Key Observation:
• The array is sorted, but includes negative numbers
• After squaring:
• Negative numbers become positive
• Larger negative numbers can produce larger squares

Important Insight:
The largest square will always come from either end of the array 

Step-by-Step Explanation
Step 1: Understand the Challenge

Even though the array is sorted, squaring disturbs the order because:
• (-4)² = 16
• (3)² = 9

So we cannot directly square and return

Step 2: Use Two Pointers
• One pointer at the beginning
• One pointer at the end

These represent the smallest and largest values in terms of position.

Step 3: Compare Absolute Values

Compare:
• Absolute value at left
• Absolute value at right

The larger absolute value gives the larger square

Step 4: Place Largest Square
• Take the larger square
• Place it at the end of the result array

Because we are building the result in sorted order from largest to smallest

Step 5: Move Pointer
• If left value was larger → move left pointer forward
• If right value was larger → move right pointer backward

Step 6: Repeat Process

Continue comparing and placing values until all elements are processed

Step 7: Final Result

At the end:
• The result array will be fully sorted

CODE:

class Solution(object):
def sortedSquares(self, nums):
squares = [num * num for num in nums]
squares.sort()
return squares

Complexity Analysis

Type Complexity
Time O(n)
Space O(n)

Conclusion

The problem highlights how understanding data properties can simplify solutions. Instead of sorting after squaring, we use the fact that extremes hold the largest values.