🗓️ LeetCode Daily Challenge – Day 2

🔑 Prerequisite Knowledge:

Matrices and Sliding Window Technique – Key Points:

1. Matrices:
   • Matrices are 2D arrays organized in rows and columns. Each element is accessed using its row and column indices.
   • Matrices are useful in a variety of problems where data needs to be organized spatially, like image processing or game grids.
2. Matrix Traversal:
   • Matrix traversal refers to navigating through a matrix to read or modify its elements. Traversals can be in row-major order, column-major order, or special patterns like diagonal or spiral traversal.
   • For spiral traversal, we typically move in a cycle—right, down, left, and up.
3. Sliding Window Technique:
   • Sliding window is an efficient technique often used with arrays or strings. It involves moving a window (or subarray) over the main array while maintaining or updating certain properties (e.g., sum, max, min).
4. Time Complexity in Matrix and Array Operations:
   • Traversing a matrix or an array linearly has a time complexity of O(n), where n is the number of elements.

🧠 LeetCode Problem 59: Spiral Matrix II

🚀 A. Problem Description:

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

Example 1:

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

Constraints:

• 1 ≤ n ≤ 20

You can find the full problem description here. 👈

💡 B. Thought Process:

1. Understand the problem: 🤔
   • We are tasked with creating an n x n matrix where the numbers from 1 to n^2 are arranged in a spiral order, starting from the top left corner.
   • The matrix must be filled layer by layer, moving in a circular pattern: right, down, left, and up, shrinking the boundaries as we go.
   • Special consideration is needed for when n is odd, where a single central value remains after filling the outer layers.
2. Break it down:
   • 📥 Inputs: An integer n representing the size of the matrix.
   • 📤 Outputs: A 2D matrix of size n x n filled with integers in spiral order from 1 to n^2.
   • 💭 Edge cases:
     • For n = 1, the matrix will have only one element, which is 1.
     • For very large n, we need to ensure efficient traversal and memory usage.
3. Choose an approach:
   • Version 1: Iteratively fill the matrix using boundary values and shrink the boundaries after each full cycle.
   • Version 2: Use a slightly different technique that defines four distinct boundaries and updates them while traversing each edge of the matrix.

🔨 C. Approach 1: Iterative Layer by Layer Traversal

📝 Plan:

1. Start with a matrix of zeros and initialize the variables: startx, starty for the top-left corner and loop to represent the number of layers.
2. For each layer, fill the four sides (right, down, left, up), updating the counter count after each insertion.
3. After completing a full loop, update the starting points startx and starty.
4. Handle the special case where n is odd by filling the center element after all layers are processed.

🧮 Complexity:

• ⏳ Time complexity: O(n^2) since we are filling n^2 elements in the matrix.
• 🗂️ Space complexity: O(n^2) because the matrix itself requires O(n^2) space.

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        nums = [[0] * n for _ in range(n)]
        startx, starty = 0,0
        loop, mid = n//2, n//2
        count = 1

        for offset in range(1, loop+1):
            # left to right
            for i in range(starty, n - offset):
                nums[startx][i] = count
                count += 1

            # top to bottom
            for i in range(startx, n - offset):
                nums[i][n - offset] = count  # Mistake: nums[i][n - offset]
                count += 1
            
            # right to left
            for i in range(n-offset, starty, -1):
                nums[n- offset][i] = count  # Mistake nums[n-offset][i]
                count += 1

            # bottom to top
            for i in range(n-offset, startx, -1):
                nums[i][starty] = count 
                count += 1

            startx += 1
            starty += 1  # Forget to add  

        if n % 2 == 1:  # Forget to handle odd number, need to add middle 
            nums[mid][mid] = n*n

        return nums

🔨 C. Approach 2: Four Boundaries Method

📝 Plan:

1. Start by defining the matrix and initializing four boundary markers: top, bottom, left, and right.
2. Use these boundaries to control where to fill the elements in the matrix:
   • First, traverse from left to right along the top boundary.
   • Then, move from top to bottom along the right boundary.
   • Next, traverse from right to left along the bottom boundary.
   • Finally, move from bottom to top along the left boundary.
3. After each full cycle of filling, adjust the boundary markers inward to handle the next layer.
4. Continue until all elements have been placed in the matrix.

🧮 Complexity:

• ⏳ Time complexity: O(n^2) because we are filling each element exactly once.
• 🗂️ Space complexity: O(n^2) for storing the matrix.

