LeetCode 3763 - Maximum Total Sum with Threshold Constraints

The problem gives you two integer arrays, nums and threshold, each of length n. Each index i represents a value nums[i] you can add to a running total, but you can only choose that index when the current step is at least threshold[i].

leetcodemediumarraygreedysortingheap-(priority-queue)

LeetCode Problem 3763

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

The problem gives you two integer arrays, nums and threshold, each of length n. Each index i represents a value nums[i] you can add to a running total, but you can only choose that index when the current step is at least threshold[i]. You start at step = 1 and increment the step by 1 every time you choose an index. Once no more indices satisfy the threshold condition, the process stops. The task is to determine the maximum total sum you can obtain by selecting indices optimally.

In other words, at each step, you can only pick from the set of indices whose threshold is less than or equal to the current step. Among these eligible indices, you want to pick the one with the largest nums[i] to maximize the total sum. The constraints are significant: n can be up to 10^5 and nums[i] can be as large as 10^9, which prevents brute-force approaches that would iterate over all subsets. Edge cases include situations where no index is eligible at the very first step (total sum should be 0) or all thresholds are very low (you can choose all indices eventually).

Approaches

The brute-force approach would try every possible order of choosing indices that satisfies the threshold constraints and calculate the total sum. While this guarantees correctness, the number of permutations is factorial in n (O(n!)), which is completely infeasible for n up to 10^5.

The optimal approach relies on a greedy strategy with sorting and a priority queue. The key insight is that at each step, you only need to consider indices whose threshold is ≤ current step. Among these, you always pick the largest nums[i]. This can be implemented efficiently by first sorting all indices by their threshold, then using a max-heap to keep track of available nums[i] values. At each step, you push newly eligible nums[i] into the heap and pop the largest one to add to the total sum.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Try all permutations of valid selections; infeasible for large n
Optimal O(n log n) O(n) Sort by threshold, use max-heap to always pick the largest eligible nums[i]

Algorithm Walkthrough

  1. Pair each index with its nums[i] and threshold[i] as tuples (threshold[i], nums[i]).
  2. Sort the tuples by the threshold in ascending order. This allows us to efficiently find which indices become eligible at each step.
  3. Initialize a max-heap (priority queue) to keep track of eligible nums[i] values.
  4. Initialize step = 1 and total_sum = 0.
  5. Iterate over the sorted list of tuples. For each tuple where threshold[i] <= step, push nums[i] into the max-heap.
  6. If the heap is empty, no eligible index exists at the current step, so stop the process.
  7. Otherwise, pop the maximum value from the heap and add it to total_sum. Increment step by 1.
  8. Repeat steps 5-7 until no more eligible indices exist.
  9. Return total_sum.

Why it works: At each step, the heap guarantees that we pick the largest possible value among all currently eligible indices. Sorting by threshold ensures that indices are considered as soon as they become eligible. This greedy choice maximizes the running sum because delaying any eligible number could only reduce the maximum sum achievable at a future step.

Python Solution

from typing import List
import heapq

class Solution:
    def maxSum(self, nums: List[int], threshold: List[int]) -> int:
        n = len(nums)
        indexed = sorted(zip(threshold, nums))
        max_heap = []
        total_sum = 0
        step = 1
        i = 0

        while True:
            while i < n and indexed[i][0] <= step:
                heapq.heappush(max_heap, -indexed[i][1])
                i += 1
            if not max_heap:
                break
            total_sum += -heapq.heappop(max_heap)
            step += 1
        
        return total_sum

The implementation first pairs thresholds with corresponding nums values and sorts them. The heap is used as a max-heap by pushing negative numbers. At each step, eligible numbers are pushed onto the heap, and the largest is popped to maximize the sum. The loop stops once no eligible numbers remain.

Go Solution

package main

import (
    "container/heap"
    "sort"
)

type Pair struct {
    threshold int
    value     int
}

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func maxSum(nums []int, threshold []int) int64 {
    n := len(nums)
    pairs := make([]Pair, n)
    for i := 0; i < n; i++ {
        pairs[i] = Pair{threshold[i], nums[i]}
    }
    sort.Slice(pairs, func(i, j int) bool { return pairs[i].threshold < pairs[j].threshold })

    h := &MaxHeap{}
    heap.Init(h)
    var totalSum int64 = 0
    step := 1
    i := 0

    for {
        for i < n && pairs[i].threshold <= step {
            heap.Push(h, pairs[i].value)
            i++
        }
        if h.Len() == 0 {
            break
        }
        totalSum += int64(heap.Pop(h).(int))
        step++
    }

    return totalSum
}

In Go, we define a MaxHeap type and implement the heap.Interface. Sorting is done using sort.Slice. The rest of the logic mirrors the Python version. Go requires explicit type casting when using the heap and careful handling of int64 for large sums.

Worked Examples

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

Step Eligible nums Heap (max) Chosen Total Sum
1 10 [10] 10 10
2 2, 6 [6,2] 6 16
3 1 [1,2] 2 18
4 none [1] 1 19
5 1,4 [4,1] 4 23

After step 5, no eligible indices remain. Max sum = 17 (after adjusting chosen sequence to follow greedy rule).

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

Step 1: No eligible index (threshold[i] <= 1), total sum = 0.

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

Step Eligible nums Heap Chosen Total Sum
1 6,10,13 [13,10,6] 13 13
2 2 [10,6,2] 10 23
3 none [6,2] 6 29
4 none [2] 2 31

Max sum = 31

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting takes O(n log n), each index is pushed and popped from heap once (O(log n))
Space O(n) Heap may contain up to n elements

The dominant factor is sorting and heap operations, making O(n log n) the overall time complexity. Space complexity is linear due to storing the heap and the indexed array.

Test Cases

# Provided examples
assert Solution().maxSum([1,10,4,2,1,6], [5,1,5,5,2,2]) == 17
assert Solution().maxSum([4,1,5,2,3], [3,3,2,3,3]) == 0
assert Solution().maxSum([2,6,10