LeetCode 2554. Maximum Number of Integers to Choose From a Range I

Dynamic Programming

The problem can be thought as Knapsack Without Repeat problem where items are in $\{1, 2, 3, \ldots, n\} \setminus \texttt{banned}$ , capacity is $maxSum$ , and value of each item is $1$ .

Time: $\mathcal{O}(n \cdot maxSum)$ , space: same.

class Solution:

    def solve_knapsack_no_repeat(self, weights, values, cap) -> List[int]:
        m = len(weights)
        dp = [
            [0] * (cap+1) for _ in range( m+1 )
        ]

        for i in range(1, m+1):
            for W in range(1, cap+1):
                dp[i][W] = dp[i-1][W]

                w_i = weights[i-1]
                v_i = values[i-1]
                if w_i <= W:
                    dp[i][W] = max( dp[i][W], v_i + dp[i-1][W - w_i] )

        return dp[m][cap]

    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        banned_set = set(banned)
        allowed = [x for x in range(1, n+1) if x not in banned_set]

        return self.solve_knapsack_no_repeat( allowed, [1]*len(allowed), maxSum )

Since a subproblem depends only on subproblems from the previous row, we can reuse two rows.

Time: $\mathcal{O}(n \cdot maxSum)$ , space: $\mathcal{O}(maxSum)$ .

class Solution:
    def solve_knapsack_no_repeat(self, weights, values, cap) -> List[int]:
        m = len(weights)
        dp = [
            [0] * (cap+1) for _ in range( 2 )
        ]
        prev_i, curr_i = 0, 1
        for i in range(1, m+1):
            for W in range(1, cap+1):
                dp[curr_i][W] = dp[prev_i][W]

                w_i = weights[i-1]
                v_i = values[i-1]
                if w_i <= W:
                    dp[curr_i][W] = max( dp[curr_i][W], v_i + dp[prev_i][W - w_i] )
            
            prev_i, curr_i = curr_i, prev_i

        return dp[prev_i][cap]

    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        banned_set = set(banned)
        allowed = [x for x in range(1, n+1) if x not in banned_set]

        return self.solve_knapsack_no_repeat( allowed, [1]*len(allowed), maxSum )

Greedy

Since all items have same value, we can greedily take the items with smallest weights. Additionally, weights are presorted; so, we just keep taking prefix weights until we hit cap.

Say the allowed numbers are $\langle x_1, x_2, \ldots, x_i, x_j, \ldots x_n \rangle$ and our greedy solution includes the prefix $x_1, x_2, \ldots, x_i$ . So, $\forall_{k \ge j} \left(maxSum - \sum_{l = 1}^{i} x_l \right) < x_k$ . So, we cannot plainly append to our greedy solution. Only way to improve over it would be to replace and append. If we replace one of our greedy numbers with one of the $x_k$ ‘s, the gap with $maxSum$ would be even smaller forbidding a following append.

Time: $\mathcal{O}(|\texttt{banned}| + n)$ , space: $\mathcal{O}(|\texttt{banned}|)$ .

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        banned_set = set(banned)
        curr_sum, count = 0, 0
        for x in range(1, n+1):
            if x in banned_set:
                continue
            if (next_sum := curr_sum+x) > maxSum:
                return count
            curr_sum, count = next_sum, count+1
        return count

To reduce space, we could use sorted banned list instead of creating a set.

Time: $\mathcal{O}( |\texttt{banned}| \cdot \lg{( |\texttt{banned}| )} + n + |\texttt{banned}|)$ , space: that of sorting.

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        banned.sort()
        b = 0
        curr_sum, count = 0, 0
        for x in range(1, n+1):
            if b < len(banned) and x == banned[b]:
                # Find next distinct banned
                while b < len(banned) and banned[b] == x:
                    b += 1
                continue
            if (next_sum := curr_sum+x) > maxSum:
                return count
            curr_sum, count = next_sum, count+1
        return count

unreasonably effective