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
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?
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
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]