<jupyter_start><jupyter_text>String   27. Remove Element [27. Remove Element](https://leetcode.com/problems/remove-element/) Two pointers (same direction):- [0, i): being processed - [i, j): garbage area - [j, n-1]: unexplored Define the meaning of each pointer. Ensure the correctness of initialization and each step of the algorithm.<jupyter_code>class Solution:
    def removeElement(self, nums, val) -> int:  
        if not nums or len(nums) == 0: 
            return 0 
        
        i = j = 0  
        n = len(nums)
        while j != n: 
            # case 1: delete 
            if nums[j] == val: 
                j += 1 
            else: 
                nums[i] = nums[j] 
                i += 1 
                j += 1 
        
        return i<jupyter_output><empty_output><jupyter_text>two pointers and three regions     - [0, i):numbers to be kept     - [i, j]: unexplored numbers     - (j, n-1]: numbers to be removed<jupyter_code>class Solution:
    def removeElement(self, nums, val: int) -> int:  
        if not nums or len(nums) == 0: 
            return 0 
        
        n = len(nums) 
        # initially, i = 0, j = n-1, because [i, j] is unexplored area. 
        i = 0 
        j = n - 1 
        while i <= j:
            
            if nums[i] == val: 
                # if current element i is the number to be removed, we swap nums[i] and nums[j]. 
                nums[i], nums[j] = nums[j], nums[i] 
                # After swaping, new nums[i] is still unexplored and new nums[j] is to be removed. 
                # Thus, to maintain the meaning of i and j, we need to decrement j by 1 and keep i 
                j -= 1 
            else: 
                # if nums[i] is to be kept, 
                i += 1 

        return i

from timeit import default_timer as timer 
import time
start = timer() 
time.sleep(3)
end = timer() 
end - start 
import func_timeout
def long_function(argument1, argument2): 
    print(argument1, argument2)
    while True: pass
    return 'universe'

def run_function(f, my_argument, arg2, max_wait, default_value):
    try:
        return func_timeout.func_timeout(max_wait, long_function, args=[my_argument, arg2])
    except func_timeout.FunctionTimedOut:
        pass
    return default_value
for _ in range(5):
    x = run_function(long_function, 'start printing', 'start printg', 2, 'world')
    print(x)<jupyter_output>start printing start printg
world
start printing start printg
world
start printing start printg
world
start printing start printg
world
start printing start printg
world<jupyter_text>283. Move Zeroes [283. Move Zeroes](https://leetcode.com/problems/move-zeroes/)<jupyter_code>class Solution:
    def moveZeroes(self, nums) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        """
        two pointers: 
        Define: 
        j: processing 
        [0, i): kept 
        [i, j): 0 area 
        (j, n): unexplored 
        
        [1,3,12,3,12] 
                i 
                     j 
         
         while j < n: 
            if nums[j] == 0: 
                # move 
                j += 1 
            else: 
                # keep 
                nums[i] = nums[j] 
                i += 1 
                j += 1 
        # fill nums[i:] with 0  
        while i < n: 
            nums[i] = 0 
            i += 1 
        """ 
        if len(nums) <= 1: 
            return  
        n = len(nums) 
        i = 0 
        j = 0 
        while j < n: 
            if nums[j] == 0: 
                j += 1 
            else: 
                nums[i] = nums[j] 
                j += 1 
                i += 1 
        
        while i < n: 
            nums[i] = 0 
            i += 1 
            
        return<jupyter_output><empty_output><jupyter_text>26. Remove Duplicates from Sorted Array [26. Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/)<jupyter_code>class Solution:
    def removeDuplicates(self, nums) -> int: 
        """ 
        two pointers: 
        define: 
        j: processing 
        (0, i): processed and kept 
        [i, j): garbage 
        (j, n): to be explored 
        
        [0,1,2,3,4,2,2,3,3,4] 
                   i 
                             j 
        
        while j < n: 
            if i == 0 and nums[j] == nums[i-1]: 
                j += 1 
            else: 
                # keep 
                nums[i] = nums[j] 
                i += 1 
                j += 1 
        
        """ 
        n = len(nums) 
        if n <= 1: 
            return n 
        
        i = 1
        j = 1 
        
        while j < n: 
            if nums[j] == nums[i-1]: 
                j += 1 
            else: 
                nums[i] = nums[j] 
                i += 1 
                j += 1 
                
        return i<jupyter_output><empty_output><jupyter_text>80. Remove Duplicates from Sorted Array II[80. Remove Duplicates from Sorted Array II](https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/)<jupyter_code>class Solution:
    def removeDuplicates(self, nums) -> int:
        if len(nums) <= 2: 
            return len(nums) 
        
        n = len(nums) 
        i = j = 2 
        
        while j != n: 
            if nums[j] == nums[i-2]: 
                j += 1 
            else: 
                nums[i] = nums[j]
                j += 1 
                i += 1 
        
        return i<jupyter_output><empty_output><jupyter_text>1047. Remove All Adjacent Duplicates In String[1047. Remove All Adjacent Duplicates In String](https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/) Two pointers solution: Notice: if i, j are initialized as 1, then it will fail for ![image.png](attachment:image.png)<jupyter_code>class Solution:
    def removeDuplicates(self, s: str) -> str: 
        """
        two pointers solution 
        """ 
        if len(s) <= 1: 
            return s 
        
        n = len(s)  
        a = list(s) 
        # print(s_list) 
        i = j = 0  
        while j != n: 
            if i == 0 or a[j] != a[i-1]: 
                # keep 
                a[i] = a[j] 
                i += 1 
                j += 1 
            else: 
                # remove 
                i -= 1 
                j += 1 
        return ''.join(a[:i])<jupyter_output><empty_output><jupyter_text>Stack solution:<jupyter_code>from collections import deque 
# stack solution 
class Solution:
    def removeDuplicates(self, s: str) -> str:
        if len(s) <= 1: 
            return s 
        
        i = 1 
        
        stack = deque([s[0]]) 
        
        while i != len(s): 
            if len(stack) >= 1 and s[i] == stack[-1]: 
                stack.pop() 
            else: 
                stack.append(s[i]) 
            i += 1 
        return ''.join(list(stack))<jupyter_output><empty_output><jupyter_text>1209. Remove All Adjacent Duplicates in String II[1209. Remove All Adjacent Duplicates in String II](https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/)  Two pointers                 """        three pointers, four region.         i, j', j.         [0, i): processed and to be kept         [i, j): garbage area         [j, j'): repeated sequence         [j', n-1]: unexplored                 d e e e d b b c c c b d a a        i          j           j'                  """<jupyter_code># Runtime: 219 ms, faster than 30.33%
class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        if len(s) < k or len(s) <= 1: 
            return s 
        
        n = len(s) 
        
        # fixme: push the first k - 1 elements 
        stack_count = deque([1])  
        stack_res = deque([s[0]])  
        i = 1 
        # i = k # fixme: check 
        while i != n: 
            if len(stack_count) == 0: 
                stack_count.append(1) 
                stack_res.append(s[i])
            
            elif s[i] != stack_res[-1]: 
                stack_count.append(1) 
                stack_res.append(s[i])
            elif s[i] == stack_res[-1] and stack_count[-1] + 1 < k: 
                stack_res.append(s[i]) 
                stack_count[-1] += 1 
                 
            else:
                stack_count.pop()  
                for _ in range(k-1):
                    if stack_res: 
                        stack_res.pop()
                
            i += 1 
        
        return ''.join(list(stack_res)) 
            
        
# Runtime: 219 ms, faster than 10.33%

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        if len(s) < k or len(s) <= 1: 
            return s 
        
        n = len(s) 
        
        # fixme: push the first k - 1 elements 
        stack_count = deque([1])  
#         stack_res = deque([s[0]])  
        stack_res = [] 
        stack_res.append(s[0]) 
        s_list = list(s) 
        i = 1 
        # i = k # fixme: check 
        while i != n: 
            if len(stack_count) == 0: 
                stack_count.append(1) 
                stack_res.append(s_list[i])
            
            elif s_list[i] != stack_res[-1]: 
                stack_count.append(1) 
                stack_res.append(s_list[i])
            elif s[i] == stack_res[-1] and stack_count[-1] + 1 < k: 
                stack_res.append(s_list[i]) 
                stack_count[-1] += 1 
                 
            else:
                stack_count.pop()  
                for _ in range(k-1):
                    if stack_res: 
                        stack_res.pop()
                
            i += 1 
        
        return ''.join(list(stack_res)) 
            
        
# Runtime: 163 ms, faster than 50.60%
class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        if len(s) < k or len(s) <= 1: 
            return s 
        
        n = len(s) 
        
        # fixme: push the first k - 1 elements 
        stack_count = deque([1])  
        # stack_res = deque([s[0]])  
        stack_res = [] 
        stack_res.append(s[0]) 
        s_list = list(s) 
        i = 1 
        # i = k # fixme: check 
        while i != n: 
            if len(stack_count) == 0: 
                stack_count.append(1) 
                stack_res.append(s_list[i])
            
            elif s_list[i] != stack_res[-1]: 
                stack_count.append(1) 
                stack_res.append(s_list[i])
            elif s[i] == stack_res[-1] and stack_count[-1] + 1 < k: 
                stack_res.append(s_list[i]) 
                stack_count[-1] += 1 
                 
            else:
                stack_count.pop()  
                # pop_num = k - 1 
                del stack_res[-(k-1):]
            i += 1 
        
        return ''.join(list(stack_res)) 
            
        
languages = ['Python', 'Java', 'C++', 'Ruby', 'C']

from collections import deque 
languages = deque(languages)
print(languages)
# del languages[-3:]
# remove and return the last item
# print('When index is not passed:') 
# print('Return Value:', languages.pop())
languages = ['Python', 'Java', 'C++', 'Ruby', 'C']
print('original languages:', languages) 
del languages[-3:] 
print('delete the last 3 elements:', languages)<jupyter_output>original languages: ['Python', 'Java', 'C++', 'Ruby', 'C']
delete the last 3 elements: ['Python', 'Java']<jupyter_text>28. Implement strStr() [28. Implement strStr()](https://leetcode.com/problems/implement-strstr/)<jupyter_code>class Solution:
    def strStr(self, haystack: str, needle: str) -> int: 
        if len(haystack) < len(needle): 
            return -1 
        
        for i in range(len(haystack) - len(needle) + 1):
            match = True 
            for j in range(len(needle)): 
                if haystack[i+j] != needle[j]: 
                    match = False 
            if match == True: 
                return i
        
        return -1<jupyter_output><empty_output><jupyter_text>344. Reverse String [344. Reverse String](https://leetcode.com/problems/reverse-string/)<jupyter_code>class Solution:
    def reverseString(self, s) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        n = len(s) 
        self.helper(s, 0, n - 1) 
        
    def helper(self, s, i, j): 
        # base case 
        if i >= j: 
            return 
        s[i], s[j] = s[j], s[i] 
        self.helper(s, i+1, j-1) 
class Solution:
    def reverseString(self, s) -> None:
        """
        Do not return anything, modify s in-place instead.
        """ 
        """
        ["h","e","l","o"] 
                  i 
              j 
        
        """
        n = len(s) 
        if n <= 1: 
            return s  
        
        i = 0 
        j = n - 1 
        while i <= j: 
            s[i], s[j] = s[j], s[i] 
            i += 1 
            j -= 1<jupyter_output><empty_output><jupyter_text>151. Reverse Words in a String[151. Reverse Words in a String](https://leetcode.com/problems/reverse-words-in-a-string/)<jupyter_code>class Solution:
    def reverseWords(self, s: str) -> str: 
        """
        the sky is blue --> eht yks si eulb --> blue is sky the  
        
        preprocessing to get rid of the additional spaces. 
        reverse each single word  
        the sky is blue
                   i 
                      j 
        reverse the whole sentence 
        
        """
        
        # preprocessing 
        arr = s.split() 
        arr = " ".join(arr) 
        arr = list(arr) 
        
        # reverse single word 
        n = len(arr) 
        i = 0 
        j = 0  
        
        while j < n: 
            # move j to the end of the word 
            while j < n and arr[j] != " ": 
                j += 1 
            # reverse the word arr[i:j]  
            self.reverse(arr, i, j - 1) 
            
            # move i  
            i = j + 1 
            j = i 
        
        self.reverse(arr, 0, n - 1) 
        return "".join(arr)
        
            
            
    def reverse(self, s, i, j): 
        while i < j: 
            s[i], s[j] = s[j], s[i] 
            i += 1 
            j -= 1 
        
s = "  the sky  is blue"
# s_list = list(s) 
s = list(" ".join(s.split()))[::-1]
s
s = "  the sky  is blue"
s_list = s.split()
print(s_list)
# s_list_join = ' '.join(s_list) 
# list(s_list_join)<jupyter_output>['the', 'sky', 'is', 'blue']<jupyter_text>186. Reverse Words in a String II [186. Reverse Words in a String II](https://leetcode.com/problems/reverse-words-in-a-string-ii/)<jupyter_code>class Solution:
    def reverseWords(self, s) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        # reverse the whole list 
        n = len(s) 
        self.reverse(s, 0, n - 1) 
        
        start = 0 
        end = 0 
        # reverse each word 
        while end < n: 
            while end < n and s[end] != ' ': 
                end += 1 
            self.reverse(s, start, end - 1) 
            
            start = end + 1 
            end = start 
        
    def reverse(self, s, start, end): 
        while start < end: 
            s[start], s[end] = s[end], s[start] 
            start += 1 
            end -= 1<jupyter_output><empty_output><jupyter_text>189. Rotate Array [189. Rotate Array](https://leetcode.com/problems/rotate-array/)<jupyter_code>class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """ 
        """
        [1,2,3,4,5,6,7], k = 3  -->> [5,6,7,1,2,3,4]   k + n * z, where z \in Z  
        Derive the fomula: m = n - k % n 
        nums[0, m), nums[m, n] 
        [1,2,3,4], [5,6,7] --> 4 3 2 1; 7 6 5 --> 5 6 7 1 2 3 4 
        
        
        """
        n = len(nums) 
        # if n <= 1: 
        #     return 
        # find the pivot m 
        m = n - k % n 
        # reverse nums[0, m) 
        self.reverse(nums, 0, m - 1) 
        # reverse nums[m, n] 
        self.reverse(nums, m, n-1) 
        # reverse nums  
        self.reverse(nums, 0, n-1) 
        
        
    def reverse(self, s, i, j): 
        while i < j: 
            s[i], s[j] = s[j], s[i] 
            i += 1 
            j -= 1<jupyter_output><empty_output><jupyter_text>125. Valid Palindrome [125. Valid Palindrome](https://leetcode.com/problems/valid-palindrome/)<jupyter_code>class Solution:
    def isPalindrome(self, s: str) -> bool: 
        
        n = len(s) 
        
        i = 0 
        j = n - 1 
        
        while i < j: 
            # move i and j to a letter or number 
            # notice: the i < j should be consistent with while. 
            while i < j and not s[i].isalnum(): 
                i += 1 
            while i < j and not s[j].isalnum():
                j -= 1 
            
            if s[i].lower() != s[j].lower():
                return False
            
            i += 1
            j -= 1
        
        return True<jupyter_output><empty_output><jupyter_text>443. String Compression[443. String Compression](https://leetcode.com/problems/string-compression/)<jupyter_code>class Solution:
    def compress(self, chars) -> int:
        """
        [0, i): processed and kept 
        [i, j): garbage 
        j: processing 
        [j, j'): current chunk 
        a 2 a b b b  c c c  d e 
        i 
        j 
              j' 
        
        """
        
        if len(chars) == 1: 
            return 1 
        
        n = len(chars) 
        i = 0 
        j = 0 
        jp = 0
        
        while j < n: 
            # move j' to next different 
            while jp < n and chars[jp] == chars[j]: 
                jp += 1 
            count = jp - j 
            
#             chars[i] = chars[j] 
#             i += 1 
#             if count > 1: 
#                 # chars[i] = str(count) 
#                 for s in str(count): 
#                     chars[i] = s
#                     i += 1 
            
#             j = jp 
            
            if count == 1: 
                chars[i] = chars[j] 
                i += 1 
                j = jp 
                # j += 1 
            else: 
                chars[i] = chars[j] 
                i += 1 
                for s in str(count): 
                    chars[i] = s
                    i += 1 
                
                # chars[i+1] = str(count) # fixme split to single digit string 
                
                j = jp 
                # i += 2 
        return i<jupyter_output><empty_output><jupyter_text>Sliding window   3. Longest Substring Without Repeating Characters [3. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)   fix right<jupyter_code>class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int: 
        n = len(s)
        if len(s) <= 1: 
            return len(s) 
        
        l = 0 
        res = 1 
        hashset = set() 
        for r in range(n): 
            # if invalid, make it valid. 
            while s[r] in hashset: 
                hashset.remove(s[l]) 
                l += 1 
            
            hashset.add(s[r]) 
            res = max(res, r - l + 1)
        
        return res 
    
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """
        sliding window: 
        i: start index 
        j: end index 
        
        set: letters in [i, j] 
        
        a b c a b c b b 
        i 
        j 
        
        set: {a, b, c, }
        
        """
        if len(s) <= 1: 
            return len(s) 
        
        n = len(s) 
        i = 0 
        j = 0 
        res = 0 
        hashset = set([s[0]])  
        
        while j < n - 1: 
            if s[j+1] not in hashset: 
                hashset.add(s[j+1])
                j += 1  
                res = max(res, j-i+1)
            else: 
                hashset.remove(s[i]) 
                i += 1 
        return res<jupyter_output><empty_output><jupyter_text>438. Find All Anagrams in a String[438. Find All Anagrams in a String](https://leetcode.com/problems/find-all-anagrams-in-a-string/)<jupyter_code>class Solution:
    def findAnagrams(self, s: str, p: str):
        """
        i: start 
        j: end 
        [i, j]: current substring 
        
        hashmap: element: count for [i, j] 
        c b a e b a b a c d 
        i 
            j 
        
        """
        
        if len(s) < len(p): 
            return [] 
        
        # counter dict 
        p_count = Counter(p)  
        
        n = len(s)
        i = 0 
        j = len(p) - 1 
        # hashmap = {} 
        # hashmap = dict() 
        hashmap = defaultdict(int) 
        # intialize the hashmap 
        for idx in range(j + 1): 
            hashmap[s[idx]] += 1 
        res = [] 
        
        while j < n:  
            if self.is_same_map(p_count, hashmap):  
                res.append(i) 
            hashmap[s[i]] -= 1  # notice 
            i += 1 
            j += 1  
            if j < n: 
                hashmap[s[j]] += 1 
        return res 
                
    def is_same_map(self, count, hashmap): 
        for k, v in count.items(): 
            if hashmap[k] != v: 
                return False 
        return True 
        
# default dict 
dic = {1: 'k', 2: 'k'} 
print(dic) 
# dic[3]
ele = dic.get(3, 0) 
print(ele) 
dic[3] = dic.get(3, 0) + 1 
print(dic[3])

# default dict 
from collections import defaultdict 
d = defaultdict(int)  
# d = dict() 
# d = {} 
d[0] = 1 
d[1] = 1  
print(d)
print(d[4]) 



import collections  
p = 'cicitttt' 
myDictP = collections.Counter(p) 
print(myDictP) 
# for i in myDictP.elements(): 
#     print(i)
print(myDictP['t'])
print(myDictP.get('t', 0))
print(myDictP.get('e', 0))<jupyter_output>Counter({'t': 4, 'c': 2, 'i': 2})
4
4
0<jupyter_text>485. Max Consecutive Ones[485. Max Consecutive Ones](https://leetcode.com/problems/max-consecutive-ones/)<jupyter_code>class Solution:
    def findMaxConsecutiveOnes(self, nums) -> int: 
        """
        count for 1s 
        
        
        """
        
        n = len(nums)  
        count = 0 
        res = 0 
        for idx, item in enumerate(nums): 
            if item == 0: 
                count = 0 
            else: 
                count += 1 
                res = max(count, res)

        return res<jupyter_output><empty_output><jupyter_text>487. Max Consecutive Ones II[487. Max Consecutive Ones II](https://leetcode.com/problems/max-consecutive-ones-ii/)<jupyter_code>class Solution:
    def findMaxConsecutiveOnes(self, nums) -> int: 
        """
        sliding window: 
        [i, j]: current valid subarray 
        count: current length 
        num_zeros: # of 0s in [i, j]
        1 0 1 1 0 
        i 
          j 
        
        num_zeros 
        res = max(j-i+1, res)
        
        """ 
        
        if len(nums) <= 1: 
            return len(nums) 
        
        n = len(nums) 
        i = 0 
        j = 0  
        res = 0 
        num_zeros = 0 
        
        while j < n: 
            if nums[j] == 1: 
                count = j - i + 1
                res = max(res, count) 
            else: 
                num_zeros += 1 
                if num_zeros <= 1: 
                    count = j - i + 1
                    res = max(res, count) 
                else: 
                    # invalid 
                    while i <= j and nums[i] != 0: 
                        i += 1 
                    i += 1 
            j += 1 
                    
        return res<jupyter_output><empty_output><jupyter_text>1004. Max Consecutive Ones III[1004. Max Consecutive Ones III](https://leetcode.com/problems/max-consecutive-ones-iii/)   key to understand two pointers and sliding window try every start point. arr = [1, 1, 0, 0, 1, 1, 1[l, r): spend all k flips. or less thank k flips.<jupyter_code>class Solution:
    def longestOnes(self, nums, k: int) -> int:
        
        if len(nums) <= k: 
            return len(nums) 
        
        n = len(nums) 
        i = 0 
        j = 0  
        res = 0
        num_zeros = 0 
        
        while j < n: 
            if nums[j] == 1: 
                count = j - i + 1
                res = max(res, count) 
            else: 
                num_zeros += 1 
                if num_zeros <= k: 
                    count = j - i + 1
                    res = max(res, count) 
                else: 
                    # invalid 
                    while i <= j and nums[i] != 0: 
                        i += 1 
                    i += 1 
            j += 1 
                    
        return res 
class Solution:
    def longestOnes(self, nums, k: int) -> int: 
        """
        sliding window: 
        fix left, expand right 
        
        increment left, maintain k. 
        
        """
        
        if len(nums) <= k: 
            return len(nums) 
        
        n = len(nums) 
        r = 0 
        res = 0 
        for l in range(n): 
            # expand right 
            # teminate condition: r >= n 
            # or k <= 0 
            while r < n and (nums[r] == 1 or (nums[r] == 0 and k > 0)):   
                if nums[r] == 0: 
                    k -= 1 
                r += 1 
            
            res = max(res, r - l) 
            
            if nums[l] == 0: 
                k += 1 
        return res<jupyter_output><empty_output><jupyter_text>fix right<jupyter_code>class Solution:
    def longestOnes(self, nums, k: int) -> int: 
        n = len(nums)
        if len(nums) <= k: 
            return len(nums) 
        
        l = 0 
        res = 0 
        for r in range(n): 
            
            if nums[r] == 0: 
                k -= 1 
                
            # if invalid, make it valid  
            if k < 0: 
                while nums[l] != 0: 
                    l += 1 
                l += 1 
                k += 1 
            
#             while l < n and k < 0: 
#                 if nums[l] == 0: 
#                     k += 1 
#                 l += 1 
            
            res = max(res, r - l + 1) 
        return res<jupyter_output><empty_output><jupyter_text>239. Sliding Window Maximum[239. Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/)  Window data structure: - add - remove - max ![image.png](attachment:image.png) Deque: the left most element is the greatest. Deque information: - max in current window  - potential max(s) in subsequent windows How we update the deque as we move the window? - if the max (first element in the deque) is out of the range, we remove it, and thus the second greatest element is the max in current window. - if the max is within the range, then it is the max, and we simply append it to the result.  ```         window                max         deque [1]  3  -1  -3  5  3  6  7      1         [1][1   3] -1  -3  5  3  6  7      3         [3][1   3  -1] -3  5  3  6  7      3         [3, -1]   -1 is the potintial max 1   [3  -1  -3]  5  3  6  7      3         [3, -1, -3] 1    3  [-1  -3  5]  3  6  7      3        [5] 1    3  -1  [-3  5  3]  6  7      3        [5, 3]  1    3  -1  -3  [5  3  6]  7      3        [6]  ``` Another example: ```[1    3  -1]  3  2  1  1  7      3        [3, -1]   1    [3  -1  3]  2  1  1  7      3        [3, -1]  1    3  -1  3  [2  1  1]  7      3        [6]  ```<jupyter_code>class Solution:
    def maxSlidingWindow(self, nums, k: int):
        n = len(nums) 
        window_size = n - k + 1 
        res = [0 for _ in range(window_size)] 
        q = deque() 
        
        for idx, item in enumerate(nums): 
            # update q: check if current max is out of range  
            left_boundry = idx - k + 1
            if q and q[0] < left_boundry: 
                q.popleft() 
            # update q: push new element to q. 
            # note: potential max for subsequent windows, order? 
            while q and nums[q[-1]] <= item:  # note has to be <= 
            # while q and nums[q[-1]] < item:  # note has to be <= 
                q.pop()  
            q.append(idx) 
            
            # append max to result 
            if idx >= k - 1: 
                res[idx - k + 1] = nums[q[0]]   # note append the element rather than the index 
        
        return res<jupyter_output><empty_output><jupyter_text>295. Find Median from Data Stream[295. Find Median from Data Stream](https://leetcode.com/problems/find-median-from-data-stream/)   Naive approach We call the sort function every time. Time: O(nlog(n))<jupyter_code>class MedianFinder:

    def __init__(self):
        self.data = []  
        self.length = 0 
        

    def addNum(self, num: int) -> None: 
        self.data.append(num) 
        self.length = len(self.data)
        

    def findMedian(self) -> float:
        self.data.sort() 
        if self.length % 2 == 0: 
            median_idx_1 = self.length // 2 
            median_idx_2 = median_idx_1 - 1  
            res = self.data[median_idx_1] + self.data[median_idx_2]
            return res / 2 
        else: 
            median_idx = (self.length - 1) // 2 
            return self.data[median_idx]<jupyter_output><empty_output><jupyter_text>two-heap time: $log(logn)$ - When we add a number, we need to perform several $log(n)$ operation over the two heaps. - When we call $findMedian$, it only takes O(n).  [41, 35, 62, 5, 97, 108] Add num to max-heap lo. Since lo received a new element, we must do a balancing step for hi. So remove the largest element from lo and offer it to hi.lo.push(num);                                    // Add to max heaphi.push(lo.top());                               // balancing steplo.pop();Since we do not know the new element, we simply add it to the lower half. Then, we the top element to the higher half, and the arry becomes good again. [108, 97, 62], [41, 35, 5]```num = 34 lo.push(num);   lo: [41, 34, 35, 5]hi.push(lo.pop());   high: [108, 97, 62, 41], low: [35, 34, 5]  adjust length: if len(high) > len(low):     low.push(hi.pop())    high: [108, 97, 62], low: [41, 35, 34, 5] Median is: 41 num = 99 lo.push(num);   lo: [99, 41, 34, 35, 5]hi.push(lo.pop());   high: [108, 97, 99, 62], low: [41, 35, 34, 5] Median: (62+41)/2 ```<jupyter_code>from heapq import heappush, heappop, heapify

class MedianFinder:

    def __init__(self):
        self.data_high = []
        self.data_low = []  
        
#         self.length = 0 
        self.median = 0 
        

    def addNum(self, num: int) -> None: 
        heappush(self.data_low, -num)  # max heap, need minus sign 
        heappush(self.data_high, -heappop(self.data_low))  
        # compact version: 
#         heappush(self.data_high, -heappushpop(self.data_low, -num))  

        
        length_high = len(self.data_high)
        length_low = len(self.data_low)
#         self.length = length_low + length_high 
        
        if length_high > length_low: 
            heappush(self.data_low, -heappop(self.data_high))  
            self.median = -self.data_low[0] 
        else: 
            self.median = (-self.data_low[0] + self.data_high[0]) / 2  
            

    def findMedian(self) -> float:
        return self.median 
from heapq import heappush, heappop, heapify, heappushpop
arr = [41, 35, 62, 5, 97] 
print("arr original:", arr)
heappush(arr, 1)
print("arr heap add 100:", arr)
print(arr[0], heappop(arr))
print(arr)

from heapq import heappush, heappop, heapify, heappushpop
arr = [] 
print(arr)
a = [3, 4, 5]
b = ['d', 4]

ele = (1, a)
heappush(arr, ele) 
print(arr) 
ele = (33, a)

heappush(arr, ele) 
print(arr) 


# By default Min Heap is implemented by this class. 
# But we multiply each value by -1 so that we can use it as MaxHeap.
# why: 

arr = [-5, -6, -7] 
print("arr original:", arr) 
heapify(arr) 
print("arr after heapify:", arr) 

heappushpop(arr, -1) 
print("arr heap add 1:", arr)<jupyter_output>arr original: [-5, -6, -7]
arr after heapify: [-7, -6, -5]
arr heap add 1: [-6, -1, -5]<jupyter_text>480. Sliding Window Median[480. Sliding Window Median](https://leetcode.com/problems/sliding-window-median/)  Is there a data-structure out there that we can use (in one or more quantities) to obtain the median element extremely fast, say O(1) time while having the ability to perform the other operations fairly efficiently as well?two-heap: heaps: maintain the median of current window. How we update heaps as we move the window? - remove the outdated element from heaps. - add new to the heaps. for loop: 1. update heaps for current window 2. get median   76. Minimum Window Substring[76. Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/) Use sliding window and hashmap. ```s = "ADOBECODEBANC", t = "ABC""ADOBECODEBANC"[i, j]: current string hashmap: counter for [i, j] update rule: c a b w e f g e w c  w  a  e   f   g   c   f0 1 2 3 4 5 6 7 8 9 10  11 12  13  14 15  16  "cae"Output:"aefgc" [11, 15] Expected:"cwae" [9, 12] ```<jupyter_code>class Solution:
    def minWindow(self, s: str, t: str) -> str:
        n = len(s)
        if n < len(t):
            return ''

        res_idx = float('inf'), None, None
        t_count = Counter(t)
        hashmap = defaultdict(int)
        l = 0
        for r, ch in enumerate(s):
            if ch in t_count:
                hashmap[ch] += 1

                if self.is_contain(t_count, hashmap):
                    if r - l + 1 < res_idx[0]:
                        res_idx = r - l + 1, l, r

                    while l <= r:
                        if self.is_contain(t_count, hashmap):
                            if r - l + 1 < res_idx[0]:
                                res_idx = r - l + 1, l, r

                            # res_idx = l - r + 1, l, r
                            # !!!!!!!!!!!!!! 
                            hashmap[s[l]] -= 1  # remove current l
                            l += 1
                        else:
                            break

        if res_idx[1] == None:
            return ''
        else:
            return s[res_idx[1]:res_idx[2] + 1]

        
        
    def is_contain(self, t_count, hashmap): 
        for k, v in t_count.items(): 
            if hashmap[k] < v: 
                return False 
        return True 
# v1 wrong .... 
from collections import Counter, defaultdict
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        n = len(s) 
        if n < len(t): 
            return '' 
        
        res_idx_a, res_idx_b = None, None  
        t_count = Counter(t) 
        hashmap = defaultdict(int) 
        l = 0 
        for r, ch in enumerate(s): 
            if ch in t_count: 
                hashmap[ch] += 1 
            
                if self.is_contain(t_count, hashmap): 
                    res_idx_a, res_idx_b = l, r 
                    print(hashmap)

                    while l <= r and self.is_contain(t_count, hashmap): 
                        res_idx_a, res_idx_b = l, r 
                        l += 1  
                        if s[l] in t_count: 
                            hashmap[s[l]] -= 1 
                    
        
        if res_idx_a == None: 
            return '' 
        else: 
            return s[res_idx_a:res_idx_b + 1] 
    
    def is_contain(self, t_count, hashmap): 
        for k, v in t_count.items(): 
            if hashmap[k] < v: 
                return False 
        return True 

s = "ABAACBAB" 
t = "ABC"
s = "ADOBECODEBANC" 
t = "ABC"
a = Solution() 
a.minWindow(s, t)<jupyter_output>defaultdict(<class 'int'>, {'A': 1, 'B': 1, 'C': 1})
defaultdict(<class 'int'>, {'A': 1, 'B': 1, 'C': 1})
defaultdict(<class 'int'>, {'A': 2, 'B': 1, 'C': 1})<jupyter_text>42. Trapping Rain Water[42 leetcode](https://leetcode.com/problems/trapping-rain-water/)  naive solution for each index, we look to the left and right, find the right_max and left_max, caulculate min(left_max, right_max) - cur_height.   407. Trapping Rain Water II [407. Trapping Rain Water II ](https://leetcode.com/problems/trapping-rain-water-ii/)  84. Largest Rectangle in Histogram [84. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)  Naive solution<jupyter_code>class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int: 
        res = 0 
        n = len(heights) 
        for i, height in enumerate(heights): 
            # determine left border  
            r = i 
            l = i 
            while l >= 0 and l <= n -1 and height <= heights[l]: 
                l -= 1 
            
            # determine right border
            while r >= 0 and r <= n -1 and height <= heights[r]: 
                r += 1 
            
            # calculate and update area 
            cur_area = height * (r - l - 1)
            res = max(res, cur_area)
        
        return res<jupyter_output><empty_output><jupyter_text>![image.png](attachment:image.png) borders of left, right, and bottom can be easily determined. In an ascending order, we can extend our right border to the right.<jupyter_code>class Solution:
    def largestRectangleArea(self, heights) -> int: 
        res = 0 
        heights.insert(0, -1) 
        heights.append(-1) 
        n = len(heights) 
        stack = deque([(0, heights[0])]) 
        p = 1 
        
        while p < n: 
            if stack and stack[-1][1] > heights[p]:  
                idx, h = stack.pop() 
                # determine the left and right borders 
                l = stack[-1][0] + 1 
                r = p - 1 
                # calculate and update the area 
                length = r - l + 1  
                cur_area = length * h 
                res = max(res, cur_area)
                
            else: 
                # ascending order 
                stack.append((p, heights[p])) 
                p += 1 
        
        return res<jupyter_output><empty_output><jupyter_text>85. Maximal Rectangle[85. Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/)  This is an extension of 84.  ![image.png](attachment:image.png)  deep copy and shallow copy in python [How to Copy List of Lists in Python (Shallow vs Deep)?](https://blog.finxter.com/copy-list-of-lists-in-python-shallow-vs-deep/)<jupyter_code>arr = [1, 1, 2, 3] 
matrix = [arr.copy(), arr.copy(), arr.copy()] 
print(matrix) 
mat = [arr, arr, arr]  
print(mat) 
arr[1] = 3333
print(matrix) 
print(mat) 

matrix_copy = matrix.copy() 
print('matrix.copy() ', matrix_copy) 
matrix[1][1] = 333333 
print('matrix.copy() modified matrix', matrix_copy) 
matrix_copy[1][1] = 'abb' 
print('matrix after modified matrix_copy', matrix) 

from copy import deepcopy
matrix_deep = deepcopy(matrix)  
print('deep copy: ', matrix_deep) 
matrix[1][1] = 'ccc'
matrix_copy[0][1] = 'ccc'  
print('deep copy after modification: ', matrix_deep) 

class Solution:
    def maximalRectangle(self, matrix) -> int: 
        
        res = 0 
        
        # generate histogram H for each row 
        hist_matrix = self.generate_histogram(matrix) 
        
        # for row in hist_matrix: 
        #     print(row)
        
        # test_hist = hist_matrix[2] 
        # hist = test_hist 
        # cur_max = self.largest_rectangle(hist) 
        # print('test hist', cur_max)    
        
        # For each row of H, calculate its largest rectangle.  update the max 
        for hist in hist_matrix: 
            cur_max = self.largest_rectangle(hist) 
            res = max(res, cur_max) 
        
        return res 
    
        
    def largest_rectangle(self, hist): 
        from collections import deque 
        res = 0 
        
        hist.insert(0, -1) 
        hist.append(-1) 
        n = len(hist) 
        stack = deque([(0, hist[0])])  
        p = 1 
        while p < n: 
            if stack and stack[-1][1] > hist[p]: 
                idx, height = stack.pop() 
                # determine the left and right border  
                l = stack[-1][0] + 1 
                r = p - 1 
                length = r - l + 1 
                # calculate current area and update res 
                cur_area = length * height 
                res = max(res, cur_area) 
                
            else: 
                stack.append((p, hist[p])) 
                p += 1 
        
        
        return res 
    
    def generate_histogram(self, matrix): 
        import copy 
        hists = copy.deepcopy(matrix)  
        size_row = len(hists) 
        size_col = len(hists[0])  
        
        # first row to int 
        for c in range(size_col): 
            hists[0][c] = int(hists[0][c]) 
            
        # remaining 
        for r in range(1, size_row): 
            for c in range(size_col): 
                cur_num = int(hists[r][c])
                if cur_num == 1: 
                    hists[r][c] = 1 + hists[r-1][c] 
                else:  
                    hists[r][c] = 0 
        
        return hists<jupyter_output><empty_output><jupyter_text>221. Maximal Square[221. Maximal Square](https://leetcode.com/problems/maximal-square/)<jupyter_code>class Solution:
    def maximalSquare(self, matrix) -> int: 
        
        res = 0 
        # generate histogram 
        hist_matrix = self.generate_histogram(matrix) 
        
        for row in hist_matrix: 
            cur_max = self.largest_rectangle(row) 
            res = max(res, cur_max) 
        
        return res 
        
    def generate_histogram(self, matrix): 
        import copy 
        hists = copy.deepcopy(matrix) 
        
        size_row = len(hists) 
        size_col = len(hists[0]) 
        for c in range(size_col): 
            hists[0][c] = int(hists[0][c]) 
            
        for r in range(1, size_row): 
            for c in range(size_col): 
                cur_num = int(hists[r][c]) 
                if cur_num == 1: 
                    hists[r][c] = hists[r-1][c] + 1 
                else: 
                    hists[r][c] = 0 
        
        return hists 
        
        
    def largest_rectangle(self, hist): 
        from collections import deque 
        hist.insert(0, -1) 
        hist.append(-1)  
        n = len(hist)
        stack = deque([(0, hist[0])]) 
        p = 1 
        res = 0 
        while p < n: 
            if stack and stack[-1][1] > hist[p]: 
                idx, height = stack.pop() 
                # determine the left and right border 
                r = p - 1 
                l = stack[-1][0] + 1 
                length = r - l + 1 
                # calculate the area and update res 
                if length >= height: 
                    cur_area = height * height 
                else: 
                    cur_area = length * length 
                res = max(res, cur_area) 
                
            else: 
                stack.append((p, hist[p])) 
                p += 1 
        return res<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11316686374069694, 'fraction_numerical': 0.02251280981196819, 'mean_word_length': 1.3236720181014976, 'pattern_counts': {'":': 1, '<': 193, '<?xml version=': 0, '>': 169, 'https://': 28, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '29', 'dir': 'jupyter-structured-clean-dedup', 'id': '521575', 'license': 'MIT', 'n_tokens_mistral': 15017, 'n_tokens_neox': 13395, 'n_words': 3958, 'path': 'String.ipynb', 'repo_name': 'ling-k/leetcode', 'size': '43131'}