LeetCode Problem 3428

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming, Sorting, Combinatorics

Solution

Problem Understanding

We are given an array nums and an integer k.

For every subsequence whose size is at most k, we look at two values:

• The minimum element in that subsequence.
• The maximum element in that subsequence.

We add minimum + maximum for every valid subsequence, then return the total modulo 10^9 + 7.

A key detail is that the problem asks for subsequences, not subarrays. A subsequence can be formed by choosing any subset of indices while preserving relative order. Since the minimum and maximum depend only on the chosen values, the ordering aspect is not especially important for the final counting argument.

The constraints are the most important clue:

• n = nums.length can be as large as 100000.
• k <= 70.

A brute force enumeration of subsequences is impossible because there are 2^n subsequences in total.

The unusually small value of k compared to n strongly suggests that we should derive a combinatorial counting formula whose complexity depends on k rather than on the number of subsequences.

Some important edge cases are:

• k = 1, where every valid subsequence contains exactly one element.
• Arrays containing duplicate values.
• Arrays where all values are identical.
• Very large n, where an O(n^2) solution is far too slow.
• Very large element values up to 10^9, requiring modular arithmetic.

Approaches

Brute Force

The most direct approach is to generate every subsequence whose size is at most k.

For each generated subsequence:

1. Find its minimum element.
2. Find its maximum element.
3. Add their sum to the answer.

This is correct because it exactly follows the problem definition.

Unfortunately, even if we restrict ourselves to subsequences of size at most k, the number of such subsequences is still enormous when n = 100000. Enumerating them is completely infeasible.

Key Observation

Instead of enumerating subsequences, we can count how many times each element contributes as a minimum and how many times it contributes as a maximum.

After sorting the array:

• If nums[i] is the maximum of a subsequence, every other selected element must come from positions 0..i-1.
• If nums[i] is the minimum of a subsequence, every other selected element must come from positions i+1..n-1.

Suppose the array is sorted.

For nums[i] to be the maximum:

• Choose t additional elements from the i elements to its left.
• The subsequence size becomes t + 1.
• Since the size must be at most k, we need t <= k - 1.

Therefore the number of subsequences where nums[i] is the maximum is

$$\sum_{t=0}^{k-1} \binom{i}{t}$$

Similarly, the number of subsequences where nums[i] is the minimum is

$$\sum_{t=0}^{k-1} \binom{n-1-i}{t}$$

Thus the contribution of nums[i] is

$$nums[i] \left( \sum_{t=0}^{k-1}\binom{i}{t} + \sum_{t=0}^{k-1}\binom{n-1-i}{t} \right)$$

The entire problem reduces to efficiently computing

$$F(m)=\sum_{t=0}^{k-1}\binom{m}{t}$$

for every m from 0 to n-1.

Because k <= 70, we can compute all required binomial coefficients in O(nk) time using Pascal's identity.

Problem Understanding

We are given an array nums and an integer k.

A subsequence is obtained by choosing any subset of indices while preserving their relative order. For every subsequence whose size is at most k, we compute:

$$\text{minimum element} + \text{maximum element}$$

The task is to sum this quantity over all subsequences having between 1 and k elements, inclusive.

Because the number of subsequences grows exponentially, the answer can be extremely large, so the final result must be returned modulo:

$$10^9 + 7$$

The constraints are the key to understanding the intended solution:

• n = nums.length can be as large as 100000.
• k ≤ 70.

A solution that explicitly generates subsequences is impossible because there are $2^n$ subsequences. The small value of k is the crucial observation that allows a combinatorial counting solution.

Several edge cases deserve attention:

• k = 1, only single-element subsequences contribute.
• All values equal, where minimum and maximum are always the same.
• Large arrays (n = 100000) requiring near-linear time.
• Duplicate values, which must be handled correctly without double-counting.
• k > n, although the constraints guarantee k ≤ n.

Approaches

Brute Force

The most direct approach is to enumerate every subsequence whose size is at most k.

For each subsequence, compute its minimum and maximum values, add them to the answer, and continue until all subsequences have been processed.

This approach is correct because it literally follows the problem statement. However, it is completely infeasible. Even when k = n, there are $2^n - 1$ non-empty subsequences. For n = 100000, this is astronomically large.

Key Observation

Instead of enumerating subsequences, count how many times each element contributes as a minimum and how many times it contributes as a maximum.

