23.05.24 Today’s Leetcode

2542. Maximum Subsequence Score (medium)

DFS Approach TLE at 12/28

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        n = len(nums1)
        res = 0

        @functools.lru_cache(None)
        def dfs(a, b, index, count):
            if count == 0:
                nonlocal res
                res = max(res, a * b)
                return
            for i in range(index, n):
                dfs(a + nums1[i], min(b, nums2[i]), i + 1, count - 1)
        
        dfs(0, math.inf, 0, k)

        return res

Approach with prefixSum

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        res, prefixSum, maxHeap = 0, 0, []
        # sorted with nums2, therefore no need to consider minimum value of subsequences of nums2
        # clever approach!
        for a, b in sorted(list(zip(nums1, nums2)), key=itemgetter(1), reverse=True):
            prefixSum += a
            heappush(maxHeap, a)
            if len(maxHeap) == k:
                res = max(res, prefixSum * b)
                prefixSum -= heappop(maxHeap)                               
        return res

2596. Check Knight Tour Configuration (medium)

class Solution:
    def checkValidGrid(self, grid: List[List[int]]) -> bool:
        n = len(grid)
        d = [(0, 0)] * (n * n)
        for i in range(n):
            for j in range(n):
                num = grid[i][j]
                d[num] = (i, j)

        if d[0] != (0, 0):
            return False

        for i in range(n * n - 1):
            a, b = d[i], d[i + 1]
            if abs(a[0] - b[0]) * abs(a[1] - b[1]) != 2:
                return False

        # print(d)
        return True

2592. Maximize Greatness of an Array

TLE at 1069 / 1072

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        res = 0
        arr = sorted(nums)
        while arr:
            n = len(arr)
            temp = []
            for i in range(n - 1):
                if arr[i] < arr[i + 1]:
                    res += 1
                else:
                    temp.append(arr[i])
            # temp.append(arr[-1])
            arr = temp if len(arr) > len(temp) else None
                
        return res

Sliding window Approach

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        arr = sorted(nums)
        n = len(nums)
        res = i = j = 0
        while j < n:
            if arr[i] < arr[j]:
                i += 1
                j += 1
                res += 1
            elif arr[i] == arr[j]:
                j += 1
            else:
                break
        return res

2583. Kth Largest Sum in a Binary Tree (medium)

class Solution:
    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
        q = deque([root])
        heap = []
        while q:
            temp = deque([])
            num = 0
            while q:
                tar = q.popleft()
                num += tar.val
                if tar.left: temp.append(tar.left)
                if tar.right: temp.append(tar.right)

            q = temp
            heappush(heap, -num)
        
        if len(heap) < k: return -1

        res = -1
        for i in range(k):
            res = -heappop(heap)

        return res