algoadvance

Leetcode 977. Squares of a Sorted Array

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 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Clarifying Questions

1. Q: Can the input array contain duplicate numbers? A: Yes, the input array can contain duplicates.

2. Q: What is the range of the input array size? A: The problem doesn’t specify ranges, but typically LeetCode problems should handle sizes up to tens of thousands efficiently.

3. Q: Can we use extra space for memory? A: Yes, there is no constraint against using extra space.

4. Q: Should the algorithm handle negative numbers? A: Definitely, the example contains negative numbers.

Strategy

Given the input array nums sorted in non-decreasing order:

1. We need to create an array of the squares of the numbers in nums.
2. Since squaring each number would change the relative order due to the absolute values, we must sort the squared values.

We can utilize a two-pointer approach since we know that the largest squares might be found:

• At the beginning of the array (most negative values).
• At the end of the array (largest positive values or least negative values).

Two-pointer Approach Steps:

1. Initialize two pointers, left at the start of the array and right at the end of the array.
2. Create a result array with the same length as nums.
3. Iterate from the end of the result array to the beginning:
   • Compare the absolute values of the elements at left and right.
   • Place the square of the larger absolute value at the current position in the result array.
   • Move the corresponding pointer (left or right) inward.
4. Continue until the result array is fully populated.

This strategy ensures we fill the result array from the largest to the smallest value, essentially performing an efficient sort.

Time Complexity

• Time Complexity: O(n) where n is the number of elements in nums, since we make a single pass through nums.
• Space Complexity: O(n) for the result array.

Code

public class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int left = 0, right = n - 1;
        int pos = n - 1;

        while (left <= right) {
            int leftVal = nums[left] * nums[left];
            int rightVal = nums[right] * nums[right];

            if (leftVal > rightVal) {
                result[pos] = leftVal;
                left++;
            } else {
                result[pos] = rightVal;
                right--;
            }
            pos--;
        }

        return result;
    }
}

This implementation maintains optimal efficiency in terms of both time and space, ensuring that the problem constraints and requirements are effectively met.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?