class Solution:
    def generateMatrix(self, n):
        if n <= 0:
            return []
        
        # Initialize the n x n matrix
        matrix = [[0]*n for _ in range(n)]

        # Set initial boundaries
        top, bottom, left, right = 0, n-1, 0, n-1
        num = 1

        # Continue while the boundaries haven't crossed
        while top <= bottom and left <= right:
            # Fill top row from left to right
            for i in range(left, right + 1):
                matrix[top][i] = num
                num += 1
            top += 1

            # Fill right column from top to bottom
            for i in range(top, bottom + 1):
                matrix[i][right] = num
                num += 1
            right -= 1

            # Fill bottom row from right to left
            for i in range(right, left - 1, -1):
                matrix[bottom][i] = num
                num += 1
            bottom -= 1

            # Fill left column from bottom to top
            for i in range(bottom, top - 1, -1):
                matrix[i][left] = num
                num += 1
            left += 1

        return matrix

🔎 D. Edge Cases:

• n = 1: Only one element is required in the matrix.
• Very large n: Ensure time complexity scales properly as the matrix grows.

🔗 E. Similar Questions:

• 🔗 LeetCode 54: Spiral Matrix

• 🔗 劍指Offer 29: Print Matrix Clockwise

🧠 LeetCode Problem 209: Minimum Size Subarray Sum

🚀 A. Problem Description:

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

Example 1:

• Input: s = 7, nums = [2,3,1,2,4,3]
• Output: 2
• Explanation: The subarray [4,3] is the smallest subarray with a sum greater than or equal to 7.

Constraints:

• 1 ≤ s ≤ 10^9
• 1 ≤ nums.length ≤ 10^5
• 1 ≤ nums[i] ≤ 10^5

You can find the full problem description here. 👈

💡 B. Thought Process:

1. Understand the problem: 🤔
   • We are given an array of positive integers and a target sum s. The goal is to find the smallest subarray (contiguous sequence of elements) whose sum is greater than or equal to s.
   • A brute force approach could check all possible subarrays, but this would be inefficient with a time complexity of O(n²).
   • A more optimized approach is to use the sliding window technique, which can reduce the time complexity to O(n) by dynamically adjusting the window size.
2. Break it down:
   • 📥 Inputs: A positive integer s and an array nums of positive integers.
   • 📤 Outputs: The length of the smallest subarray whose sum is at least s, or 0 if no such subarray exists.
   • 💭 Edge cases:
     • If all elements are smaller than s, and their sum never reaches s.
     • If the input array is empty.
3. Choose an approach:
   • Version 1: Use a brute force approach to check every possible subarray and calculate their sums.
   • Version 2: Use a sliding window to maintain a running sum and dynamically adjust the window size.

🔨 C. Approach 1: Brute Force

📝 Plan:

1. Use two nested loops to evaluate every possible subarray:
   • The outer loop picks the start index of the subarray.
   • The inner loop picks the end index and calculates the sum of the elements in the subarray.
2. For each subarray, check if the sum is greater than or equal to s. If so, update the minimum length and move on to the next subarray.
3. Return the smallest subarray length found, or 0 if no subarray meets the condition.

🧮 Complexity:

• ⏳ Time complexity: O(n²) because for each starting point of a subarray, we loop through all possible endpoints, checking their sums.
• 🗂️ Space complexity: O(1) since we only use a few variables to track the current subarray sum and the minimum length.

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        l = len(nums)
        min_len = float('inf')
        
        for i in range(l):
            cur_sum = 0
            for j in range(i, l):
                cur_sum += nums[j]
                if cur_sum >= s:
                    min_len = min(min_len, j - i + 1)
                    break
        
        return min_len if min_len != float('inf') else 0

🔨 C. Approach 2: Sliding Window

📝 Plan:

1. Start with two pointers left and right that represent the current subarray.
2. Expand the right pointer to increase the window size, and add the element at right to cur_sum.
3. When cur_sum is greater than or equal to s, shrink the window by moving the left pointer to the right, subtracting elements from cur_sum as you go.
4. Keep track of the smallest window length during this process.

🧮 Complexity:

• ⏳ Time complexity: O(n) because each element is added and removed from the window at most once.
• 🗂️ Space complexity: O(1) as no extra space is needed apart from a few variables.

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        l = len(nums)
        left = 0
        cur_sum = 0
        min_len = float('inf')  # Start with an infinitely large length
        
        for right in range(l):
            cur_sum += nums[right]
            
            while cur_sum >= s:  # Shrink the window as much as possible while the condition is met
                min_len = min(min_len, right - left + 1)
                cur_sum -= nums[left]
                left += 1
        
        return min_len if min_len != float('inf') else 0

🔎 D. Edge Cases:

• If no subarray exists that meets or exceeds s, the output should be 0.
• If nums contains only one element and that element is smaller than s, return 0.

🔗 E. Similar Questions:

• 🔗 LeetCode 76: Minimum Window Substring
• 🔗 LeetCode 904: Fruit Into Baskets

✨ Happy coding! 🤓