LeetCode 977 – Squares of a Sorted Array

• Algorithm: Two‑pointers
• After squaring, the largest numbers are at the two ends of the array, while the smallest numbers gather in the middle. This naturally suggests using a pointer at the start and a pointer at the end.
• Modifying the original array in place can accidentally overrwite elements that haven’t been visited yet, so it’s safer to fill a new array from the back to the front.

Consider a squared sequence like {4, 1, 0, 9, 16}. Becauce you cannot know whether the next pair (1 and 9) contains a number larger than 4, you shouldn’t update the index that points to the position of 4, nor should you push 4 into the result too early.

• A flawed implementation:

vector<int> sortedSquares(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    int leftSq = nums[left] * nums[left];
    int rightSq = nums[right] * nums[right];
    vector<int> res;
    if (nums.size() == 1) {
        nums[left] = leftSq;
        return nums;
    }
    while (left <= right) {
        if (leftSq >= rightSq) {
            res.insert(res.begin(), leftSq);
            ++left;
            leftSq = nums[left] * nums[left];
        } else {
            res.insert(res.begin(), rightSq);
            --right;
            rightSq = nums[right] * nums[right];
        }
    }
    return res;
}

Both ++left and --right can cause an out‑of‑bounds access. The lesson is: always place the statements that change the indices at the very end of the loop body, letting the while condition guard the next access. To still use the updated index, compute the squares at the beginning of the next iteration. This effectively interleaves the loop condition between squaring and index advancement.

The same idea leads to a correct vertion, which also avoids the expensive O(n²) cost of inserting at the front of a vector:

• Working code (O(n)):

vector<int> sortedSquares(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    int pos = nums.size() - 1;
    vector<int> squared(nums.size()); // must be pre‑allocated
    while (left <= right) {
        if (nums[left] * nums[left] >= nums[right] * nums[right]) {
            squared[pos--] = nums[left] * nums[left];
            ++left;
        } else {
            squared[pos--] = nums[right] * nums[right];
            --right;
        }
    }
    return squared;
}

Notice that we fill squared from the tail (pos) forward, which naturally builds the non‑decreasing order without any need for insertions at index 0.