The math behind | Clear explanation | Two Approaches | O(N log N) | My first solution write-up ^_^
APPROACH-1Intuition Overviewi) How sorting might help in
- choosing max (from left to right)
- and min (from right to left)ii) Observe the symmetry
and understa
# APPROACH-1

# Intuition Overview

i) **How sorting might help in**
    - choosing max (from left to right)
    - and min (from right to left)
    
ii) **Observe the symmetry**
and understand how many times a **particular number is being counted as max while moving left to right** and **it's counterpart is being counted as min while moving right to left**.

# More Explanation on Code Level

i) **SORT THE ARRAY**.
```
N = len(nums)
```
In the sorted array, if we consider **SubArrays** including **num[i]** where **i** is the last index of *SubArray*, it will always be **MAXIMUM** and similarly while considering **SubArrays** in the descending order/right to left, including **num[N-1-i]** where **N-1-i** is the last index of *SubArray*, it will always be **MINIMUM**. So, from this observation, we conclude that **the number of times** where **num[i] is MAXIMUM** is **same as** where **num[N-1-i] is MINIMUM**.
So,
```python3
ans += t * (nums[i] + nums[N - 1 - i])
```
ii) **FOCUS ON  variable `t` FOR EACH i**.

As the **Maximum SubArray length** is k. That means we can have SubArrays of any length between 0 and k, right?

If I include **i-th** index everytime, that means I have to choose **atmost k-1** values from first **i numbers** of consideration. Which I can do in $$\sum_{j=0}^{k-1} iCj$$  ways

For **0-indexed**, **i-th index** symbolizes **i+1 numbers so far**. So, there are **i numbers at the left of i-th indexed number**.

When I am considering i-th index, that means I have already worked on i numbers.


# Complexity
- Time complexity:
    - Sorting: $O (N \log N)$
    - Loops: $O (NK)$

- Space complexity: $O (NK)$

# Code
```python3 []
MOD = 1000000007

class Solution:
    def minMaxSums(self, nums: List[int], k: int) -> int:
        
        nums.sort() 
        N = len(nums)

        # DP with Pascal's Triangle for nCr
        C = [[0] * (k + 1) for _ in range(N + 1)]
        C[0][0] = 1
        
        for n in range(1, N + 1):
            C[n][0] = 1
            for r in range(1, k + 1):
                C[n][r] = (C[n - 1][r - 1] + C[n - 1][r]) % MOD
        
        ans = 0
        # adding the iCj sum for j from 0 upto k-1
        # as i-th indexed number is k-th number
        # of consideration all the time
        for i in range(N):
            t = 0
            for j in range(k):
                if j <= i: # if i < j the iCj = 0
                    t += C[i][j] % MOD 

            ans += (t * (nums[i] + nums[N - 1 - i])) % MOD
        
        return ans

```

---
# APPROACH-2 - More efficient

# Intuition

idea is still same but we will calculate variable `t` in a different way now. 

```
t = 1
for i in range(N):
    sum += ( t*(nums[i] + nums[N - 1 - i]) ) % MOD
    t = 2*t - C[i][k-1]
```

this works because of the underlying mathematical property:

$$
\sum_{t=0}^{k-1} \binom{i+1}{t} = 2 \times \sum_{t=0}^{k-1} \binom{i}{t} - \binom{i}{k-1}.
$$

### Let's prove this property

#### Recall Pascal’s identity:

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

#### Apply sum to both sides:

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

#### Adjust the Index in the Second Sum
In the second summation, let’s shift the index of summation by setting $ t' = t-1 $. When $ t = 0 $, $ t' = -1 $, and when $ t = k-1 $, $ t' = k-2 $. Thus: $
\sum_{t=0}^{k-1} \binom{i}{t-1} = \sum_{t'=-1}^{k-2} \binom{i}{t'}
$

For binomial coefficients, $\binom{i}{t'} = 0$ when $t' < 0$.
So we can safely remove the $t' = -1$ term
and rewrite the summation as: $
\sum_{t=0}^{k-1} \binom{i}{t-1} = \sum_{t=0}^{k-2} \binom{i}{t}
$

#### Combining the Two Summations
$$
\sum_{t=0}^{k-1} \binom{i+1}{t} = \sum_{t=0}^{k-1} \binom{i}{t} + \sum_{t=0}^{k-2} \binom{i}{t}.
$$

Notice that the first summation includes terms from $t=0$ to $t=k-1$, while the second summation includes terms from $t=0$ to $t=k-2$. Combine these to rewrite the result:

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

#### Substituting the Complement

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

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

$$
\sum_{t=0}^{k-1} \binom{i+1}{t} = 2 \left( \sum_{t=0}^{k-1} \binom{i}{t} - \binom{i}{k-1} \right) + \binom{i}{k-1}.
$$

So, $$
\sum_{t=0}^{k-1} \binom{i+1}{t} = 2 \sum_{t=0}^{k-1} \binom{i}{t} - \binom{i}{k-1}.
$$

Now to use the formula for $$ \sum_{j=0}^{k-1} \binom{i}{j} $$ recursively but with iteration, we set $ t = \binom{0}{0} = 1$ for $i = 0$, and in the next iterations where **i value increments** we have previous **t** value as $\sum_{j=0}^{k-1} \binom{i}{j}$. So, next **t value** equals to **2 * (previous t) - C[i][k-1]** thanks to the property $$
\sum_{t=0}^{k-1} \binom{i+1}{t} = 2 \times \sum_{t=0}^{k-1} \binom{i}{t} - \binom{i}{k-1}.
$$

# CODE
```python3 []
MOD = 1000000007

class Solution:
    def minMaxSums(self, nums: List[int], k: int) -> int:
        
        nums.sort()
        N = len(nums)

        ans = 0
        t = 1
        
        # comb is a built-in function for nCr
        # using it as I may not need too many nCrs this time
        for i in range(N):
            ans += (t * (nums[i] + nums[N - 1 - i])) % MOD
            t = (2 * t - comb(i, k - 1)) % MOD

        return ans % MOD

```

# Complexity
- Time complexity:
    - Sorting: $O (N \log N)$
    - Loops: $O (N)$
    - Overall: $O (N \log N)$

- Space complexity: $O (1)$

---
Hope this solution write-up helped you. Thank you for bearing with me. Suggestions for improvement are always appreciated


['Math', 'Dynamic Programming', 'Combinatorics', 'Python3']