How many times can a list be split in a way that every element on the left is smaller than every element on the right?

user_14283186 0
Viewed 166

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?

time-complexity algorithm python
4 Answers

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

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
user_105620

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.

user_129522630

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
user_142831860
Related