Algorithms Related to Array: Part 2

This article is a continuation of a series of articles related to algorithms based on ARRAY data structure.

Algorithms Related to Array: Part 1

Minimum Size Subarray

Suppose we are given a numerical array and a target value, then what is the minimum size of a continuous subarray whose sum is larger than the given target value? This is the minimum size subarray problem.

The solution to this problem is to use a trick called moving window, which is an extension of double-pointer technique we used before.

Instead of enumerating all the possible combinations of subarrays, using moving window will first collect the subarray under the window, and then if the subarray fulfills the requirement (its sum is larger than the target value), we will record the size of the moving window, and then shrink the moving window from the array’s beginning position in order to check whether the sub-subarray fulfills the requirement or not. Otherwise, we will increase the moving windows size by extending the subarray’s end position in the array.

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        min_len=10000000000
        begin_index = 0 
        sum_value = 0 
        for index in range(len(nums)):
            sum_value = sum_value+nums[index]
            while sum_value>=target:
                min_len=min([min_len, index-begin_index+1])
                sum_value -= nums[begin_index]
                begin_index += 1 
                
        if min_len == 10000000000:
            return 0
        else:
            return min_len

Spiral Matrix

Spiral matrix tries to construct a matrix in this way when the square side n (n=3 in the example) is given:

Solving this problem should understand four different ways of arrange elements in the matrix:

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        
        output = [[0]*n for _ in range(n)]
        count = 1 
        loop = n//2 
        for loop_index in range(loop):
            # from left to right 
            ele_cont = n - 1- loop_index*2
            for col_index in range(loop_index, loop_index+ele_cont):
                output[loop_index][col_index] = count
                count = count+1 
            # from top to bottom
            for row_index in range(loop_index, loop_index+ele_cont):
                output[row_index][n-1-loop_index] = count
                count = count+1
            # from right to left 
            for col_index in range(n-loop_index-1, n-loop_index-1-ele_cont, -1):
                output[n-1-loop_index][col_index] = count 
                count = count+1
            # from bottom to top 
            for row_index in range(n-loop_index-1, n-loop_index-1-ele_cont, -1):
                output[row_index][loop_index] = count
                count = count+1
        if (n//2*2 == n):
            pass
        else:
            output[n//2][n//2] = n*n
        return output

• in the top row, elements are listed from left to right
• in the right row, elements are listed from top to bottom
• in the bottom row, elements are listed from right to left
• in the left row, elements are listed from bottom to right
• after each loop, there will be 2 less elements that needs to be arranged
• if the square side is odd, then the central element in the square matrix corresponds to the maximum value

Reference

• Array in Leetcode (in Chinese)