Leetcode Notes

Posted on 2024-10-21 Disqus:

Today, I began the long journey of practicing Leetcode problems. Previously, I only did a few problems to maintain familiarity, but today, I officially started preparing for interviews.

I have been thinking about how to efficiently solve Leetcode problems. In my opinion, to be efficient, one must memorize problems. Just as reading a book a hundred times reveals its meaning, training a language model through extensive practice hones its coding skills. Similarly, with Leetcode, through repeated practice, the answers will come naturally; quantity brings quality.

53. Maximum Subarray

The solution can be approached using Kadane’s Algorithm. The code is as follows:

def maxSubArray(nums):
    max_current = max_global = nums[0]
    for num in nums[1:]:
        max_current = max(num, max_current + num)
        max_global = max(max_global, max_current)
    return max_global

This is a classic dynamic programming problem, and the above algorithm actually hides the essence of dynamic programming.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
        }
        return *max_element(dp.begin(), dp.end());
    }
};

This code better reflects the essence of dynamic programming.

To understand the formula dp[i] = max(nums[i] + dp[i-1], nums[i]), we can analyze it from a dynamic programming perspective. The core idea here is to make the optimal choice at each position. Here is a detailed explanation:

1. What does `dp[i]` represent?

dp[i] represents the maximum subarray sum ending at position i.

2. Why compare `nums[i] + dp[i-1]` and `nums[i]`?

The key question is: Should the current maximum subarray include the previous part (dp[i-1])?
- nums[i] + dp[i-1]: If dp[i-1] is positive, adding the current nums[i] will increase the subarray sum, so we choose to add it.
- nums[i]: If dp[i-1] is negative, we choose to start a new subarray from the current position, as a negative sum will only drag down the current sum.

3. Why not compare subsequent numbers?

When making the comparison, we assume the subarray stops at position i. In other words, we consider the maximum value within the range [0:i]. At position i, we either add the previous subarray or abandon it and only use the current number.
We then traverse the entire array, finding the maximum value at each position, and finally return the largest value.

57. Insert Interval

This is a classic interval merging problem, where we need to merge a new interval into existing intervals.

The solution can be broken down as follows:

Step 1: Add all non-overlapping intervals that come before newInterval to the result.
Step 2: Merge all potentially overlapping intervals with newInterval. Note the conditions for merging.
Step 3: Add the remaining intervals to the result.

Note that the condition for merging intervals is that the start of the previous interval is less than or equal to the end of the subsequent interval, i.e., intervals[i][0] <= newInterval[1].

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        ret_list = []
        i = 0

        while i < len(intervals) and intervals[i][1] < newInterval[0]:
            ret_list.append(intervals[i])
            i += 1

        while i < len(intervals) and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(intervals[i][0], newInterval[0])
            newInterval[1] = max(intervals[i][1], newInterval[1])
            i += 1

        ret_list.append(newInterval)

        while i < len(intervals):
            ret_list.append(intervals[i])
            i += 1

        return ret_list

With careful attention to detail, this problem is not difficult.

300. Longest Increasing Subsequence

This is obviously a dynamic programming problem.

dp[i] represents the length of the longest increasing subsequence ending with a certain number.

Each time an element is added, we update the current dp array. If the current number is greater than the previous one, we increment the result by 1.

Note that the first dp[i] starts from index 1.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums)

        for i in range(1, len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

Complexity Analysis:

Time Complexity: $O(n^2)$, due to the two nested loops.
Space Complexity: $O(n)$, as we need a dp array of length n.

674. Longest Continuous Increasing Subsequence

This is a simple problem, but still worth understanding.

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums)
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                dp[i] = max(dp[i], dp[i-1] + 1)
        return max(dp)

392. Is Subsequence

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i = 0
        j = 0
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == len(s)

This problem can be solved using a two-pointer technique, with t as the base. If s contains matching characters, we move forward; if we reach the end of s, it means the match is complete.

115. Distinct Subsequences

This problem asks us to find how many distinct subsequences of string s equal string t.

First, we need to define dp, where dp[i][j] represents the number of distinct subsequences that can be formed from the first i characters of s to form the first j characters of t.

dp[i][0] represents when t is an empty string, the result is 1.
dp[0][j] represents forming t from an empty string, which results in 0.

For dp[i][j], the result depends on the characters at positions i and j:

If they are equal, the result is the sum of the cases where s[i-1] is not matched (dp[i-1][j]) and the cases where it is matched (dp[i-1][j-1]).
If they are not equal, the result is equal to dp[i-1][j].

Note that i, j refer to the first i and j characters.

Additionally, dp[0][0] is initialized to 1, as an empty string is a subsequence of any string.

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]
        for i in range(len(s) + 1):
            dp[i][0] = 1

        for j in range(1, len(t) + 1):
            for i in range(1, len(s) + 1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
                else:
                    dp[i][j] = dp[i-1][j]

        return dp[-1][-1]