Find the Sum of Subsequence Powers

Hard

#2752Time: O(k * n^2 * D), where D is the number of distinct power values. In the worst case, D is O(n^2), leading to a time complexity of O(k * n^4). Given n <= 50, this might be too slow but could pass if the number of distinct powers is small in practice.Space: O(k * n * D), where D is the number of distinct power values. In the worst case, D can be O(n^2), leading to a space complexity of O(k * n^3).1 company

Patterns

Algorithms

Data structures

Companies

Prompt

You are given an integer array nums of length n, and a positive integer k.

The power of a subsequence is defined as the minimum absolute difference between any two elements in the subsequence.

Return the sum of powers of all subsequences of nums which have length equal to k.

Since the answer may be large, return it modulo 10⁹+ 7.

Example 1:

Input: nums = [1,2,3,4], k = 3

Output: 4

Explanation:

There are 4 subsequences in nums which have length 3: [1,2,3], [1,3,4], [1,2,4], and [2,3,4]. The sum of powers is |2 - 3| + |3 - 4| + |2 - 1| + |3 - 4| = 4.

Example 2:

Input: nums = [2,2], k = 2

Output: 0

Explanation:

The only subsequence in nums which has length 2 is [2,2]. The sum of powers is |2 - 2| = 0.

Example 3:

Input: nums = [4,3,-1], k = 2

Output: 10

Explanation:

There are 3 subsequences in nums which have length 2: [4,3], [4,-1], and [3,-1]. The sum of powers is |4 - 3| + |4 - (-1)| + |3 - (-1)| = 10.

Constraints:

2 <= n == nums.length <= 50
-10⁸ <= nums[i] <= 10⁸
2 <= k <= n

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to directly build the distribution of powers for subsequences of increasing lengths. We define a DP state that stores not just a single value, but a map from each possible power value to the count of subsequences having that power.

Algorithm

Sort the Input Array: First, sort the nums array in non-decreasing order. This simplifies the calculation of differences, as |a - b| becomes b - a for a < b. The set of subsequences remains the same, only their element order might change, which doesn't affect the power calculation.
Define DP State: Let dp[i][j] be a map where dp[i][j][p] stores the number of subsequences of length j that can be formed using elements from nums[0...i], with nums[i] being the largest element, and having a power of exactly p.
Base Case: For subsequences of length 1, the power is undefined. We can consider it to be infinite. So, for each i from 0 to n-1, dp[i][1] will be a map { infinity: 1 }.
DP Transition: We build the solution for length j from 2 to k. To compute dp[i][j], we consider nums[i] as the largest element. The second largest element must be nums[p] for some p < i. The remaining j-2 elements must be chosen from nums[0...p-1].
- A subsequence of length j with nums[i] as the max and nums[p] as the second max is formed by taking a subsequence of length j-1 ending at nums[p] and appending nums[i].
- Let S' be a subsequence of length j-1 ending at nums[p]. Its power is power(S'). The new subsequence S = S' ∪ {nums[i]} has power(S) = min(power(S'), nums[i] - nums[p]).
- We iterate through p from j-2 to i-1. For each p, we iterate through the power distribution map dp[p][j-1]. For each entry (power_old, count) in dp[p][j-1], the new power is min(power_old, nums[i] - nums[p]). We add count to the corresponding entry in dp[i][j]'s map.
Calculate Total Sum: After filling the dp table up to length k, the total sum of powers is the sum of power * count for all entries in all dp[i][k] maps, for i from k-1 to n-1. All calculations should be done modulo 10^9 + 7.

Walkthrough

The core idea is to compute, for each length j and ending element nums[i], how many subsequences have a certain power. We can define dp[i][j] as a hash map, where keys are power values and values are the counts of subsequences of length j ending at nums[i] with that power.

To compute dp[i][j], we iterate through all possible previous elements nums[p] (p < i). For each p, we look at the power distributions of subsequences of length j-1 ending at p, which is dp[p][j-1]. For each (old_power, count) pair in dp[p][j-1], we form a new subsequence by adding nums[i]. The new power will be min(old_power, nums[i] - nums[p]). We update the map dp[i][j] with this new information.

After computing these distributions for all i and for j=k, the final answer is obtained by summing up power * count over all these distributions.

