*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!*

Source: codewars | Difficulty: EASY
Tags: Data structures

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

def find_min_max_product(arr, k):
	if k < 1 or k > len(arr) or len(arr) == 0:
		return None
	(k_vals, other_vals) = partition_around_k(arr, k, True)
	largest_product = 1
	smallest_positive_k_val = None
	smallest_negative_k_val = None
	for num in k_vals:
		largest_product *= num
		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
	if k == len(arr):
		return (largest_product, largest_product)
	other_min_or_max = negate_product(arr, largest_product, smallest_negative_k_val, smallest_positive_k_val, other_vals)
	if other_min_or_max == None:
		(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
	if largest_product > other_min_or_max:
		return (other_min_or_max, largest_product)
	else:
		return (largest_product, other_min_or_max)

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
	for num in other_vals:
		if num >= 0 and negate_removed != None:
			product = negate_removed * num
		elif num <= 0 and positive_removed != None:
			product = positive_removed * num
		else:
			continue
		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

def quick_select_absolute_k(arr, k, seek_largest):
	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)
	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)

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 = []
	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)
	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