Is Maximum Total Value of Covered Indices easy or hard?

Maximum Total Value of Covered Indices is considered a medium difficulty problem. The challenge lies in recognizing the weighted interval scheduling pattern and optimizing the DP transition with binary search to reach O(m log m) time.

Maximum Total Value of Covered Indices Python/Java solution

Typical implementations compute prefix sums, sort intervals by end index, and use DP with binary search to find the last compatible interval. The same logic works across Python, Java, and C++ because it relies on standard arrays, sorting, and binary search utilities.

How to solve Maximum Total Value of Covered Indices in O(m log m)?

First compute prefix sums so the value of any interval [l, r] can be calculated instantly. Sort intervals by their ending position. For each interval, use binary search to locate the last interval that ends before its start, then apply the DP relation dp[i] = max(dp[i-1], value(i) + dp[prev]).

What is the best approach for Maximum Total Value of Covered Indices?

The best approach is weighted interval scheduling combined with prefix sums and binary search. Prefix sums compute the value of any interval in O(1), intervals are sorted by end index, and binary search finds the previous non-overlapping interval. The dynamic programming transition then builds the optimal answer in O(m log m) time.

Is Maximum Total Value of Covered Indices asked at Google/Amazon/Meta?

Problems based on weighted interval scheduling frequently appear in interviews at companies like Google, Amazon, and Meta. The exact problem title may vary, but the underlying pattern of selecting non-overlapping intervals with maximum total value is a common interview theme.

What data structure is used in Maximum Total Value of Covered Indices?

The solution primarily uses arrays for dynamic programming, prefix sums for constant-time range value calculation, and binary search on a sorted interval list. Together these structures enable efficient compatibility checks between intervals.

What is the time complexity of Maximum Total Value of Covered Indices?

The optimal solution runs in O(m log m) time where m is the number of intervals. Sorting intervals takes O(m log m), and each DP step performs a binary search to find the last compatible interval. Space complexity is O(m) for the DP array.

Description Hints 4 Video 21:24

3952. Maximum Total Value of Covered Indices

Medium28.5% acceptance1 company

You are given an integer array nums of length n and a binary string s of length n, where s[i] == '1' means index i initially contains a token and s[i] == '0' means it does not.

You may perform the following operation any number of times:

Choose a token currently located at index i, where i > 0, such that this token has not been moved before.
Move this token from index i to index i - 1.

An index is considered covered if it contains a token after all moves.

Return an integer denoting the maximum total value of nums at the covered indices after optimally performing the operations.

Example 1:

Input: nums = [9,2,6,1], s = "0101"

Output: 15

Explanation:

Initially, indices 1 and 3 contain tokens.
Move the token from index 3 to index 2.
Move the token from index 1 to index 0.
The covered indices are [0, 2], so the total value is nums[0] + nums[2] = 9 + 6 = 15.

Example 2:

Input: nums = [5,1,4], s = "001"

Output: 4

Explanation:

Initially, only index 2 contains a token.
It is optimal to leave the token at index 2.
The covered index is [2], so the total value is nums[2] = 4.

Example 3:

Input: nums = [9,3,5], s = "011"

Output: 14

Explanation:

Initially, indices 1 and 2 contain tokens.
Move the token from index 1 to index 0.
The covered indices are [0, 2], so the total value is nums[0] + nums[2] = 9 + 5 = 14.

Constraints:

1 <= n == nums.length == s.length <= 10⁵
1 <= nums[i] <= 10⁵
s[i] is either '0' or '1'

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

1a (Greedy). Consider each maximal block of consecutive tokens independently, together with the index immediately before the block if it exists.

Hint 2

1b (Greedy). From this range, every index except one can be covered, so subtract the minimum nums value in the range.

Hint 3

2a (DP). A token at index i can only end at i or i - 1.

Hint 4

2b (DP). Process indices from left to right and keep whether the previous index is already covered; try both choices for the current token when possible.

LanguageLoading editor…

1class Solution:
2    def maxTotal(self, nums: List[int], s: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[9,2,6,1]
"0101"

Input

[5,1,4]
"001"

Input

[9,3,5]
"011"

Your code is saved on this device.