Squares of a Sorted Array (LeetCode 977)

The challenge in squaring a sorted array that contaisn negative numbers is that the largest squares can appear at both ends of the array. While a naive solution involves squaring every element and then sorting the array in $O(n \log n)$ time, a more efficient $O(n)$ approach utilizes the two-pointer technique.

Two-Pointer Strategy

By placing one pointer at the beginning and another at the end of the array, we can compare the squares of the elements. Since the array is sorted, the maximum squared value must be at either left or right. We populate a new result array starting from the last index and move the pointers inward.

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        int left = 0;
        int right = n - 1;
        int pos = n - 1;

        while (left <= right) {
            long long leftSquare = nums[left] * nums[left];
            long long rightSquare = nums[right] * nums[right];

            if (leftSquare > rightSquare) {
                result[pos--] = leftSquare;
                left++;
            } else {
                result[pos--] = rightSquare;
                right--;
            }
        }
        return result;
    }
};

Minimum Size Subarray Sum (LeetCode 209)

Given an array of positive integers and a target value, the goal is to find the minimal length of a contiguous subarray whose sum is greater than or equal to the target. A brute-force approach using nested loops results in $O(n^2)$ complexity, which is inefficient for large datasets.

Sliding Window Optimization

The sliding window technique reduces the complexity to $O(n)$. We maintain a window defined by two pointers: start and end. The end pointer expands the window to include eleemnts untill the sum meets the target. Once the condition is met, we contract the window by moving the start pointer forward to find the smallest possible length that still satisfies the sum requirement.

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int minLength = INT_MAX;
        int currentSum = 0;
        int windowStart = 0;

        for (int windowEnd = 0; windowEnd < nums.size(); ++windowEnd) {
            currentSum += nums[windowEnd];
            
            while (currentSum >= target) {
                int currentWidth = windowEnd - windowStart + 1;
                minLength = min(minLength, currentWidth);
                
                // Shrink the window from the left
                currentSum -= nums[windowStart++];
            }
        }

        return (minLength == INT_MAX) ? 0 : minLength;
    }
};

Spiral Matrix II (LeetCode 59)

Generating an $n \times n$ matrix filled with elements from 1 to $n^2$ in spiral order requires careful boundary management. The core difficulty lies in maintaining a consistent logic for traversing each edge of the spiral.

The Loop Invariant Principle

To avoid "off-by-one" errors, we adopt a strict loop invariant: Left-Closed, Right-Open. This means each loop processes the side of the square from the first element up to, but not including, the last element of that row or column. The last element is handled as the first element of the next side's traversal.

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> matrix(n, vector<int>(n, 0));
        int startX = 0, startY = 0;
        int loopCount = n / 2;
        int mid = n / 2;
        int counter = 1;
        int offset = 1;

        while (loopCount--) {
            int row = startX;
            int col = startY;

            // Top side: Left to Right
            for (col = startY; col < n - offset; ++col) {
                matrix[startX][col] = counter++;
            }

            // Right side: Top to Bottom
            for (row = startX; row < n - offset; ++row) {
                matrix[row][col] = counter++;
            }

            // Bottom side: Right to Left
            for (; col > startY; --col) {
                matrix[row][col] = counter++;
            }

            // Left side: Bottom to Top
            for (; row > startX; --row) {
                matrix[row][col] = counter++;
            }

            // Move to the inner sub-matrix
            startX++;
            startY++;
            offset++;
        }

        // If n is odd, fill the center cell
        if (n % 2 != 0) {
            matrix[mid][mid] = counter;
        }

        return matrix;
    }
};