1import java.util.Arrays;2import java.util.HashMap;3import java.util.Map;4 5class Solution {6    public int sumOfPowers(int[] nums, int k) {7        Arrays.sort(nums);8        int n = nums.length;9        long MOD = 1_000_000_007;10 11        // dp[i][j] is a map from power to count for subsequences of length j ending at nums[i]12        Map<Integer, Long>[][] dp = new HashMap[n][k + 1];13        for (int i = 0; i < n; i++) {14            for (int j = 0; j <= k; j++) {15                dp[i][j] = new HashMap<>();16            }17        }18 19        // Base case: subsequences of length 120        for (int i = 0; i < n; i++) {21            dp[i][1].put(Integer.MAX_VALUE, 1L); // Power is effectively infinite22        }23 24        for (int len = 2; len <= k; len++) {25            for (int i = len - 1; i < n; i++) {26                for (int p = len - 2; p < i; p++) {27                    int diff = nums[i] - nums[p];28                    for (Map.Entry<Integer, Long> entry : dp[p][len - 1].entrySet()) {29                        int oldPower = entry.getKey();30                        long count = entry.getValue();31                        int newPower = Math.min(oldPower, diff);32                        dp[i][len].put(newPower, (dp[i][len].getOrDefault(newPower, 0L) + count) % MOD);33                    }34                }35            }36        }37 38        long totalSumOfPowers = 0;39        for (int i = k - 1; i < n; i++) {40            for (Map.Entry<Integer, Long> entry : dp[i][k].entrySet()) {41                long power = entry.getKey();42                long count = entry.getValue();43                totalSumOfPowers = (totalSumOfPowers + (power * count) % MOD) % MOD;44            }45        }46 47        return (int) totalSumOfPowers;48    }49}

Complexity

Time

O(k * n^2 * D), where D is the number of distinct power values. In the worst case, D is O(n^2), leading to a time complexity of O(k * n^4). Given n <= 50, this might be too slow but could pass if the number of distinct powers is small in practice.

Space

O(k * n * D), where D is the number of distinct power values. In the worst case, D can be O(n^2), leading to a space complexity of O(k * n^3).

Trade-offs

Pros

It's a direct and intuitive DP formulation of the problem.
It correctly solves the problem without complex combinatorial identities.

Cons

The time complexity is high, making it potentially slow for the given constraints, though it might just pass.
The space complexity is also significant due to storing maps for each DP state.

A more efficient approach transforms the problem. Instead of summing the powers directly, we sum the counts of subsequences that meet a certain power threshold. The sum of powers of all subsequences S is equal to the sum, over all possible positive integers d, of the number of subsequences with power greater than or equal to d.

The values of d for which this count changes are precisely the differences nums[j] - nums[i]. This allows us to discretize the problem. We only need to calculate the count for each unique difference value.

Algorithm

Sort the Input Array: Sort nums in non-decreasing order.
Key Identity: The core of this approach is the identity: Sum(power(S)) = Sum_{d > 0} (number of subsequences with power >= d). A subsequence S with power(S) = p is counted in the sum for d=1, 2, ..., p, contributing exactly p to the total sum.
Discretize Differences: The number of subsequences with power >= d only changes when d crosses a value equal to nums[j] - nums[i]. So, we only need to consider these O(n^2) difference values. Let V be the sorted list of unique positive differences nums[j] - nums[i].
Rewrite Sum: The total sum can be expressed as Sum_{i=1 to m} (v_i - v_{i-1}) * N(>=v_i), where v_i are the unique sorted differences from V, v_0 = 0, and N(>=v_i) is the number of subsequences of length k with power at least v_i.
DP for N(>=v): For a fixed difference v, we can calculate N(>=v) using dynamic programming in O(n*k) time.
- Let dp[i][j] be the number of subsequences of length j from nums[0...i-1] ending with nums[i-1] and having a minimum difference of at least v.
- The transition is dp[i][j] = sum(dp[p][j-1]) for all p < i such that nums[i-1] - nums[p-1] >= v.
- This summation can be optimized. Let S[i][j] be the prefix sum sum_{l=1 to i} dp[l][j]. Then dp[i][j] = S[m][j-1], where m is the largest index such that nums[m-1] <= nums[i-1] - v. The index m can be found efficiently using a two-pointer technique across the i loop.
Main Loop: Iterate through the sorted unique differences v from V. In each iteration, calculate N(>=v) using the O(n*k) DP. Then add (v - prev_v) * N(>=v) to the total sum. Update prev_v = v and continue. Remember to use modulo arithmetic.

Walkthrough

First, we sort the nums array. The main insight is to change the summation: Sum(power(S)) = Sum_{d > 0} (count of subsequences with power >= d). Since the count of subsequences with power >= d is a step function that only changes at values d = nums[j] - nums[i], we can compute the sum more efficiently.

Let v_1, v_2, ..., v_m be the unique sorted positive differences. The total sum is (v_1 - v_0)*N(>=v_1) + (v_2 - v_1)*N(>=v_2) + ..., where v_0 = 0 and N(>=v) is the number of subsequences of length k with power at least v.

For each required v, we can compute N(>=v) using an O(n*k) dynamic programming algorithm. Let dp[i][j] be the number of valid subsequences of length j using elements from nums[0...i-1] and ending with nums[i-1]. To form such a subsequence, we must pick a previous element nums[p-1] such that nums[i-1] - nums[p-1] >= v. The number of ways is the sum of dp[p][j-1] over all valid p. This sum can be optimized using prefix sums and a two-pointer approach to achieve O(n*k) complexity for each v.

Since there are O(n^2) unique differences, the total time complexity becomes O(n^2 * n * k) = O(n^3 * k).

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.Collections;4import java.util.HashSet;5import java.util.List;6import java.util.Set;7 8class Solution {9    long MOD = 1_000_000_007;10 11    public int sumOfPowers(int[] nums, int k) {12        Arrays.sort(nums);13        int n = nums.length;14 15        Set<Integer> diffSet = new HashSet<>();16        for (int i = 0; i < n; i++) {17            for (int j = i + 1; j < n; j++) {18                diffSet.add(nums[j] - nums[i]);19            }20        }21        List<Integer> diffs = new ArrayList<>(diffSet);22        Collections.sort(diffs);23 24        long totalSum = 0;25        long prev_v = 0;26 27        for (int v : diffs) {28            long count = countSubsequencesWithMinDiff(nums, k, v);29            long term = ((long)(v - prev_v) * count) % MOD;30            totalSum = (totalSum + term) % MOD;31            prev_v = v;32        }33 34        return (int) totalSum;35    }36 37    private long countSubsequencesWithMinDiff(int[] nums, int k, int minDiff) {38        int n = nums.length;39        long[][] dp = new long[n + 1][k + 1];40        long[][] prefixSum = new long[n + 1][k + 1];41 42        for (int i = 1; i <= n; i++) {43            dp[i][1] = 1;44            prefixSum[i][1] = prefixSum[i - 1][1] + dp[i][1];45        }46 47        for (int j = 2; j <= k; j++) {48            int p_ptr = 1;49            for (int i = 1; i <= n; i++) {50                while (p_ptr < i && nums[i - 1] - nums[p_ptr - 1] >= minDiff) {51                    p_ptr++;52                }53                // p_ptr is now at the first index that doesn't satisfy the condition54                // So we can sum up to p_ptr - 155                if (p_ptr > 0) {56                    dp[i][j] = prefixSum[p_ptr - 1][j - 1];57                }58            }59            for (int i = 1; i <= n; i++) {60                prefixSum[i][j] = (prefixSum[i - 1][j] + dp[i][j]) % MOD;61            }62        }63 64        return prefixSum[n][k];65    }66}

Complexity

Time

O(n^2 * log(n^2) + D * n * k), where D is the number of unique differences. D can be up to O(n^2). The dominant part is `D * n * k`, leading to a total complexity of O(n^3 * k).

Space

O(n^2 + n*k). O(n^2) to store the unique differences and O(n*k) for the DP table in the helper function.

Trade-offs

Pros

Significantly more efficient than the direct DP approach.
The complexity is well within the limits for the given constraints.

Cons

The logic is more complex, relying on a combinatorial identity and a DP on top of it.
Implementation requires careful handling of several nested loops and data structures.

Solutions

Solution

1class Solution {2private3  Map<Long, Integer> f = new HashMap<>();4private5  final int mod = (int)1 e9 + 7;6private7  int[] nums;8public9  int sumOfPowers(int[] nums, int k) {10    Arrays.sort(nums);11    this.nums = nums;12    return dfs(0, nums.length, k, Integer.MAX_VALUE);13  }14private15  int dfs(int i, int j, int k, int mi) {16    if (i >= nums.length) {17      return k == 0 ? mi : 0;18    }19    long key = (1L * mi) << 18 | (i << 12) | (j << 6) | k;20    if (f.containsKey(key)) {21      return f.get(key);22    }23    int ans = dfs(i + 1, j, k, mi);24    if (j == nums.length) {25      ans += dfs(i + 1, i, k - 1, mi);26    } else {27      ans += dfs(i + 1, i, k - 1, Math.min(mi, nums[i] - nums[j]));28    }29    ans %= mod;30    f.put(key, ans);31    return ans;32  }33}

1class Solution:2    def sumOfPowers(self, nums: List[int], k: int) -> int: @ cache def dfs(i: int, j: int, k: int, mi: int) -> int: if i >= n: return mi if k == 0 else 0 ans = dfs(i + 1, j, k, mi) if j == n: ans += dfs(i + 1, i, k - 1, mi) else: ans += dfs(i + 1, i, k - 1, min(mi, nums[i] - nums[j])) ans %= mod return ans mod = 10 ** 9 + 7 n = len(nums) nums . sort() return dfs(0, n, k, inf)

1class Solution {2public:3  int sumOfPowers(vector<int> &nums, int k) {4    unordered_map<long long, int> f;5    const int mod = 1e9 + 7;6    int n = nums.size();7    sort(nums.begin(), nums.end());8    function<int(int, int, int, int)> dfs = [&](int i, int j, int k, int mi) {9      if (i >= n) {10        return k == 0 ? mi : 0;11      }12      long long key = (1LL * mi) << 18 | (i << 12) | (j << 6) | k;13      if (f.contains(key)) {14        return f[key];15      }16      long long ans = dfs(i + 1, j, k, mi);17      if (j == n) {18        ans += dfs(i + 1, i, k - 1, mi);19      } else {20        ans += dfs(i + 1, i, k - 1, min(mi, nums[i] - nums[j]));21      }22      ans %= mod;23      f[key] = ans;24      return f[key];25    };26    return dfs(0, n, k, INT_MAX);27  }28};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  Map<Long, Integer> f = new HashMap<>();4private5  final int mod = (int)1 e9 + 7;6private7  int[] nums;8public9  int sumOfPowers(int[] nums, int k) {10    Arrays.sort(nums);11    this.nums = nums;12    return dfs(0, nums.length, k, Integer.MAX_VALUE);13  }14private15  int dfs(int i, int j, int k, int mi) {16    if (i >= nums.length) {17      return k == 0 ? mi : 0;18    }19    long key = (1L * mi) << 18 | (i << 12) | (j << 6) | k;20    if (f.containsKey(key)) {21      return f.get(key);22    }23    int ans = dfs(i + 1, j, k, mi);24    if (j == nums.length) {25      ans += dfs(i + 1, i, k - 1, mi);26    } else {27      ans += dfs(i + 1, i, k - 1, Math.min(mi, nums[i] - nums[j]));28    }29    ans %= mod;30    f.put(key, ans);31    return ans;32  }33}

1class Solution:2    def sumOfPowers(self, nums: List[int], k: int) -> int: @ cache def dfs(i: int, j: int, k: int, mi: int) -> int: if i >= n: return mi if k == 0 else 0 ans = dfs(i + 1, j, k, mi) if j == n: ans += dfs(i + 1, i, k - 1, mi) else: ans += dfs(i + 1, i, k - 1, min(mi, nums[i] - nums[j])) ans %= mod return ans mod = 10 ** 9 + 7 n = len(nums) nums . sort() return dfs(0, n, k, inf)

1class Solution {2public:3  int sumOfPowers(vector<int> &nums, int k) {4    unordered_map<long long, int> f;5    const int mod = 1e9 + 7;6    int n = nums.size();7    sort(nums.begin(), nums.end());8    function<int(int, int, int, int)> dfs = [&](int i, int j, int k, int mi) {9      if (i >= n) {10        return k == 0 ? mi : 0;11      }12      long long key = (1LL * mi) << 18 | (i << 12) | (j << 6) | k;13      if (f.contains(key)) {14        return f[key];15      }16      long long ans = dfs(i + 1, j, k, mi);17      if (j == n) {18        ans += dfs(i + 1, i, k - 1, mi);19      } else {20        ans += dfs(i + 1, i, k - 1, min(mi, nums[i] - nums[j]));21      }22      ans %= mod;23      f[key] = ans;24      return f[key];25    };26    return dfs(0, n, k, INT_MAX);27  }28};

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.