LeetCode Day 02 Arrays(2/2)

LeetCode Practice Day 2, arrays (2/2)

Question 1

977. Squares of a Sorted Array

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

After seeing the question, the first thing that comes to mind is the Brute force, using a for loop to square one by one, and then finally nums.sort() to sort them. It took 2 minutes and 11 seconds.

# Brute force
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            nums[i] = nums[i] * nums[i]
            i += 1
        nums.sort()
        return nums

But the sorting itself takes O(nlogn), which is hard, and it doesn’t make sense to practice the algorithm in this way.

I think the key to solving the problem should be in the double pointer, but the idea is limited to the process of squaring→sorting, applying the double pointer should also be sorted after squaring, right?

To change the idea, not to rush to calculate the number of squares, we can use the double pointer and a new array to do, and finally return the new array can do.

And this is a non-decreasing array, after squaring the largest number is exactly the head and tail of these two numbers.

That’s the basic idea of the problem. It took 6 minutes and 25 seconds to implement.

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        newList = [0] * len(nums)
        l, r = 0, len(nums)-1
        n = len(nums)-1
        while l <= r:
            if nums[l] **2 < nums[r] ** 2:
                newList[n] = nums[r] **2
                r -= 1
            else:
                newList[n] = nums[l] **2
                l += 1
            n -= 1
        return newList

Question 2

209. Minimum Size Subarray Sum

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.

The complexity of the brute force of the two for loops goes to O(n^2), which is obviously not the best solution, this should be solved with the idea of a sliding window.

But I can’t code it.

Sad.

Optimised solution: sliding window To implement a sliding window in this problem, determine the following three main points:

• What is inside the window?
• How to move the start position of the window?
• How do I move the end of the window?

1. A window is the smallest consecutive subarray of length satisfying its sum ≥ s.
2. How to move the start of the window: If the current window value is greater than s, the window should move forward (i.e., shrink).
3. How to move the end position of the window: the end position of the window is the pointer to the traversed array, i.e. the index in the for loop.

The key to solving the problem is how to move the window’s start position.

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        res = float("inf")
        i = 0 # window start
        sum = 0 # window length
        for j in range(len(nums)):
            sum += nums[j]
            while sum >= target:
                res = min(res,j-i+1)
                sum -= nums[i]
                i += 1
        return 0 if res == float("inf") else res

Question 3

59. Spiral Matrix II

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

We should look for the pattern first, when n is odd, the largest number should be in the middle. n is even, then we can only fill in the order of left → down → right → up, and each time we have to update the starting point of filling in the numbers.

I can’t do it. Look at other people’s solutions:

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix = [[0 for _ in range(n)] for _ in range(n)]
        i, r, c = 1, 0, 0
 
        while i <= n**2:
            while r < n and matrix[c][r] == 0:
                matrix[c][r] = i
                r += 1 if r != n-1 and matrix[c][r+1] == 0 else 0
                i += 1
            c += 1
 
            while c < n and matrix[c][r] == 0:
                matrix[c][r] = i
                c += 1 if c != n-1 and matrix[c+1][r] == 0 else 0
                i += 1
            r -= 1
 
            while r >= 0 and matrix[c][r] == 0:
                matrix[c][r] = i
                r -= 1 if r != 0 and matrix[c][r-1] == 0 else 0
                i += 1
            c -= 1
 
            while c >= 0 and matrix[c][r] == 0:
                matrix[c][r] = i
                c -= 1 if c != 0 and matrix[c-1][r] == 0 else 0
                i += 1
            r += 1
 
        return matrix