Split list of integers at certain value efficiently

Question

I am working on a python puzzle over at codewars ( Largest Rectangle ) My solution is working for small cases but times out for the very large ones.) I think one major hit to performance is in my subroutine splitz(arr):

The purpose of this subroutine is something like string.split('X') - but for lists of integers. In my case, I will always be spllitting at the minimum value on the list, so splitz([3,3,5, 1, 5,5,5, 1, 6,5,4]) should return [[3,3,5], [5,5,5], [6,5,4]]

def splitz(iterable):
    key = (min(iterable),)
    return [list(g) for k,g in itertools.groupby(iterable,lambda x:x in key) if not k]

My code is adapted from a snippet found on Stackoverflow, and I don't understand it well enough to know how efficient it really is (or not.) It needs to efficiently deal with lists with len ~= 100,000 that could be splitting up into almost that many sublists.

Is there a better way to do this split, or do I need to find a completely different approach to solving the overall problem?

FULL CONTEXT

The overall task is to identify the largest rectangle that can be made in a grid made from stacked rows of length a[i]. So if a is [7,2,6,4,5,1] the grid looks like

0000000
00
000000
0000
00000
0

largest possible rectangle is shown in H's:

0000000
00
HHHH00
HHHH
HHHH0
0

And the routine should return 12 (=3*4)

This is my third approach. The first one was a lambda one-liner that was quite compact, but could only handle lists up to about 1000. My current solution works with long lists on my PC, (150,000 in 1.5 seconds, 1.5 million in 110 seconds) but fails on codewars. I don't know how long the longest test case is there, but the time limit is 1.2 seconds.

import itertools


def largest_rect(a):
    maxRect = 0  # This will store the result
    if len(a) == 0:
        return 0
    mina = min(a)

    # The area of a rectangle extending
    # all the way across the the current list,
    # with the maximum possible height (which is the minimum in this list)
    maxRect = len(a) * mina
    # split the current lists into sublist, dividing at the
    # value that limited the height of the previous calc
    newarrlist = splitz(a, mina)

    # Now loop through each of the lists returned when split the original
    keepTrying = True
    while keepTrying:
        tmparrlist = []
        keepTrying = False  # This will be set True if we generate a new sublist
        for thisarr in newarrlist:
            # If the enclosing dimensions of this block aren't bigger
            # than the current largest rectangle, don't bother using it.
            lenta = len(thisarr)
            if lenta * max(thisarr) > maxRect:
                minta = min(thisarr)
                maxRect = max(maxRect, minta*lenta)
                lists = splitz(thisarr, minta)
                # If splitz was given a perfect rectangle, that block is now finished.
                # Otherwise add the sublists to a temporary array.
                if len(lists) > 0:
                    tmparrlist = tmparrlist + lists
                    keepTrying = True  # We stored a sublist - we'll have to repeat

        # Once we have gone through the list of lists, reset to our temporary array
        # and try again until keepTrying = False
        newarrlist = tmparrlist
    return maxRect


# This will split a list into sublists at the minimum value on the original
def splitz(iterable, minin):  # Pass in the min value, since we already know it.
    splitters = (minin, )
    return [list(g) for k, g in itertools.groupby(iterable,lambda x:x in splitters) if not k]

Answer 1

I would use a generator:

def splitz(seq, smallest):    
    group = []    
    for num in seq:
        if num != smallest:
            group.append(num)
        elif group:
            yield group
            group = []


numbers = [1, 3, 3, 5, 1, 5, 5, 5, 1, 6, 5, 4, 1]
min_val = min(numbers)
print(list(splitz(numbers, min_val)))

It prints:

[[3, 3, 5], [5, 5, 5], [6, 5, 4]]

You could time it:

if __name__ == '__main__':
    import timeit
    print(timeit.timeit("splitz(numbers, min_val)", setup="from __main__ import splitz, numbers, min_val", number=1000000))

On my machine, it is:

1.0186186955428558

Note the default number of times through the loop is one million.

Answer 2

I suspect a simple for loop is hard to beat:

def splitz(iterable, minin):
    result = []
    group = []
    for e in iterable:
        if e == minin: # found delimiter
            if group: # ignore empty groups (delimiter at beginning or after another delimiter)
                result.append(group)
                group = [] # start new accumulator
        else: 
            group.append(e)
    if group: # Handle last group
        result.append(group)
    return result

itertools.groupby is concise, but it can't really take advantage of the knowledge that the groups are built sequentially, it deals with more general cases.

Actually, to amend my initial claim, I suspect there's a more efficient way that involves searching for the delimiter and then using a list slice.