Skip to main content
Talentd

Maximum Total Sum with Threshold Constraints - Solution & Explanation

MediumPremiumFree on FleetCodeArrayGreedySortingHeap (Priority Queue)11 min read
Practice this problem

Problem Statement

You are given two integer arrays nums and threshold, both of length n.

Starting at step = 1, you perform the following repeatedly:

  • Choose an unused index i such that threshold[i] <= step.
    • If no such index exists, the process ends.
  • Add nums[i] to your running total.
  • Mark index i as used and increment step by 1.

Return the maximum total sum you can obtain by choosing indices optimally.

 

Example 1:

Input: nums = [1,10,4,2,1,6], threshold = [5,1,5,5,2,2]

Output: 17

Explanation:

  • At step = 1, choose i = 1 since threshold[1] <= step. The total sum becomes 10. Mark index 1.
  • At step = 2, choose i = 4 since threshold[4] <= step. The total sum becomes 11. Mark index 4.
  • At step = 3, choose i = 5 since threshold[5] <= step. The total sum becomes 17. Mark index 5.
  • At step = 4, we cannot choose indices 0, 2, or 3 because their thresholds are > 4, so we end the process.

Example 2:

Input: nums = [4,1,5,2,3], threshold = [3,3,2,3,3]

Output: 0

Explanation:

At step = 1 there is no index i with threshold[i] <= 1, so the process ends immediately. Thus, the total sum is 0.

Example 3:

Input: nums = [2,6,10,13], threshold = [2,1,1,1]

Output: 31

Explanation:

  • At step = 1, choose i = 3 since threshold[3] <= step. The total sum becomes 13. Mark index 3.
  • At step = 2, choose i = 2 since threshold[2] <= step. The total sum becomes 23. Mark index 2.
  • At step = 3, choose i = 1 since threshold[1] <= step. The total sum becomes 29. Mark index 1.
  • At step = 4, choose i = 0 since threshold[0] <= step. The total sum becomes 31. Mark index 0.
  • After step = 4 all indices have been chosen, so the process ends.

 

Constraints:

  • n == nums.length == threshold.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= 109
  • 1 <= threshold[i] <= n

Approach Overview

Problem Overview: You are given an array where each element represents the maximum value (threshold) you can assign to a position. Choose a value for every position such that it does not exceed its threshold and all chosen values remain valid under the constraint rules. The objective is to maximize the total sum of the chosen values.

Approach 1: Greedy + Sorting (O(n log n) time, O(1) extra space)

The optimal strategy is greedy. Larger thresholds should receive larger assigned values because they give more flexibility. Start by sorting the threshold array in descending order using sorting. Track the largest value you can still assign, initially equal to the largest threshold. For each element, assign min(current_threshold, previous_assigned - 1). This enforces the decreasing constraint while staying within each threshold. If the computed value becomes zero or negative, a valid assignment is impossible. Otherwise, accumulate the value into the total sum. This works because greedily giving the largest feasible value early preserves room for smaller thresholds later.

Approach 2: Greedy with Max Heap (Priority Queue) (O(n log n) time, O(n) space)

A heap (priority queue) can also simulate the greedy selection process. Push all thresholds into a max heap and repeatedly take the largest available threshold. Maintain the previously assigned value and reduce it by one each step to enforce the constraint. If the popped threshold is smaller than the allowed value, clamp the assignment to that threshold. The heap ensures you always process the largest remaining candidate first. This approach is conceptually similar to sorting but useful when values arrive dynamically or when you want explicit control over priority ordering.

Why the Greedy Strategy Works

The key insight is that assigning the largest possible value to the largest threshold cannot harm future decisions. Smaller thresholds already limit future choices, so delaying large assignments would only reduce the achievable total. Greedy ordering after sorting ensures every step locally maximizes the sum while keeping the global constraints satisfied.

Recommended for interviews: The Greedy + Sorting approach is what interviewers typically expect. It demonstrates understanding of greedy decision making and efficient use of arrays with sorting. Mentioning a brute-force search shows baseline reasoning, but deriving the sorted greedy rule signals strong problem-solving ability.

Solution

We observe that at each step, we want to select the largest number among those that satisfy the condition to add to the total sum. Therefore, we can use a greedy approach to solve this problem.

We first sort an index array idx of length n in ascending order by their corresponding thresholds. Then, we use a sorted set or priority queue (max heap) to maintain the numbers that currently satisfy the condition. At each step, we add all numbers whose thresholds are less than or equal to the current step number into the sorted set or priority queue, and then select the largest number among them to add to the total sum. If the sorted set or priority queue is empty at this point, it means there are no numbers that satisfy the condition, and we end the process.

The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force AssignmentO(n!)O(n)Conceptual baseline to understand constraints; not practical for large inputs
Greedy + SortingO(n log n)O(1) or O(log n)Best general solution when all thresholds are known upfront
Greedy with Max HeapO(n log n)O(n)Useful when thresholds are processed dynamically or streaming

Video Solution

Maximum Total Sum With Threshold Constraints • Owen Wu • 43 views views

Frequently Asked Questions

Is Maximum Total Sum with Threshold Constraints easy or hard?
Maximum Total Sum with Threshold Constraints is typically rated Medium. The implementation is short, but recognizing the greedy rule—sorting thresholds and decreasing the allowed value step by step—is the key insight that makes the problem straightforward.
Maximum Total Sum with Threshold Constraints Python/Java solution
Most implementations sort the threshold array and iterate from the largest value downward. For each step, assign min(threshold, previous_value - 1) and add it to the running total. The same greedy logic works in Python, Java, C++, Go, TypeScript, and Rust with O(n log n) complexity.
How to solve Maximum Total Sum with Threshold Constraints in O(n)?
An exact O(n) solution generally isn't possible because the greedy strategy requires ordering thresholds by size. Sorting dominates the runtime at O(n log n). After sorting, the assignment step itself is O(n) using a simple greedy rule that reduces the previous value by one each iteration.
What is the best approach for Maximum Total Sum with Threshold Constraints?
The best approach is Greedy with Sorting. Sort the thresholds in descending order and assign values greedily so each assignment is at most the threshold and strictly smaller than the previous assignment. This guarantees the maximum possible total while satisfying the constraints. The time complexity is O(n log n) due to sorting.
Is Maximum Total Sum with Threshold Constraints asked at Google/Amazon/Meta?
Greedy allocation problems with sorting constraints appear frequently in interviews at companies like Amazon, Google, and Meta. Variants often involve assigning values under upper bounds, scheduling tasks with decreasing limits, or maximizing sums under ordering constraints.
What data structure is used in Maximum Total Sum with Threshold Constraints?
The primary structures are arrays and sorting. A max heap (priority queue) can also be used to repeatedly extract the largest threshold while maintaining the greedy constraint. Both approaches rely on processing elements in descending order of their limits.
What is the time complexity of Maximum Total Sum with Threshold Constraints?
The optimal greedy solution runs in O(n log n) time because the thresholds must be sorted first. After sorting, a single linear pass assigns the values and computes the total sum in O(n). The extra space usage is O(1) if sorting is done in place.

Ready to solve this problem?

Practice Maximum Total Sum with Threshold Constraints with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays