Scribbling

Idea: Any characters that have frequencies less than k work as a breakpoints, meaning that the substring we're looking for can't include that particular character. So, recursively look for substrings while excluding those characters. Time complexity is O(N). from collections import Counter class Solution: def longestSubstring(self, s: str, k: int) -> int: return self.helper(s, k) def helper(self..

Refer to the below post for Knuth Shuffle. https://focalpoint.tistory.com/253 Shuffle Algorithm: Knuth Shuffle This post is about Knuth Shuffle, a shuffle algorithm. - This algorithm allows random shuffle, giving all permuations of array equal likelihood. - No need for additional arrays, so memory complexity.. focalpoint.tistory.com class Solution: def __init__(self, nums: List[int]): self.nums ..

Coming up with O(1) memory solution was very difficult for me. I refered to this post's last solution. https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/1322101/C%2B%2BJavaPython-MaxHeap-MinHeap-Binary-Search-Picture-Explain-Clean-and-Concise [C++/Java/Python] MaxHeap, MinHeap, Binary Search - Picture Explain - Clean & Concise - LeetCode Discuss Level up your coding s..

Making a new list is an easy solution to implement with recursion. class NestedIterator: def __init__(self, nestedList: [NestedInteger]): self.res = [] self._flattener(nestedList) self.ptr = 0 def _flattener(self, nestedList): for nl in nestedList: if nl.isInteger(): self.res.append(nl.getInteger()) else: self._flattener(nl.getList()) def next(self) -> int: ret = self.res[self.ptr] self.ptr += 1..

This problem is a special case of #300, which is LIS. Refer to LIS algorithm here. https://focalpoint.tistory.com/179 LeetCode: 300. Longest Increasing Subsequence - 시바견의 끄적임 1. 가장 간단한 DP 형태 O(N**2)이다. class Solution: def lengthOfLIS(self, nums: List[int]) -> int: dp = [0] * len(nums) dp[0] = 1 for i in range(1, len(nums)): temp = -1 j = i - 1 while j >= 0: if n.. focalpoint.tistory.com class So..

Tip of the day: A problem starts with "Longest" usually has something to do with DP. Though the difficulty is hard, it's not a difficult one. Seeing the below code will be enough for sure, so I won't give any explanation about it. class Solution: def longestIncreasingPath(self, matrix: List[List[int]]) -> int: m, n = len(matrix), len(matrix[0]) self.matrix = matrix self.visited = [[False] * n fo..

Using double counters. class Solution: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: from collections import Counter c1 = Counter(nums1) c2 = Counter(nums2) ret = [] for k in c2.keys(): ret.extend([k] * min(c1[k], c2[k])) return ret

This is a typical DP problem. At first, one should think of backtracking all the cases. That way, you can find the solution but it isn't efficient. In the meantime, you should notice that you will calculate for the same amount repeatedly when backtracking all the cases. Inspired by that idea, apply DP there. Below is the code. INF = int(1e9) class Solution: def coinChange(self, coins: List[int],..

Use dummy head to simplify code. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: dummy_head = ListNode() cur, p1, p2 = dummy_head, l1, l2 while p1 != None and p2 != None: if p1.val

O(N), O(1) Solution by using input array as a memory. class Solution: def findDuplicates(self, nums: List[int]) -> List[int]: ret = [] for i, num in enumerate(nums): if nums[abs(num) - 1] < 0: ret.append(abs(num)) nums[abs(num) - 1] *= -1 return ret