Well Explained and Efficient Solution | Java Implementation | Combinatorics
IntuitionFind the contribution for each number in nums and then sum them up.Approach
Initially, sort the array. Consideration of maxima and minima are now easie
# Intuition
Find the contribution for each number in nums and then sum them up.

# Approach
- Initially, sort the array. Consideration of maxima and minima are now easier.
- Now, for any element $$nums[i]$$, $$nums[i]$$ is the minima for all subsequences in $$nums[i:]$$ and the maxima for all subsequences in $$nums[:i]$$ that contains $$nums[i]$$. Lets us consider the Maxima.
- Since we can choose only at most $$k$$ elements, we've got to choose at most $$k - 1$$ elements within $$nums[:i]$$

The number of possibilities for choosing at most $$x$$ (here $$x = k - 1$$) elements within $$n$$ elements is given by:

$$f(n) = \binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{x}$$


If you consider $$n$$ elements for the index $$i$$, you need to consider $$n + 1$$ elements for the index $$i + 1$$.

$$f(n + 1) = \binom{n + 1}{0} + \binom{n + 1}{1} + \dots + \binom{n + 1}{x}$$

Now to find a relaltion between $$f(n)$$ and $$f(n + 1)$$, we use the following formula:

$$\binom{n + 1}{r} - \binom{n}{r} = \binom{n}{r - 1}$$

Therefore,

$$f(n + 1) - f(n) = (\binom{n + 1}{0} - \binom{n}{0}) + (\binom{n + 1}{1} - \binom{n}{1}) + \dots + (\binom{n + 1}{x} - \binom{n}{x})$$

which gives,

$$f(n + 1) - f(n) = \binom{n}{-1} + \binom{n}{0} + \dots + \binom{n}{x - 1}$$

$$f(n + 1) - f(n) = f(n) - \binom{n}{x}$$

$$f(n + 1)  = 2 *  f(n) - \binom{n}{x}$$

This formula with $$O(1)$$ complexity is much more efficient when compared to the brute approach with $$O(nk)$$ complexity.

The same formula applies in the reverse order for Minima.
The contribution value for the $$Maxima(nums[i]) = Minima(nums[n - i - 1])$$

Now it is easier to find the solution by running a single loop by considering both forward(minima) and reverse(maxima) order traversals by using the same contributions values for both.

# Complexity
- Time complexity: $$O(nlogn)$$

- Space complexity: $$O(n)$$

# Code
```java []
class Solution {
    private int mod = 1_000_000_007;
    private long[] fact;
    private long pow(long a, long b, int mod) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1)
                res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }
    private long comb(int n, int k) {
        if (n < k)
            return 0;
        return fact[n] * pow(fact[k], mod - 2, mod) % mod * pow(fact[n - k], mod - 2, mod) % mod;
    }
    public int minMaxSums(int[] nums, int k) {
        int n = nums.length;
        fact = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++)
            fact[i] = fact[i - 1] * i % mod;
        Arrays.sort(nums);
        long ans = 0;
        long cur = 1;
        for (int i = 0; i < n; i++) {
            ans = (ans + (nums[i] + nums[n - i - 1]) * cur) % mod;
            cur = (2 * cur - comb(i, k - 1) + mod) % mod;
        }
        return (int) ans;
    }
}

```
['Combinatorics', 'Java']