23.04.01 Today’s Leetcode

704. Binary Search (easy)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start, end = 0, len(nums)
        while start < end:
            mid = (start + end) // 2
            if nums[mid] < target:
                start = mid + 1
            elif nums[mid] > target:
                end = mid
            else:
                return mid
        if start < len(nums) and nums[start] == target:
            return start
        return -1

2529. Maximum Count of Positive Integer and Negative Integer (easy)

class Solution:
    def maximumCount(self, arr: List[int]) -> int:
        n = len(arr)
        def help():
            if arr[0] >= 0:
                return 0
            start, end = 0, n
            while start < end:
                mid = (start + end) // 2
                if arr[mid] < 0:
                    start = mid + 1
                elif arr[mid] > 0:
                    end = mid
                else:
                    return mid
            return start

        neg = temp = help()
        while temp < n and arr[temp] == 0:
            temp += 1
        pos = n - temp
        print(neg, pos)
        return max(neg, pos)

1351. Count Negative Numbers in a Sorted Matrix (easy)

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        res = 0
        for col in grid:
            res += bisect_left(col[::-1], 0)
        return res

948. Bag of Tokens (medium)

DFS Approach : Failed

class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
        n = len(tokens)
        res = 0
        tokens = sorted(tokens)
        # print(tokens)
        played = [False] * n
        d = {}
        def dfs(score, power):
            nonlocal res, played
            res = max(res, score)
            if (score, power) in d:
                return d[score, power]
            d[score, power] = max(res, d.get((score, power), 0))
            for i in range(n):
                if played[i]:
                    continue
                if tokens[i] <= power:
                    played[i] = True
                    dfs(score + 1, power - tokens[i])
                    played[i] = False
                if score >= 1:
                    played[i] = True
                    dfs(score - 1, power + tokens[i])
                    played[i] = False
        
        dfs(0, power)
        return res

Greedy Approach

class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
        tokens.sort()
        i, j = 0, len(tokens) - 1
        res = score = 0
        while i < j:
            if tokens[i] > power and score == 0:
                break
            if tokens[i] <= power:
                score += 1
                power -= tokens[i]
                res = max(res, score)
                i += 1
            elif score > 0:
                score -= 1
                power += tokens[j]
                j -= 1
        if i < len(tokens) and tokens[i] <= power:
            score += 1
            res = max(res, score)
        return res