23.05.08 Today’s Leetcode

1572. Matrix Diagonal Sum (easy)

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        n = len(mat)
        res = 0
        for i in range(n):
            res += mat[i][i]
            if i != n - 1 - i:
                res += mat[i][n - 1 - i]
        
        return res

1573. Number of Ways to Split a String (medium)

class Solution:
    def numWays(self, s: str) -> int:
        n = len(s)
        MOD = 10**9 + 7
        num = Counter(s)['1']
        if num == 0:
            return (n * (n - 1) // 2 - (n - 1)) % MOD
        if num % 3 != 0:
            return 0
        num //= 3

        temp = 0
        arr = [0]
        for index, char in enumerate(s):
            if char == '0' and temp == -1:
                arr[-1] += 1
            if char == '1':
                if temp == -1:
                    temp = 0
                    arr.append(0)
                temp += 1
            if temp == num:
                temp = -1

        # print(arr)
        return (arr[0] + 1) * (arr[1] + 1) % MOD

implementation with split

class Solution:
    def numWays(self, s: str) -> int:
# First count 1's in given string. cnt = s.count('1')
# if cnt == 0: special case: return (len(s)-1)*(len(s)-2)//2
# elif cnt is not divisible by 3: return 0
# else:
# keep track of indices of 1's in ones list:
# for exaple: s = '100100010100110'
# ones = [0,3,7,9,12,13]
# we need to devide this list into 3parts:
# '1001' + {0's here} + '101' + {0's here }+ '110'
# result = x * y
# x = number of 0's between first and second part + 1
# y = number of 0's between second and third part + 1
# to find x and y:
# x = ones[cnt//3] - ones[cnt//3-1]
# y = ones[2*cnt//3] - ones[2*cnt//3-1]
        n = len(s)
        ss = s.split("1")
        ones = len(ss)-1
        
        # The ones can't be evenly distributed over 3 arrays.
        if ones % 3 != 0:
            return 0
        
        # Case with 0 ones.
        if ones == 0:
            # (n-1) choose 2, because we have n-1 split points
            # and have to pick two splits.
            return ((n-1)*(n-2)//2) % (10**9+7)
        
        # Normal case.
        return ((len(ss[ones//3])+1) * (len(ss[ones//3*2])+1)) % (10**9+7)

1574. Shortest Subarray to be Removed to Make Array Sorted (medium)

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        # sentinel
        arr.append(float("inf"))
        arr.insert(0, 0)
        
        left = 0
        right = len(arr) - 1
        shortest = float("inf")
        # find longest ascending array at left side.
        while left < len(arr) - 2 and arr[left] <= arr[left + 1]:
            left += 1
            
        # [0, 1, 2, 3, 10, 4, 2, 3, 5, ∞]
        #               ↑              
        #             left           
        
        # move right pointer while moving left pointer.
        while left >= 0:
            while right - 1 > left and arr[right - 1] >= arr[left] and arr[right] >= arr[right - 1]:
                right -= 1
            shortest = min(shortest, right - left - 1)
            left -= 1
            
        # [0, 1, 2, 3, 10, 4, 2, 3, 5, ∞]
        #               ↑              ↑
        #             left           right  -> length = 4
        #   
        # [0, 1, 2, 3, 10, 4, 2, 3, 5, ∞]
        #           ↑            ↑
        #          left        right        -> length = 3
        #
        # [0, 1, 2, 3, 10, 4, 2, 3, 5, ∞]
        #        ↑            ↑
        #       left        right           -> length = 3
        #
        # [0, 1, 2, 3, 10, 4, 2, 3, 5, ∞]
        #        ↑            ↑
        #       left        right           -> length = 3
        #
        # [0, 1, 2, 3, 10, 4, 2, 3, 5, ∞]
        #     ↑               ↑
        #    left           right           -> length = 4
        #
        # [0, 1, 2, 3, 10, 4, 2, 3, 5, ∞]
        #  ↑                  ↑
        # left              right           -> length = 5
            
        return shortest