Post

Leetcode Day 2 - Advanced Array Manipulation

More advanced array techniques, including sliding window to find the minimum subarray sum and generating a matrix in a spiral order, which requires managing more complex array structures.

Posted Updated
By Le Lyu
views 6 min read

Array 21

DiffProblemPythonC++
Medium209 Minimum Size Subarray Sum✅✅
Medium59 Spiral Matrix II✅✅
Additional ACM QuestionsPythonJava
ACM 59 Range Sum  
ACM 44 Developer land purchase  

Minimum Size Subarray Sum

Link to Leetcode question2

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*

1
2
3

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

1
2

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

Example 3

1
2

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

Solution 3

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution(object):
    def minSubArrayLen(self, target, nums):
        left = 0
        right = 0
        cur_sum = 0
        min_len = len(nums) + 1

        while(right < len(nums)):
            cur_sum += nums[right]
            while(cur_sum >= target):
                min_len = min(min_len,right - left + 1)
                cur_sum -= nums[left]
                left += 1
            right += 1
        
        if(min_len == len(nums) + 1):
            return 0
        
        return min_len

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int slow = 0;
        int fast = 0;
        int sum = 0;
        int minLen = 100001;

        while(fast < nums.size()){
            sum += nums[fast];
            if (sum >= target){
                while(slow <= fast){
                    if(fast - slow + 1 < minLen)minLen = fast - slow + 1;
                    sum -= nums[slow];
                    slow ++;
                    if(sum < target)break;
                }
            }
            fast++;
        }
        if (minLen == 100001)return 0;
        return minLen;
    }
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int cur_sum = 0;
        int min_len = nums.length + 1;

        for(int right = 0;right < nums.length;right++){
            cur_sum += nums[right];
            while(cur_sum >= target){
                min_len = Math.min(min_len,right - left + 1);
                cur_sum -=nums[left++];
            }
        }

        return min_len == nums.length + 1 ? 0 : min_len;
    }
}

Similar Questions

DiffSimilar QuestionsPythonJava
Easy3095 Shortest Subarray With OR at Least K I4  
Medium718 Maximum Length of Repeated Subarray5  
Hard76 Minimum Window Substring6  
    

Spiral Matrix II

Link to Leetcode question7

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

Example 1

Desktop View

1
2

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

Example 2

1
2

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

Note 8

Desktop View

Solution

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        if n == 0:
            return []

        nums = [[0] * n for _ in range(n)]
        loops,mid = n//2, n//2
        row_start = 0
        col_start = 0
        num = 1

        for loop in range(loops):
            print(loop)
            for i in range(col_start,n - loop - 1):
                nums[row_start][i] = num
                num += 1
            for i in range(row_start,n - loop - 1):
                nums[i][n - loop - 1] = num
                num += 1
            for i in range(n - loop - 1,col_start,-1):
                nums[n - loop - 1][i] = num
                num += 1
            for i in range(n - loop - 1,row_start,-1):
                nums[i][col_start] = num
                num += 1
            
            col_start += 1
            row_start += 1
            
        if(len(nums) % 2 == 1):
            nums[mid][mid] = num
        
        return nums

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int colStart = 0; 
        int rowStart = 0; 
        int colEnd = n - 1; 
        int rowEnd = n - 1; 
        int num = 1; 

        vector<vector<int>> grid(n, vector<int>(n)); 

        while (rowStart <= rowEnd && colStart <= colEnd) {
            for (int i = colStart; i <= colEnd; i++) {
                grid[rowStart][i] = num++;
            }
            rowStart++; 

        
            for (int i = rowStart; i <= rowEnd; i++) {
                grid[i][colEnd] = num++;
            }
            colEnd--;

            if (rowStart <= rowEnd) {
                for (int i = colEnd; i >= colStart; i--) {
                    grid[rowEnd][i] = num++;
                }
                rowEnd--;
            }

            if (colStart <= colEnd) {
                for (int i = rowEnd; i >= rowStart; i--) {
                    grid[i][colStart] = num++;
                }
                colStart++; 
            }
        }

        return grid;
    }
};

Similar Questions

DiffSimilar QuestionsPythonJava
Medium885 Spiral Matrix III9  
Medium2326 Spiral Matrix IV10  
    

Range Sum

Link to ACM question11

Problem Description

Given an integer array Array, calculate the sum of the elements within each specified range.

Input Description

The first line contains the length n of the integer array Array. The next n lines each contain an integer, representing the elements of the array. The subsequent inputs are the indices of the ranges to calculate the sum: a and b (b >= a), until the end of the file.

Output Description

Output the sum of the elements within each specified range.

Input Example

1
2
3
4
5
6
7
8

5
1
2
3
4
5
0 1
1 3

Output Example

1
2

3
9

Solution12

Developer land purchase

Link to ACM question13

Solution14

Reference

  1. 代码随想录-数组:https://programmercarl.com/数组理论基础.html. ↩︎

  2. Leetcode-209 Minimum Size Subarray Sum: https://leetcode.cn/problems/minimum-size-subarray-sum/. ↩︎

  3. 代码随想录-289长度最小的子数组: https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html. ↩︎

  4. Leetcode-3095 Shortest Subarray With OR at Least K I: https://leetcode.com/problems/shortest-subarray-with-or-at-least-k-i/description/. ↩︎

  5. Leetcode-718 Maximum Length of Repeated Subarray: https://leetcode.com/problems/maximum-length-of-repeated-subarray/description. ↩︎

  6. Leetcode-76 Minimum Window Substring: https://leetcode.com/problems/minimum-window-substring/description/. ↩︎

  7. Leetcode-59: Spiral Matrix: https://leetcode.com/problems/spiral-matrix-ii/. ↩︎

  8. 代码随想录-螺旋矩阵: https://programmercarl.com/0059.螺旋矩阵II.html. ↩︎

  9. Leetcode-885 Spiral Matrix III: https://leetcode.com/problems/spiral-matrix-iii/description/. ↩︎

  10. Leetcode-2326 Spiral Matrix IV: https://leetcode.com/problems/spiral-matrix-iv/description/. ↩︎

  11. Kamacoder-59 Range Sum: https://kamacoder.com/problempage.php?pid=1070. ↩︎

  12. 代码随想录-区间和: https://www.programmercarl.com/kamacoder/0058.区间和.html#思路. ↩︎

  13. Kamacoder-44 Developer land purchase: https://kamacoder.com/problempage.php?pid=1044. ↩︎

  14. 代码随想录-开发商购买土地: https://www.programmercarl.com/kamacoder/0044.开发商购买土地.html#思路. ↩︎

Data Structure and Algorithm, Leetcode, Array
array sliding window
This post is licensed under CC BY 4.0 by the author.