For example if the list is: [2,1,2,5,7,6,9] there's 3 possible ways of splitting:
[2,1,2] [5,7,6,9]
[2,1,2,5] [7,6,9]
[2,1,2,5,7,6] [9]
I'm supposed to calculate how many times the list can be split in a way that every element on the left is smaller than every element on the right. So with this list, the output would be 3.
Here's my current solution:
def count(t):
c= 0
for i in range(len(t)):
try:
if max(t[:i]) < min(t[i:]):
c+=1
except:
continue
return c
The above code does the right thing, but it's not of O(n) time complexity. How could I achieve the same result, but faster?
Compute all prefix maxima and suffix minima in linear time. And combine them in linear time.
from itertools import accumulate as acc
from operator import lt
def count(t):
return sum(map(lt,
acc(t, max),
[*acc(t[:0:-1], min)][::-1]))
Jacques requested a benchmark:
1444.6 ms Jacques_Gaudin
5.0 ms Kelly_Bundy
1424.5 ms Jacques_Gaudin
4.4 ms Kelly_Bundy
1418.2 ms Jacques_Gaudin
4.7 ms Kelly_Bundy
Code (Try it online!):
from timeit import timeit
from itertools import accumulate as acc
from operator import lt
def Kelly_Bundy(t):
return sum(map(lt,
acc(t, max),
[*acc(t[:0:-1], min)][::-1]))
def Jacques_Gaudin(t):
if not t: return 0
v, left_max = list(t), max(t)
c, right_min = 0, left_max
while (item := v.pop()) and v:
if item == left_max:
left_max = max(v)
if item < right_min:
right_min = item
if left_max < right_min:
c += 1
return c
funcs = [
Jacques_Gaudin,
Kelly_Bundy,
]
t = list(range(12345))
for func in funcs * 3:
time = timeit(lambda: func(t), number=1)
print('%6.1f ms ' % (time * 1e3), func.__name__)
My answer turned out to be very similar to kelly's above - we both calculate the mins and maxs for valid split points then check the condition on each split.
I'm around +50% slower than Kelly's as it's not fully functional as Kelly's is.
from itertools import accumulate as acc
from typing import List
def paddy3118(lst: List[int]) -> int:
# min of RHS for any split
min_from_r = list(acc(lst[::-1], min))[::-1]
# max of LHS for any split
max_from_l = list(acc(lst, max))
# Condition for valid split
return sum(max_from_l[split] < min_from_r[split+1]
for split in range(len(lst) - 1))
The following function can generate interesting test data, (try count == swap for larger count arguments):
def _gen_swap(count, swaps):
ans = list(range(count))
for i in range(swaps):
s = random.randint(0, count - 2)
ans[s], ans[s+1] = ans[s+1], ans[s]
return ans
my attempt:
def count(t):
max_el = t[0]
min_el = min(t[1:])
res = 0
for i in range(len(t)-1):
if t[i] == min_el:
min_el = min(t[i+1:])
if max_el < t[i]:
max_el = t[i]
if max_el < min_el:
res +=1
return res
Pretty straightforward, only compute the max/min if it could be different.