23.04.04 Today’s Leetcode

1636. Sort Array by Increasing Frequency (easy)

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        counter = Counter(nums)
        d = defaultdict(list)
        for key, value in counter.items():
            heappush(d[value], -key)
        
        # print(d)
        res = []
        for key in sorted(list(d.keys())):
            while d[key]:
                tar = -heappop(d[key])
                res += [tar] * key

        return res

2206. Divide Array Into Equal Pairs (easy)

class Solution:
    def divideArray(self, nums: List[int]) -> bool:
        counter = Counter(nums)
        for value in counter.values():
            if value % 2 == 1:
                return False
        return True

2369. Check if There is a Valid Partition For The Array (medium)

class Solution:
    def validPartition(self, nums: List[int]) -> bool:

        n = len(nums)
        dp = {}
        def dfs(index):
            if index in dp:
                return dp[index]
            if index >= n:
                return True
            res = False
            a = nums[index]
            b = nums[index + 1] if index + 1 < n else -1
            c = nums[index + 2] if index + 2 < n else -1
            if a == b:
                res |= dfs(index + 2)
            if a == b and b == c:
                res |= dfs(index + 3)
            if a + 1 == b and b + 1 == c:
                res |= dfs(index + 3)
            dp[index] = res
            return res

        return dfs(0)

2405. Optimal Partition of String (medium)

class Solution:
    def partitionString(self, s: str) -> int:
        temp = set()
        n = len(s)
        res = 0
        for i in range(n):
            if s[i] in temp:
                res += 1
                # print(temp)
                temp = set()
            temp.add(s[i])
        return res + 1

763. Partition Labels (medium)

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        d = {}
        n = len(s)
        for i in range(n):
            word = s[i]
            if word not in d:
                d[word] = [i, i]
            d[word][0] = min(d[word][0], i)
            d[word][1] = max(d[word][0], i)
        
        i = 0
        res = []
        while i < n:
            word = s[i]
            j = i
            tar = d[word][1]
            while j < tar:
                tar = max(tar, d[s[j]][1])
                j += 1
            res.append(tar - i + 1)
            i = tar + 1

        return res

1712. Ways to Split Array Into Three Subarrays (medium)

TLE : 49/87

class Solution:
    def waysToSplit(self, nums: List[int]) -> int:
        n = len(nums)
        d = []
        temp = 0
        for i in range(n):
            temp += nums[i]
            d.append(temp)

        count = 0
        for i in range(1, n):
            for j in range(i + 1, n):
                left, mid, right = nums[0:i], nums[i:j], nums[j:n]
                a, b, c = d[i - 1], d[j - 1] - d[i - 1], d[n - 1] - d[j - 1]
                # print(left, mid, right)
                # print(a, b, c)
                if a <= b and b <= c:
                    count += 1
                if b > c:
                    break

prefix Sum : strictly increasing list -> we can use binary search!

class Solution:
    def waysToSplit(self, nums: List[int]) -> int:
        prefix = [0]
        for x in nums: prefix.append(prefix[-1] + x)
        
        ans = 0
        for i in range(1, len(nums)): 
            j = bisect_left(prefix, 2*prefix[i])
            k = bisect_right(prefix, (prefix[i] + prefix[-1])//2)
            ans += max(0, min(len(nums), k) - max(i+1, j))
        return ans % 1_000_000_007