Leetcode 977. Squares of a Sorted Array

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

Example 1:

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

Brute Force Approach:

The brute force approach loop through the array to square each element of the array and then sorting the resulting array.

function sortedSquares (nums) { 
     return nums.map(i => i * i).sort((a, b) => a - b);
}

Time complexity analysis, this apporach is O(n * log(n))

1. map() method:

   • Time Complexity: O(n)

   • Explanation: The map() method iterates over each element of the array once and applies a callback function to each element, creating a new array with the results. Since it processes each element once, the time complexity is linear, O(n), where n is the number of elements in the array.

2. sort() method:

   • Time Complexity: O(n * log(n))

   • Explanation: The sort() method sorts the elements of an array in place and returns the sorted array. It typically uses a comparison-based sorting algorithm, such as quicksort or mergesort, which has an average time complexity of O(n * log(n)), where n is the number of elements in the array. However, the worst-case time complexity can degrade to O(n^2) for some implementations (e.g., if the array is already sorted or nearly sorted).

Two Pointers from Different Directions Approach:

To optimize the solution further, we can utilize the two pointers technique with pointers moving from different directions. This approach takes advantage of the fact that the input array is sorted in non-decreasing order.

function sortedSquares (nums) {
    let result = [];
    let i = 0; j = nums.length - 1; k = nums.length - 1;
    while (i <= j) {
        if (nums[i] * nums[i] < nums[j] * nums[j]) {
            result[k--] = nums[j] * nums[j];
            j--;
        } else {
            result[k--] = nums[i] * nums[i];
            i++;
        };
    };
    return result;
 };

Time Complexity Analysis:

The time complexity of this approach is O(n), where n is the number of elements in the array. It is more efficient than the brute force approach since it only iterates through the array once.

Conclusion:

By leveraging the two pointers technique with pointers moving from different directions, we can efficiently solve the problem of manipulating arrays of sorted squares. This optimized solution offers a time complexity of O(n), providing a significant improvement over the brute force approach. Thus, for similar problems involving sorted arrays, it's beneficial to explore various techniques, such as the two pointers approach, to achieve optimal efficiency.