On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).


Examples:
Input: N = 1, K = 1
Output: 0

Input: N = 2, K = 1
Output: 0

Input: N = 2, K = 2
Output: 1

Input: N = 4, K = 5
Output: 1

Explanation:
row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001


Note:


       N will be an integer in the range [1, 30].
       K will be an integer in the range [1, 2^(N-1)].

Difficulty: interview

Starter code:

class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
        

Solutions:
class Solution:
     def maxChunksToSorted(self, arr):
         """
         :type arr: List[int]
         :rtype: int
         """
         res = 0
         temp = sorted(arr)
         sum1, sum2 = 0, 0
         for i in range(0,len(arr)):
             sum1 += arr[i]
             sum2 += temp[i]
             if(sum1 == sum2):
                 res += 1
         return res


import collections
 class Solution:
     '''
     >>> sol = Solution()
     >>> sol.maxChunksToSorted([2,1,3,4,4])
     4
     >>> sol.maxChunksToSorted([4, 3, 2, 1, 0])
     1
     >>> sol.maxChunksToSorted([0, 1])
     2
     '''
     def maxChunksToSorted(self, arr):
         """
         :type arr: List[int]
         :rtype: int
         """
         counter = collections.Counter()
         arrtup = []
         for num in arr:
             counter[num] += 1
             arrtup.append((num, counter[num]))
         arrsorted = sorted(arrtup)
         ans, maxnum = 0, (0, 0)
         for x, y in zip(arrtup, arrsorted):
             maxnum = max(maxnum, x)
             if maxnum == y:
                 ans += 1
 
         return ans
 


from itertools import accumulate
 
 
 class Solution:
     def maxChunksToSorted(self, arr):
         right_min = list(accumulate(arr[::-1], lambda m, a: min(m, a)))[::-1]
         right_min = right_min[1:] + [float('inf')]
         left_max = list(accumulate(arr, lambda m, a: max(m, a)))
         return sum(1 for x, y in zip(left_max, right_min) if x <= y)

class Solution:
     def maxChunksToSorted(self, arr):
         """
         :type arr: List[int]
         :rtype: int
         """
         mxvs, mnvs = [-1] * len(arr), [10**8 + 1] * len(arr)
         for i, v in enumerate(arr):
             if i == 0:
                 mxvs[i] = arr[i]
             else:
                 mxvs[i] = max(mxvs[i-1], v)
         for i in range(len(arr))[::-1]:
             if i == len(arr) - 1:
                 mnvs[i] = arr[i]
             else:
                 mnvs[i] = min(mnvs[i+1], arr[i])
         
         cnt = 0
         for i in range(len(arr)):
             if mxvs[i] <= (mnvs[i+1] if i < len(arr) - 1 else 10**8 + 1):
                 cnt += 1
         return cnt


class Solution:
     def maxChunksToSorted(self, arr):
         """
         :type arr: List[int]
         :rtype: int
         """
         stack = []
         for num in arr:
             if len(stack)==0 or stack[-1] <= num:
                 stack.append(num)
             else:
                 maxnum = stack.pop()
                 while len(stack)>0 and stack[-1]>num:
                     stack.pop()
                 stack.append(maxnum)
         return len(stack)

class Solution:
     def maxChunksToSorted(self, arr):
         """
         :type arr: List[int]
         :rtype: int
         """
         arr_index=sorted(list(range(len(arr))), key=arr.__getitem__)
         ans = ma = 0
         for i, x in enumerate(arr_index):
             ma = max(ma, x)
             if ma == i: ans += 1
         return ans


class Solution:
     def maxChunksToSorted(self, arr):
         """
         :type arr: List[int]
         :rtype: int
         """
         stack = []
         for e in reversed(arr):
             min_so_far = e
             while True:
                 if len(stack) == 0 or e <= stack[-1][0]:
                     stack.append([min_so_far, e])
                     break
                 if e > stack[-1][1]:
                     min_so_far = min(min_so_far, stack.pop()[0])
                 else:
                     stack[-1][0] = min(min_so_far, stack[-1][0])
                     break
                     
         return len(stack)

import math
 class Solution:
     def maxChunksToSorted(self, arr):
         count = 0
 
         minVal = [0] * len(arr)
         minSofar = math.inf
         for idx in reversed(range(len(arr))):
             minVal[idx] = min(minSofar, arr[idx])
             minSofar = minVal[idx]
 
         maxSofar = -math.inf
         for idx in range(len(arr)):
             maxSofar = max(maxSofar, arr[idx])
             if idx == len(arr) - 1:
                 count += 1
             elif maxSofar <= minVal[idx+1]:
                 count+=1
 
 
         return count

class Solution:
     def maxChunksToSorted(self, arr):
         """
         :type arr: List[int]
         :rtype: int
         """
         
         sarr = sorted(arr)
         table = {}
         for i, n in enumerate(sarr):
             if n not in table:
                 table[n] = [i, i]
             else:
                 table[n][1] += 1
         
         c = -1
         chunks = 0
         for i, n in enumerate(arr):
             c = max(c, table[n][0])
             if table[n][0] < table[n][1]:
                 table[n][0] += 1
             if c == i:
                 chunks += 1
         return chunks