Sort the array:

$$a_0 \le a_1 \le \cdots \le a_{n-1}$$

Consider element $a_i$.

If $a_i$ is the maximum of a subsequence, then every other selected element must come from the indices to its left.

If we choose exactly $j$ additional elements from the first $i$ positions, the subsequence size becomes $j+1$, and the number of such subsequences is

$$\binom{i}{j}.$$

Since the subsequence size must be at most $k$,

$$0 \le j \le k-1.$$

Therefore the number of subsequences in which $a_i$ is the maximum equals

$$M(i) = \sum_{j=0}^{k-1} \binom{i}{j}.$$

Similarly, $a_i$ is the minimum when all other chosen elements come from its right side:

$$m(i) = \sum_{j=0}^{k-1} \binom{n-1-i}{j}.$$

Hence the total contribution of $a_i$ is

$$a_i \bigl(M(i)+m(i)\bigr).$$

The problem reduces to efficiently computing

$$S(t) = \sum_{j=0}^{k-1} \binom{t}{j}$$

for every $t\in[0,n-1]$.

Because $k\le 70$, we can generate Pascal's triangle rows up to degree $k-1$ in $O(nk)$ time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Enumerates subsequences directly
Optimal	O(nk)	O(n)	Counts minimum and maximum contributions combinatorially

Algorithm Walkthrough

1. Sort nums in nondecreasing order.

After sorting, every element to the left of index i is less than or equal to nums[i], and every element to the right is greater than or equal to it. This makes counting minimum and maximum occurrences straightforward. 2. Define

$$F(m)=\sum_{t=0}^{k-1}\binom{m}{t}$$

We will compute this value for every m from 0 to n-1. 3. Use Pascal's identity:

$$\binom{m+1}{t} = \binom{m}{t} + \binom{m}{t-1}$$

Maintain a one-dimensional array comb where comb[t] stores the current value of $\binom{m}{t}$. 4. For each m:

• Compute F[m] as the sum of all current binomial coefficients.
• Update the Pascal row in reverse order to obtain the coefficients for m + 1.

Reverse iteration is necessary so that old values are not overwritten before they are used. 5. After building the entire F array:

• F[i] equals the number of valid subsequences where the sorted element nums[i] is the maximum.
• F[n-1-i] equals the number of valid subsequences where the same element is the minimum.

6. For every sorted index i, add

$$nums[i]\cdot(F[i]+F[n-1-i])$$

to the answer. 7. Return the answer modulo 10^9 + 7.

Why it works

For a sorted array, every subsequence has a unique maximum position and a unique minimum position. When nums[i] serves as the maximum, every other chosen element must come from the i positions to its left. Choosing t of them yields exactly $\binom{i}{t}$ valid subsequences. Summing over all allowed sizes gives the exact number of times nums[i] appears as a maximum. The same argument applies symmetrically for minimums. Since every subsequence contributes exactly one minimum and one maximum, summing all element contributions produces the desired total.

Python Solution

| Brute Force | $O(2^n \cdot n)$ | $O(n)$ | Enumerates subsequences explicitly | | Optimal | $O(nk)$ | $O(k)$ | Counts min/max contributions combinatorially |

Algorithm Walkthrough

1. Sort nums in nondecreasing order.
2. Define

$$S(t)=\sum_{j=0}^{k-1}\binom{t}{j}.$$

We need S(0), S(1), ..., S(n-1). 3. Maintain a truncated Pascal row:

$$dp[j] = \binom{t}{j}.$$

Initially for $t=0$,

$$dp[0]=1,\qquad dp[j]=0\ (j>0).$$ 4. For each value of t from 0 to n-1:

• Compute

$$S(t)=\sum_{j=0}^{k-1} dp[j].$$

• Store this value.
• Update the row to represent $t+1$ using Pascal's identity

$$\binom{t+1}{j} = \binom{t}{j} + \binom{t}{j-1}.$$

This is performed from right to left so that old values are not overwritten. 5. After preprocessing, count[t] = S(t) for every t. 6. For each sorted element nums[i]:

• Number of times it is a maximum:

$$count[i].$$

• Number of times it is a minimum:

$$count[n-1-i].$$

• Add

$$nums[i]\cdot \bigl(count[i]+count[n-1-i]\bigr)$$

