*This is the advanced version of the 
[Minimum and Maximum Product of k Elements](https://www.codewars.com/kata/minimum-and-maximum-product-of-k-elements/) kata.*

---

Given a list of **integers** and a positive integer `k` (> 0), find the minimum and maximum possible product of `k` elements taken from the list.

If you cannot take enough elements from the list, return `None`/`nil`.

## Examples

```python
numbers = [1, -2, -3, 4, 6, 7]

k = 1  ==>  -3, 7
k = 2  ==>  -21, 42    # -3*7, 6*7
k = 3  ==>  -126, 168  # -3*6*7, 4*6*7
k = 7  ==>  None       # there are only 6 elements in the list
```

Note: the test lists can contain up to 500 elements, so a naive approach will not work.

---

## My other katas

If you enjoyed this kata then please try [my other katas](https://www.codewars.com/collections/katas-created-by-anter69)! :-)

#### *Translations are welcome!*

Difficulty: introductory

Starter code:

def find_min_max_product(arr, k):
	

Solutions:
from functools import reduce

def find_min_max_product(arr, k):        
    if k <= len(arr):
        arr   = sorted(arr, key=abs)
        lasts = arr[-k:]
        v1    = reduce(int.__mul__, lasts)
        v0    = reduce(int.__mul__, arr[:k])
        
        first_SameOrOpp   = [next((v for v in lasts              if cmp(v<0, v1<0) ), None) for cmp in (int.__eq__, int.__ne__)]
        prevVal_OppOrSame = [next((v for v in reversed(arr[:-k]) if cmp(v<0, v1<0) ), None) for cmp in (int.__ne__, int.__eq__)]
        
        ans = [v0,v1] + [ v1*n//f for f,n in zip(first_SameOrOpp, prevVal_OppOrSame) if None not in (f,n) ]
        
        return min(ans), max(ans)


from functools import reduce
from operator import mul

def find_min_max_product(arr, k):
    if k > len(arr): return None
    
    if k == 1: return min(arr), max(arr)
    
    if k == len(arr):
        prod = reduce(mul, arr)
        return prod, prod
    
    arr = sorted(arr)
    prods = []
    for i in range(k+1):
        nums = arr[:k-i] + (arr[-i:] if i else [])
        prods.append(reduce(mul, nums))
    
    return min(prods), max(prods)

def find_min_max_product(arr, k):
    n = len(arr)
    if (k>n):
        return None
    
    t_plus =[]
    t_minus = []
    res = []
    for to in arr:
        if (to==0):
            res.append(0)
        elif to>0:
            t_plus.append(to)
        else:
            t_minus.append(to)
            
    t_plus.sort()
    t_minus.sort()
    
    for to in t_plus:
        res.append(to)
    for to in t_minus:
        res.append(to)
    
    ans = 1
    
    for i in range(k):
        ans = ans*res[i];
        
    ans_min = ans
    ans_max = ans
    
    for i in range(n-k+1):
        ans = 1
        for j in range(i,i+k):
            ans=ans*res[j]
            
        ans_min = min(ans,ans_min)
        ans_max = max(ans,ans_max)
    
    
    return (ans_min,ans_max)


def find_min_max_product(arr, k):
    if k > len(arr): return None
    arr.sort(key=abs, reverse=True)
    neg, pos, prod = None, None, 1
    for i in range(k):
        if arr[i] < 0: neg = arr[i]
        if arr[i] > 0: pos = arr[i]
        prod *= arr[i]
    neg1, pos1 = None, None
    for i in range(k, len(arr)):
        if not neg1 and arr[i] < 0: neg1 = arr[i]
        if not pos1 and arr[i] > 0: pos1 = arr[i]
        if neg1 and pos1: break
    candidates = [prod]
    if neg and pos1: candidates.append(prod // neg * pos1)
    if pos and neg1: candidates.append(prod // pos * neg1)
    if not (neg and neg1 and pos and pos1):
        prod = 1
        for i in range(-k, 0): prod *= arr[i]
        candidates.append(prod)
    return min(candidates), max(candidates)

from operator import mul
from functools import reduce
from collections import deque
from itertools import compress
from heapq import nsmallest, nlargest

def find_min_max_product(arr, k):
    if k <= len(arr):
        large = nlargest(k, arr)[::-1]
        small = nsmallest(min(k, len(arr) - k), arr)
        darr = small + large
        mask = deque([0] * len(small) + [1] * len(large))
        res = []
        for b in range(len(darr)):
            res.append(reduce(mul, compress(darr, mask)))
            mask.rotate(-1)
        return min(res), max(res)

from functools import reduce
from fractions import Fraction

def index(l,x,f):
    return f((i for i,v in enumerate(l) if (v>0)==(x>0)), default=None)

def find_min_max_product(arr, k):
    if k>len(arr): return None
    if len(arr)==1: return (arr[0],arr[0])
    arr = sorted(arr, key=lambda n:(abs(n),-n))
    prod = reduce(lambda a,b: a*b, arr[-k:], 1)
    if(all((n>0)==(arr[0]>0) for n in arr)): return tuple(sorted([reduce(lambda a,b: a*b, arr[-k:], 1),reduce(lambda a,b: a*b, arr[:k], 1)]))
    if min(k,len(arr)-k)==0: return (prod,prod)
    ln,le,rn,re = [index(arr[:-k],1,max),index(arr[:-k],-1,max),index(arr[-k:],1,min),index(arr[-k:],-1,min)]
    try: antiprod = int(prod*min([Fraction(arr[l],arr[r-k]) for l,r in [(le,rn),(ln,re)] if None not in (l,r)], default=prod//next(n for n in arr[:-k] if n!=0)))
    except: antiprod = 0
    return tuple(sorted([prod,antiprod]))

def find_min_max_product(arr, k):
    
    if k>len(arr):
        return None
    
    if k==1:
        return min(arr), max(arr)
    
    if k==len(arr):
        res = eval('*'.join([str(i) for i in arr]))
        return res, res
    
    arr = sorted(arr)
    
    arr_abs = sorted([abs(i) for i in arr])
    max_abs = max(arr_abs)
    pos = len([i for i in arr if i > 0])
    pos_all = [i for i in arr if i > 0]
    neg_all = [i for i in arr if i < 0]
    neg = len([i for i in arr if i < 0])
    zer = len([i for i in arr if i == 0])

    if pos==0 and zer==0 and k%2==0:
        min_both = arr[-k:]
        max_both = arr[:k] 
        
    if pos==0 and zer==0 and k%2!=0:
        min_both = arr[:k]
        max_both = arr[-k:]
        
    if pos==0 and zer!=0 and k%2==0:
        min_both = [0]
        max_both = arr[:k]
        
    if pos==0 and zer!=0 and k%2!=0:
        min_both = arr[:k]
        max_both = [0]
        
    if neg==0 and zer==0:
        min_both = arr[:k]
        max_both = arr[-k:] 
        
    if neg==0 and zer!=0:
        min_both = [0]
        max_both = arr[-k:]  
        
    if pos!=0 and neg!=0:
        for_sort = sorted([[i, abs(i)] for i in arr], key=lambda i:i[1])
        for_sort = [i[0] for i in for_sort]

        all_pos = [i for i in for_sort if i>0]
        all_neg = [i for i in for_sort if i<0]
        
        max_pos = [i for i in for_sort[-k:] if i>0]
        max_neg = [i for i in for_sort[-k:] if i<0]
        
        for i in range(len(all_pos)-len(max_pos)):
            max_pos.insert(0,0)
            
        for i in range(len(all_neg)-len(max_neg)):
            max_neg.insert(0,0)
        
        pos_reserve = [a-b for a,b in zip(all_pos,max_pos)]
        neg_pos_reserve = [a-b for a,b in zip(all_neg,max_neg)]

        pos_reserve = [i for i in pos_reserve if not i==0]
        neg_pos_reserve = sorted([i for i in neg_pos_reserve if not i==0])
        max_pos = [i for i in max_pos if not i==0]
        max_neg = [i for i in max_neg if not i==0]
        
        max_pos_alt = [i for i in for_sort[-k:] if i>0]
        max_neg_alt = [i for i in for_sort[-k:] if i<0]

        if len(max_neg)>0 and len(max_neg)%2 and len(pos_reserve)>0:
            max_neg.pop(0)
            max_pos.append(pos_reserve[-1])
            if len(max_pos_alt)>0 and len(neg_pos_reserve)>0:
                max_pos_alt.pop(0)
                max_neg_alt.append(neg_pos_reserve[0])
        elif len(max_neg)>0 and len(max_neg)%2 and len(pos_reserve)==0:
            max_pos.pop(0)
            max_neg.append(neg_pos_reserve[0])
        elif len(max_neg)==1 and len(neg_pos_reserve)>0:
            max_pos.pop(0)
            max_neg.append(neg_pos_reserve[0])
        elif len(max_neg)==1 and len(pos_reserve)>0:
            max_neg.pop(0)
            max_pos.append(pos_reserve[0])

        
        min_pos = [i for i in for_sort[-k:] if i>0]
        min_neg = [i for i in for_sort[-k:] if i<0]

        for i in range(len(all_pos)-len(min_pos)):
            min_pos.insert(0,0)
            
        for i in range(len(all_neg)-len(min_neg)):
            min_neg.insert(0,0)
        
        neg_reserve = [a-b for a,b in zip(all_neg,min_neg)]
        pos_reserve_neg = [a-b for a,b in zip(all_pos,min_pos)]
        
        neg_reserve = sorted([i for i in neg_reserve if not i==0])
        pos_reserve_neg = [i for i in pos_reserve_neg if not i==0]
        
        pos_reserve_neg_alt = pos_reserve_neg
        
        min_pos = [i for i in min_pos if not i==0]
        min_neg = [i for i in min_neg if not i==0]

        min_pos_alt = [i for i in for_sort[-k:] if i>0]
        min_neg_alt = [i for i in for_sort[-k:] if i<0]

        if not len(min_neg)%2:
            if len(min_neg_alt)>0 and len(pos_reserve_neg_alt)>0:
                min_neg_alt.pop(0)
                min_pos_alt.append(pos_reserve_neg_alt[-1])
            try:
                min_neg.append(neg_reserve[0])
                min_pos.pop(0)
            except:
                try:
                    min_neg.pop(0)
                    min_pos.append(pos_reserve_neg[-1])
                except:
                    pass
                
        elif not len(min_neg)%2 and 0 in arr:
            min_neg.append(0)

        max_both = max_pos+max_neg
        max_both_alt = max_pos_alt+max_neg_alt
        
        min_both = min_pos+min_neg
        min_both_alt = min_pos_alt+min_neg_alt
         
    mn = eval('*'.join([str(i) for i in min_both]))
    mx = eval('*'.join([str(i) for i in max_both]))
    
    try:
        mx_alt = eval('*'.join([str(i) for i in max_both_alt]))
    except:
        mx_alt = -10**1000
         
    try:
        mn_alt = eval('*'.join([str(i) for i in min_both_alt]))
    except:
        mn_alt = 10**1000
        
    
    return min(mn,mn_alt), max(mx,mx_alt)

from operator import mul
from itertools import accumulate

def A(li): return list(accumulate(li, mul))

def find_min_max_product(arr, k):
    if len(arr) < k:return
    
    arr = sorted(arr)[::-1]
    positive = [i for i in arr if i > 0]
    negative = [i for i in arr if i <= 0][::-1]
    neg, pos = A(negative), A(positive) 
    
    maximum = get(pos, neg, A(arr), [], max, k)
    minimum = get(pos, A(negative[::-1]), A(arr[::-1]), neg, min, k)
    
    return (minimum, maximum)

def get(pm, nm, tm, nm1, func, k):
    return func([func([nm[i] * pm[k - i - 2]] + ([nm1[i] * pm[k - i - 2]] if nm1 else [])) for i in range(len(nm)) if  0<=k-i-2<len(pm)]
               +[func(i[k - 1] for i in [pm, nm, tm, nm1] if k - 1 < len(i))])

import random, math

# even if k is on the order of n, the average case is O(n)
# worst case is O(n^2)
def find_min_max_product(arr, k):
    if k < 1 or k > len(arr) or len(arr) == 0:
        return None
    
    # get k largest values (by absolute value)
    # and also construct a list of all the other values
    k_vals, other_vals = partition_around_k(arr, k, True)
        
    largest_product = 1
    smallest_positive_k_val = None
    smallest_negative_k_val = None
    # single loop through arr, so still O(n)
    for num in k_vals:
        # calculate the largest possible product by absolute value
        largest_product *= num
        # get the smallest positive and smallest negative values in k_vals
        if num > 0 and (smallest_positive_k_val == None or num < smallest_positive_k_val):
            smallest_positive_k_val = num
        if num < 0 and (smallest_negative_k_val == None or num > smallest_negative_k_val):
            smallest_negative_k_val = num
    
    # min and max are the same
    if k == len(arr):
        return largest_product, largest_product
    
    # if the largest product was positive: now find the largest negative product
    # if the largest product was negative: now find the largest positive product
    other_min_or_max = negate_product(arr, largest_product, smallest_negative_k_val, smallest_positive_k_val, other_vals)

    # if there was no way to flip the sign, instead find the smallest product by absolute value
    if other_min_or_max == None:
        # this mirrors the logic above, except with the seek_largest param flipped
        k_vals, other_vals = partition_around_k(arr, k, False)
        smallest_product = 1
        for num in k_vals:
            smallest_product *= num
        other_min_or_max = smallest_product

    # always return the min followed by max
    if largest_product > other_min_or_max:
        return other_min_or_max, largest_product
    else:
        return largest_product, other_min_or_max

# find the other min or max by flipping one of its factors from positive to negative or vice versa
def negate_product(arr, largest_product, smallest_negative_k_val, smallest_positive_k_val, other_vals):
    other_min_or_max = None
    need_min = largest_product > 0
    negate_removed = None
    positive_removed = None
    if smallest_negative_k_val != None:
        negate_removed = largest_product // smallest_negative_k_val
    if smallest_positive_k_val != None:
        positive_removed = largest_product // smallest_positive_k_val
    
    # single loop through arr, so still O(n)
    for num in other_vals:
        # calculate new possible product
        if num >= 0 and negate_removed != None:
            product = negate_removed * num
        elif num <= 0 and positive_removed != None:
            product = positive_removed * num
        else:
            continue
        
        # update the min or max
        if other_min_or_max == None:
            other_min_or_max = product
            continue
        is_product_better = product < other_min_or_max if need_min else product > other_min_or_max
        if is_product_better:
            other_min_or_max = product
            
    return other_min_or_max

# find k-th largest element, by distance from zero
# average case O(n), worst case is O(n^2)
def quick_select_absolute_k(arr, k, seek_largest):
    # base cases
    if len(arr) == 1:
        return arr[0]
    if k == 1:
        return find_absolute_extreme(arr, seek_largest)
    
    pivot_index = pick_pivot_index(arr, 0, len(arr) - 1)
    smaller = []
    larger = []
    same = []
    for num in arr:
        if abs(num) < abs(arr[pivot_index]):
            smaller.append(num)
        elif abs(num) > abs(arr[pivot_index]):
            larger.append(num)
        else:
            if seek_largest:
                larger.append(num)
            else:
                smaller.append(num)
            same.append(num)
    
    # everything remaining is duplicates
    if len(same) == len(arr):
        return arr[0]
    
    preferred_array = larger if seek_largest else smaller
    other_array = smaller if seek_largest else larger
    if len(preferred_array) >= k:
        return quick_select_absolute_k(preferred_array, k, seek_largest)
    else:
        return quick_select_absolute_k(other_array, k - len(preferred_array), seek_largest)

# change to median-of-medians to improve worst case from O(n^2) to O(n)
def pick_pivot_index(arr, min, max):
    return random.randint(min, max)
    
def find_absolute_extreme(arr, seek_largest):
    extreme = None
    for num in arr:
        if extreme == None:
            extreme = num
        elif seek_largest and abs(extreme) < abs(num):
            extreme = num
        elif not seek_largest and abs(extreme) > abs(num):
            extreme = num
    return extreme

def partition_around_k(arr, k, seek_largest):
    k_val = quick_select_absolute_k(arr, k, seek_largest)
    k_vals = []
    k_val_copies = []
    other_vals = []
    # single loop through arr, so still O(n)
    for num in arr:
        if abs(num) > abs(k_val):
            if seek_largest:
                k_vals.append(num)
            else:
                other_vals.append(num)
        elif abs(num) < abs(k_val):
            if seek_largest:
                other_vals.append(num)
            else:
                k_vals.append(num)
        else:
            k_val_copies.append(num)
    
    # handling for duplicates
    remainder = k - len(k_vals)
    for i in range(remainder):
        k_vals.append(k_val_copies[i])
    for i in range(remainder, len(k_val_copies)):
        other_vals.append(k_val_copies[i])
    
    return k_vals, other_vals

from functools import reduce
from typing import List, Optional, Tuple

def find_min_max_product(arr: List[int], kpi: int) -> Optional[Tuple[int, int]]:

    if kpi <= len(arr):
        mul = []
        arr.sort()
        for _ in range(kpi):
            mul.append(reduce(lambda x, y: x * y, arr[0:kpi], 1))
            mul.append(reduce(lambda x, y: x * y, arr[-kpi:], 1))
            arr = [arr[-1]] + arr[:-1]
        return min(mul), max(mul)
    return None