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:

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

Clarifying Questions

1. Q: Can the input array contain negative numbers?
   • A: Yes, the input array can include negative numbers.
2. Q: Can the input array have duplicate elements?
   • A: Yes, the input array can have duplicate numbers.
3. Q: What is the maximum length of the input array?
   • A: The problem constraints typically ensure that the length of the input array is manageable (e.g., (1 \leq \text{nums.length} \leq 10^4)).

Strategy

1. Use Two Pointers Technique:
   • Since the original array is sorted, but we need the squares in non-decreasing order, we can leverage the property that the square of a negative number can fit somewhere in between positive numbers.
   • Use two pointers:
     • Left pointer initialized to the start of the array.
     • Right pointer initialized to the end of the array.
   • Compare the absolute values at both pointers.
     • If the absolute value at the left pointer is larger, square it and place it in the current highest available position from the output array (initially starting from the end).
     • Move the left pointer rightwards.
     • Otherwise, square the value at the right pointer and place it in the highest available position.
     • Move the right pointer leftwards.
   • Continue this process until the entire array is processed.

Code

#include <vector>
#include <algorithm>

std::vector<int> sortedSquares(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> result(n);
    
    int left = 0;
    int right = n - 1;
    int position = n - 1;
    
    while (left <= right) {
        if (abs(nums[left]) > abs(nums[right])) {
            result[position] = nums[left] * nums[left];
            left++;
        } else {
            result[position] = nums[right] * nums[right];
            right--;
        }
        position--;
    }
    
    return result;
}

Time Complexity

• The time complexity of this solution is O(n), where n is the length of the input array. This is because we are processing each element of the array exactly once.

• The space complexity is also O(n), where n is the size of the input array, as we are utilizing an additional array of the same size to store the result.

By using the two pointers technique, we are able to achieve a solution that processes the array in linear time while avoiding the need to sort the resultant array separately.

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?