Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, find the minimal length of a contiguous subarray whose sum is greater than or equal to target. If no such subarray exists, return 0.

Examples:

• Input: target = 7, nums = [2,3,1,2,4,3]
  Output: 2
  Explanation: The subarray [4,3] has the minimal length with sum 7.
• Input: target = 4, nums = [1,4,4]
  Output: 1
• Input: target = 11, nums = [1,1,1,1,1,1,1,1]
  Output: 0

Constraints:

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

Approach:

A brute-force approach with nested loops would result in O(n^2) time complexity, which is inefficient for large inputs. Instead, we can use a sliding window technique to achieve O(n) time complexity.

The sliding window approach uses two pointers to represent the current window's boundaries. We expand the window by moving the right pointer and add elements to our current sum. When the sum becomes greater than or equal to the target, we record the window size and try to shrink it from the left to find a potentially smaller valid window.

Solution Code:

<ncode class="language-cpp">
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int currentSum = 0;
        int left = 0;
        int minLength = INT_MAX;
        
        for (int right = 0; right < nums.size(); right++) {
            currentSum += nums[right];
            
            while (currentSum >= target) {
                int windowSize = right - left + 1;
                minLength = min(minLength, windowSize);
                currentSum -= nums[left++];
            }
        }
        
        return minLength == INT_MAX ? 0 : minLength;
    }
};
</ncode>

Spiral Matrix II

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 in spiral order, clockwise.

Examples:

• Input: n = 3
  Output: [[1,2,3],[8,9,4],[7,6,5]]
• Input: n = 1
  Output: [[1]]

Constraints:

• 1 <= n <= 20

Approach:

The key to solving this problem is to define clear boundaries for each layer of the spiral. We can fill the matrix layer by layer, starting from the outer layer and moving inward. For each layer, we fill the top row from left to right, the right column from top to bottom, the bottom row from right to left (if it exists), and the left column from bottom to top (if it exists).

Solution Code:

<ncode class="language-cpp">
class Solution {
public:
    vector generateMatrix(int n) {
        vector matrix(n, vector<int>(n, 0));
        
        int top = 0, bottom = n - 1;
        int left = 0, right = n - 1;
        int num = 1;
        
        while (top <= bottom && left <= right) {
            // Fill top row
            for (int i = left; i <= right; i++) {
                matrix[top][i] = num++;
            }
            top++;
            
            // Fill right column
            for (int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--;
            
            if (top <= bottom) {
                // Fill bottom row
                for (int i = right; i >= left; i--) {
                    matrix[bottom][i] = num++;
                }
                bottom--;
            }
            
            if (left <= right) {
                // Fill left column
                for (int i = bottom; i >= top; i--) {
                    matrix[i][left] = num++;
                }
                left++;
            }
        }
        
        return matrix;
    }
};
</ncode>