class Solution:
     def maxChunksToSorted(self, arr):
         """
         :type arr: List[int]
         :rtype: int
         """
         
         if arr is None:
             return 0
         
         if len(arr) < 2:
             return len(arr)
         
         # Preprocess suffix min
         suffix_min = [float('inf')] * len(arr)
         suffix_min[-1] = arr[-1]
         suffix_max = [float('-inf')] * len(arr)
         suffix_max[-1] = arr[-1]
         for index in range(len(arr) - 2, -1, -1):
             suffix_min[index] = min(arr[index + 1], suffix_min[index + 1])
             suffix_max[index] = max(arr[index + 1], suffix_max[index + 1])
         
         index = 0
         chunk_count = 0
         
         print(suffix_min)
         
         while index < len(arr):
             chunk_count += 1
             if arr[index] > suffix_min[index]:
                 j = index
                 running_max = arr[j]
                 while j < len(arr) and running_max > suffix_min[j]:
                     running_max = max(running_max, arr[j])
                     j += 1
                 # Now j is at the index where all the following elements are greater than or equal to arr[j]
                 index = j + 1
             else:
                 index += 1
         
         return chunk_count

class Solution:
     def maxChunksToSorted(self, arr):
         """
         :type arr: List[int]
         :rtype: int
         """
         t = arr[0]
         left_max = []
         
         for x in arr:
             t = max(t, x)
             left_max.append(t)
             
         t = arr[-1]
         right_min = []
         for i in range(len(arr) - 1, -1, -1):
             t = min(arr[i], t)
             right_min.append(t)
         
         count = 1
         
         # print(right_min) 
         # print(left_max)
 
         for i in range(0, len(arr) - 1):
             if left_max[i] <= right_min[len(arr) - i -2]:
                 count += 1
                 
         return count

class Solution:
     def maxChunksToSorted(self, arr):
         """
         :type arr: List[int]
         :rtype: int
         """
         dict = {}           #存储排序后的每个元素的位置
         sortedArr = sorted(arr)
         for i in range(len(sortedArr)):
             if(sortedArr[i] not in dict):
                 dict[sortedArr[i]] = [i]
             else:
                 dict[sortedArr[i]].append(i)
 
         position = []       #存储每个元素相对排序后的数组应该移动的距离
         for i, val in enumerate(arr):
             position.append(dict[val][0] - i)
             dict[val].pop(0)           #可能有重复元素，那么在使用完一个元素后，就把使用过的元素位置删除
 
 
         maxNum = 0
         i = 0
         ifPlusMinus = 0         #用于判断是否需要移动0位置的数包含在需要左右都移动的数之间，如[4,3,2,1,0]
                                 #该数组中2是不移动的，但因为4，3和1，0都要移动，所以不能单独另算
         maxIdealPosition = 0   #用于存储要移动子数组中左侧元素向右移动的最大距离
         while(i < len(position)):
             if(position[i] == 0 and ifPlusMinus == 0):
                 maxNum += 1
                 i += 1
             elif(position[i] > 0 and ifPlusMinus == 0):     #要移动的子数组中处于"最左面最开始位置"需要"右移"的数，它一定会匹配到最右侧position是负数的数
                 ifPlusMinus = 1
                 maxIdealPosition = i + position[i]
                 i += 1
             elif(position[i] >= 0 and ifPlusMinus == 1):    #处于要移动子数组的"中间位置"
                 if(i + position[i] > maxIdealPosition):     #查看是否需要更新maxIdealPosition值，如arr=[1,2,0,3],position=[1,1,-2,0]
                     maxIdealPosition = i + position[i]
                 i += 1
             elif(position[i] <0 and ifPlusMinus == 1):      #处于要移动子数组的"末尾位置"
                 if(i < len(position) - 1):
                     if(position[i+1] < 0):
                         i += 1
                     elif(position[i+1] >= 0):
                         if(i == maxIdealPosition):        #判断是否已扫描到要移动数组中需要右移数组的最大理想位置
                             maxNum += 1
                             ifPlusMinus = 0
                             maxIdealPosition = 0
                         i += 1
                 else:
                     maxNum += 1
                     ifPlusMinus = 0
                     i += 1
 
         return maxNum

class Solution:
     def maxChunksToSorted(self, arr):
         """
         :type arr: List[int]
         :rtype: int
         """
         from collections import Counter
         s = sorted(arr)
 
         i = 0
         a_nums = Counter()
         b_nums = Counter()
         total = 0
         while i < len(arr):
             a_nums[arr[i]] += 1
             b_nums[s[i]] += 1
             if a_nums == b_nums:
                 a_nums.clear()
                 b_nums.clear()
                 total += 1
             i += 1
 
         return total