to the answer. 7. Return the result modulo $10^9+7$.

Why it works

After sorting, every subsequence has a unique maximum and a unique minimum position. For a fixed index $i$, the only way for $a_i$ to be the maximum is to choose all remaining elements from the first $i$ positions. The number of such choices of size at most $k$ is exactly

$$\sum_{j=0}^{k-1}\binom{i}{j}.$$

The same reasoning applies to minima using the suffix to the right. Since every subsequence contributes exactly once to its maximum and exactly once to its minimum, summing all element contributions yields precisely the required total.

Python Solution

from typing import List

class Solution:
    def minMaxSums(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7

        nums.sort()
        n = len(nums)

        f = [0] * n

        # comb[t] = C(current_m, t)
        comb = [0] * k
        comb[0] = 1

        for m in range(n):
            f[m] = sum(comb) % MOD

            upper = min(k - 1, m + 1)
            for t in range(upper, 0, -1):
                comb[t] = (comb[t] + comb[t - 1]) % MOD

        ans = 0

        for i, value in enumerate(nums):
            count_max = f[i]
            count_min = f[n - 1 - i]

            ans = (
                ans
                + value * ((count_max + count_min) % MOD)
            ) % MOD
        counts = [0] * n

        dp = [0] * k
        dp[0] = 1

        for t in range(n):
            counts[t] = sum(dp) % MOD

            upper = min(k - 1, t + 1)
            for j in range(upper, 0, -1):
                dp[j] = (dp[j] + dp[j - 1]) % MOD

        ans = 0

        for i, x in enumerate(nums):
            contribution_count = (counts[i] + counts[n - 1 - i]) % MOD
            ans = (ans + x * contribution_count) % MOD

        return ans

The implementation begins by sorting the array. This enables the counting argument that treats each element independently as a potential minimum or maximum.

The array comb stores one row of Pascal's triangle. Initially it represents row 0, namely [1, 0, 0, ...].

For each value of m, the sum of the current row entries gives

$$\sum_{t=0}^{k-1}\binom{m}{t}$$

which is stored in f[m].

The reverse update implements Pascal's identity and transforms row m into row m + 1.

Finally, for each sorted element:

• f[i] counts the subsequences where it is the maximum.
• f[n - 1 - i] counts the subsequences where it is the minimum.

Multiplying by the element value and summing all contributions yields the answer.

Go Solution

The implementation begins by sorting the array, which allows minimum and maximum contributions to be counted independently.

The array dp stores a truncated Pascal row. At iteration t, dp[j] equals $\binom{t}{j}$. Summing the row gives

$$\sum_{j=0}^{k-1}\binom{t}{j},$$

which is exactly the number of valid ways an element can act as an extreme value.

The right-to-left update implements Pascal's identity while preserving the previous row values.

Finally, each sorted element contributes according to the number of subsequences in which it serves as a maximum and the number in which it serves as a minimum.

Go Solution

package main

import "sort"

func minMaxSums(nums []int, k int) int {
	const MOD int64 = 1_000_000_007

	sort.Ints(nums)
	n := len(nums)

	f := make([]int64, n)

	comb := make([]int64, k)
	comb[0] = 1

	for m := 0; m < n; m++ {
		var rowSum int64
		for _, v := range comb {
			rowSum += v
		}
		f[m] = rowSum % MOD

		upper := k - 1
		if m+1 < upper {
			upper = m + 1
		}

		for t := upper; t >= 1; t-- {
			comb[t] = (comb[t] + comb[t-1]) % MOD
		}
	}

	var ans int64

	for i, value := range nums {
		count := (f[i] + f[n-1-i]) % MOD
		ans = (ans + int64(value)*count) % MOD

	n := len(nums)
	counts := make([]int64, n)

	dp := make([]int64, k)
	dp[0] = 1

	for t := 0; t < n; t++ {
		var s int64 = 0
		for _, v := range dp {
			s += v
		}
		counts[t] = s % MOD

		upper := k - 1
		if t+1 < upper {
			upper = t + 1
		}

		for j := upper; j >= 1; j-- {
			dp[j] = (dp[j] + dp[j-1]) % MOD
		}
	}

	var ans int64 = 0

	for i, x := range nums {
		cnt := (counts[i] + counts[n-1-i]) % MOD
		ans = (ans + int64(x)*cnt) % MOD
	}

	return int(ans)
}

The Go implementation follows exactly the same logic as the Python version. The primary difference is the use of int64 for all arithmetic involving counts and contributions. This avoids overflow before taking the modulo. The sorted slice is modified in place using sort.Ints.

Worked Examples

Example 1

Input: The Go version follows exactly the same combinatorial logic. The primary difference is that all arithmetic is performed using int64 to avoid overflow before taking modulo. Slices are used for both the Pascal row and the precomputed count array.

Worked Examples

Example 1

Input

nums = [1,2,3]
k = 2

Sorted array: After sorting:

[1,2,3]

Computing F

m	Binomial Terms	F(m)
0	C(0,0)=1	1
1	C(1,0)+C(1,1)=1+1	2
2	C(2,0)+C(2,1)=1+2	3

Therefore:

F = [1, 2, 3]

Contributions

i	value	max count	min count	contribution
0	1	F[0]=1	F[2]=3	4
1	2	F[1]=2	F[1]=2	8
2	3	F[2]=3	F[0]=1	12
Compute S(t).

t	Pascal row	S(t)
0	[1,0]	1
1	[1,1]	2
2	[1,2]	3

Thus:

counts = [1,2,3]

Contribution table:

i	value	max count	min count	total count	contribution
0	1	1	3	4	4
1	2	2	2	4	8
2	3	3	1	4	12

Total:

4 + 8 + 12 = 24

Example 2

Input:

Example 2

Input

nums = [5,0,6]
k = 1

Sorted:

[0,5,6]

Since k = 1:

$$F(m)=C(m,0)=1$$

So:

F = [1,1,1]

Contributions

value	max count	min count	contribution
0	1	1	0
5	1	1	10
6	1	1	12

Total:

22

Example 3

Input: Since k=1:

$$S(t)=\binom{t}{0}=1$$

for every t.

counts = [1,1,1]

Contribution table:

value	total count
0	2
5	2
6	2

Answer:

0*2 + 5*2 + 6*2 = 22

Example 3

Input

nums = [1,1,1]
k = 2

Sorted:

[1,1,1]

Again:

F = [1,2,3]

Contributions

i	value	max count	min count	contribution
0	1	1	3	4
1	1	2	2	4
2	1	3	1	4

Total:

12

Complexity Analysis

Measure	Complexity	Explanation
Time	O(nk)	Computing all required combinatorial sums uses n rows and at most k updates per row
Space	O(n)	The F array stores one value per index

The dominant work is building the combinatorial counts. Because k ≤ 70, the O(nk) complexity is practical even when n = 100000. The Pascal-triangle update uses only k values per row, which keeps the computation efficient.

Test Cases

sol = Solution()

assert sol.minMaxSums([1, 2, 3], 2) == 24      # example 1
assert sol.minMaxSums([5, 0, 6], 1) == 22      # example 2
assert sol.minMaxSums([1, 1, 1], 2) == 12      # example 3

assert sol.minMaxSums([7], 1) == 14            # single element

assert sol.minMaxSums([1, 2], 1) == 6          # only singleton subsequences

assert sol.minMaxSums([1, 2], 2) == 9          # includes pair

assert sol.minMaxSums([5, 5, 5], 3) == 70      # all values identical

assert sol.minMaxSums([0, 0, 0], 2) == 0       # all zeros

assert sol.minMaxSums([1, 3, 5, 7], 4) == 112  # k equals n

assert sol.minMaxSums([10**9, 10**9], 2) == 999999965  # modulo handling

Test Summary

Test	Why
[1,2,3], k=2	Official example
[5,0,6], k=1	Singleton subsequences only
[1,1,1], k=2	Duplicate values
[7], k=1	Smallest possible array
[1,2], k=1	Minimum size limit
[1,2], k=2	Includes all possible subsequences
[5,5,5], k=3	All values equal
[0,0,0], k=2	Zero-valued elements
[1,3,5,7], k=4	k = n case
Large values	Verifies modulo arithmetic

Edge Cases

Case 1: k = 1

When k = 1, every valid subsequence contains exactly one element. The minimum and maximum are the same element, so each value contributes twice.

A common bug is accidentally counting larger subsequences. In this implementation, the formula becomes:

$$F(m)=\binom{m}{0}=1$$

for every m, which correctly counts exactly one singleton subsequence per element.

Case 2: Duplicate Values

Arrays such as [1,1,1] can be tricky because multiple elements have the same value.

The algorithm counts subsequences based on sorted positions rather than distinct values. Every position is treated independently, which is exactly what the subsequence definition requires. Therefore duplicates are handled naturally and correctly.

Case 3: Very Large Array Size

With n = 100000, any quadratic solution is impossible.

The implementation never compares every pair of elements and never generates subsequences. The only substantial work is the Pascal-triangle update, which performs at most 70 operations per index. This keeps the runtime within acceptable limits.

Case 4: Large Element Values

Values can be as large as 10^9, and the number of valid subsequences can be enormous.

Without modular arithmetic, intermediate results would overflow. The implementation performs all combinatorial calculations modulo 10^9 + 7 and reduces the answer after every addition, ensuring correctness and preventing overflow. counts = [1,2,3]

Contribution table:

| i | value | total count |
| --- | --- | --- |
| 0 | 1 | 4 |
| 1 | 1 | 4 |
| 2 | 1 | 4 |

Answer:

4 + 4 + 4 = 12

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | $O(nk)$ | Each of the `n` Pascal rows updates at most `k` entries |
| Space | $O(n+k)$ | `counts` uses `O(n)`, Pascal row uses `O(k)` |

Because `k ≤ 70`, the factor `k` is effectively constant. Even for `n = 100000`, the algorithm performs roughly seven million Pascal updates, which is easily manageable.

## Test Cases

s = Solution()

assert s.minMaxSums([1, 2, 3], 2) == 24 # example 1 assert s.minMaxSums([5, 0, 6], 1) == 22 # example 2 assert s.minMaxSums([1, 1, 1], 2) == 12 # example 3

assert s.minMaxSums([7], 1) == 14 # single element assert s.minMaxSums([0], 1) == 0 # single zero

assert s.minMaxSums([1, 2], 1) == 6 # only singletons assert s.minMaxSums([1, 2], 2) == 9 # includes pair

assert s.minMaxSums([5, 5, 5], 1) == 30 # all equal, k=1 assert s.minMaxSums([5, 5, 5], 3) == 70 # all subsequences

assert s.minMaxSums([0, 0, 0, 0], 4) == 0 # all zeros

assert s.minMaxSums([1, 3, 2], 3) == 28 # all sizes allowed

assert s.minMaxSums([109, 109], 2) == ( (2 * 109 + 2 * 109 + 2 * 109) % (109 + 7) ) # large values

assert s.minMaxSums([4, 1, 7, 2], 2) == 70 # mixed ordering

| Test | Why |
| --- | --- |
| `[1,2,3], k=2` | Official example |
| `[5,0,6], k=1` | Only singleton subsequences |
| `[1,1,1], k=2` | Duplicate values |
| `[7], k=1` | Smallest non-empty input |
| `[0], k=1` | Single zero |
| `[1,2], k=1` | Boundary where only size 1 allowed |
| `[1,2], k=2` | Small array with all subsequences |
| `[5,5,5], k=1` | Equal values, singleton only |
| `[5,5,5], k=3` | Equal values, all sizes |
| `[0,0,0,0], k=4` | All contributions zero |
| `[1,3,2], k=3` | Unsorted input |
| Large values | Verifies modular arithmetic |
| `[4,1,7,2], k=2` | General mixed case |

## Edge Cases

### Single Element Array

When `n = 1`, the only subsequence is the element itself. The minimum and maximum are equal to that element, so the answer is twice its value. The contribution formula naturally handles this because both the minimum count and maximum count equal one.

### `k = 1`

Only singleton subsequences are allowed. Every element contributes once as a minimum and once as a maximum. The algorithm correctly computes

$$S(t)=\binom{t}{0}=1,$$

so every element receives exactly two contributions.

### Many Duplicate Values

A common mistake is to count contributions by value instead of by position. Equal values may appear in multiple positions, and each position participates in a different number of subsequences. Sorting and counting by index avoids this issue completely. Every occurrence is treated independently, guaranteeing correct combinatorial counts.

### Large Input Size

With `n = 100000`, any solution involving explicit combinations, recursion over subsequences, or $O(n^2)$ processing is infeasible. The implementation stores only a truncated Pascal row of length at most `70`, ensuring the update cost remains $O(nk)$, which comfortably satisfies the constraints.