23.07.01 Today’s Leetcode

1027. Longest Arithmetic Subsequence (medium)

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 2:
            return n

        longest = 2
        dp = [{} for _ in range(n)]

        for i in range(n):
            for j in range(i):
                diff = nums[i] - nums[j]
                dp[i][diff] = dp[j].get(diff, 1) + 1
                longest = max(longest, dp[i][diff])

        return longest

2305. Fair Distribution of Cookies (medium)

Backtracking with 2 ways

class Solution:
    def distributeCookies(self, cookies: List[int], k: int) -> int:
        def dfs(p):
            nonlocal best
            if p == len(cookies):
                best = min(best, max(split))
                return
            if len(split) < k:
                split.append(cookies[p])
                dfs(p + 1)
                split.pop()
            # give to a kid that already has cookies
            for i in range(len(split)):
                if split[i] + cookies[p] < best:
                    split[i] += cookies[p]
                    dfs(p + 1)
                    split[i] -= cookies[p]

        split = []
        best = float("inf")
        dfs(0)
        return best

First Approach

class Solution:
    def distributeCookies(self, cookies: List[int], k: int) -> int:
        arr = sorted(cookies)
        num = sum(arr)
        n = len(arr)
        tar = num // k

        def help():
            temp = 0
            i, j = 0, n - 1
            while True:
                if temp >= tar:
                    break
                if i < n:
                    temp += arr[i]
                    arr[i] = 0
                    i += 1
                if j > 0:
                    temp += arr[j]
                    arr[j] = 0
                    j -= 1
            return temp
        
        res = math.inf
        for _ in range(2):
            res = min(res, help())
            print(arr)
        
        return res