How many times can a list be split in a way that every element on the left is smaller than every ele-CodePudding

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?

CodePudding user response：

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__)

CodePudding user response：

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.

CodePudding user response：

Here's my final answer:

def count(t):
    c = 0
    maxx = max(t)
    right = [0]*len(t)
    left = [0]*len(t)
    maxx = t[0]
   
    for i in range(0, len(t)):
    
        if maxx >= t[i]:
            left[i] = maxx
            
        if maxx < t[i]:
            maxx = t[i]
            left[i] = maxx
             
    minn = t[-1] 
    for i in range(len(t)-1,-1,-1):
        if minn <= t[i]:
            right[i] = minn
            
        if minn > t[i]:
            minn = t[i]
            right[i] = minn
           
    for i in range(0, len(t)-1):
        if left[i] < right[i 1] :
            c  = 1
 
    return c