🗓️Day 02 – Array.
Topics: Array II
Problem solved:
#209 - Minimum Size Subarray Sum
#59 - Spiral Matrix II

📚Concept Review – Two pointers

Two pointers is a powerful way to reduce time complexity from O(n²) to O(n) when working with linear structures like arrays, strings and linked lists.
When to use

1. Sorted array or string. ---- if it mentions sorted array, we should think about two pointers. Such as Two Sum or Squares of a Sorted Array
2. Subarray with special conditions (sliding window) ---- sliding window is a special two pointers. so if we want to get a special array or the result of a special array, we can use two pointers. Such as MInimum Size Subarray Sum or Longest Increasing Subsequence
3. Traverse, merge or compare two sequences ---- Such as Merge Sorted Array
4. Fast and slow pointers (Floyd cycle detection) ---- if we need to detect if there is a cycle in linked list.
5. Problems involving shrinking a range from both sides ---- Parlindonme Number

---

🧩Problem solution – 209. Minimum Size Subarray Sum

link

💡Problem description

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

Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

1 <= target <= 10 ⁹
1 <= nums.length <= 10 ⁵
1 <= nums[i] <= 10 ⁴

🧭Thought Process

This is a good example to use two pointers. If there is a such subarray, we use left and right to represent its beginning and end. At first, first and right are both at the beginning of nums. Then we move the right until the subarray fulfill the requirement. After that, move the left until the subarray fulfill the requirement. Repeat these two steps.

💻Code Implementation

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int start = 0, end = 0;
        int len = nums.size();
        int newlen = 0, minlen = 1e9, i = 0, sum = 0;
        for (i = 0; i < len; i++) {
            sum += nums[end];
            newlen = end - start + 1;
            while (sum >= target) {
                newlen = end-start+1;
                minlen = min(minlen, newlen);
                sum -= nums[start];
                
                start++;
            }
            end++;
        }
        return minlen == 1e9 ? 0 : minlen;
    }
};

⏱️Complexity Analysis

• Time complexity: O(n)
• Space complexity: O(1)

🧩Problem solution – 59. Spiral Matrix II

link

💡Problem description

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

Example 1:

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

Example 2:
Input: n = 1
Output: [[1]]

Constraints:

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

🧭Thought Process

Just follow the steps that mentioned.

💻Code Implementation

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n, 0));
        int x = 0, y = 0;
        int loop = n / 2;
        int i = 0, j = 0;
        int offset = 1, count = 1;

        while (loop--) {
            i = x;
            j = y;

            for (j; j < n - offset; j++) {
                ans[i][j] = count;
                count++;
            }
            for (i; i < n - offset; i++) {
                ans[i][j] = count;
                count++;
            }
            for (; j > y; j--) {
                ans[i][j] = count;
                count++;
            }
            for (; i > x; i--) {
                ans[i][j] = count;
                count++;
            }
            offset++;
            x++;
            y++;
        }
        if (n % 2 != 0) {
            ans[n / 2][n / 2] = n * n;
        }
        return ans;
    }
};

⏱️Complexity Analysis

• Time complexity: O(n)
• Space complexity: O(n²)