Description: Solution: From the last value, we are gonna update the goal pointer when i + nums[i] >= goal. The reason we do ">=" is that we can skip the index. The previous value of the last, we can skip that index. When the goal pointer reach out the nums[0], then it is True. Time Complexity: O(n)
Description: Solution: row = [1] * n => The bottom row: [1, 1, 1, 1, 1, 1, 1] We start from (n-2) with reverse order. When we complete the second row[7, 6, 5, 4, 3, 2, 1], we update this newRow as row. Time Complexity: O(n*m) Space Complexity: O(n)
Description: Solution: We should consider if the number is two digits case: 10, 20 Since A-Z is 26, 20-26 is the right range for decode. ex) s = "112" dp[3] = 1 dp[2] = 1 dp[1] = 1 + 1 = 2 dp[0] = 2 + 1 = 3 Space Complexity: O(1)
Description: Solution: We have to consider three cases: The first value of the array is the biggest number. Except the first value, try to find the maximum of the other values. Except the last value, try to find the maximum of the other values. Time Complexity: O(n) Space Complexity: O(1)
Description: Solution: ex) s = "leetcode" wordDict = ["leet", "code"] In s, we start from the end of the string. dp[8] = True do[7] = False dp[6] = dp[5] = False dp[4] = True = dp[4 + 4] dp[3] = dp[2] = dp[1] = False dp[0] = True = dp[0 + 4] If dp[0] is True, it means we can break the string with wordDict!
Description: Solution: We have two list: start & end. ex) start: [0, 5, 15] end: [10, 20, 30] We shift the start pointer when start[s] is less than end[e] => count += 1 We shift the end pointer when start[s] is equal or more thn end[e] => count -= 1 Time Complexity: O(nlogn) Space Complexity: O(n)