This is the crux of a problem found on one of those code challenge sites.
I'm fairly new to programming and this was a difficult challenge. I've attempted to solve this with stacks and calculating totals on the fly. I think this is pretty close to O(n). With the exception of values repeated without a larger value between them, all values are handled one time. (Please school me if I'm mistaken!!)
Is there a more efficient way to achieve this? I have seen a few sorta solutions involving tree structures, but none seem to handle multiple values very well, if at all.
What can I improve overall? I've been staring at this for a while. Does it make sense?
Okay, on to the problem:
The sum of maximum values for all subarrays of an integer array can be found, of course, by generating and iterating through each possible subarray and adding the maximum to a running total. It's slow.
So it works out that for any given value in an array, the number of positions to the right of that value that are less than or equal to that value plus 1, can be multiplied by the number of positions to the left (plus 1) that maintain that condition to determine the number of subarrays where that value represents the maximum.
For example:
a = [1, 2, 4, 3]
rights = {1:1, 2:1, 4:2, 3:1}
lefts = {1:1, 2:2, 4:3, 3:1}
total_subarrays = {1:1, 2:2, 4:6, 3:1}
And then just sum the products of key, value pairs to get your total.
Multiple values without a larger value in between are handled differently to account for subarrays in which both values occur.
Here's my stab:
from random import randint
def get_left(lefts, x, y):
"""Sets number of positions to the left of value that occur befor a larger value + 1."""
if lefts.get(x):
lefts[x].append(y)
else:
lefts[x] = [y]
return lefts
def get_right(rights, x, y):
"""Sets number of positions to the right of value that occur befor a larger value + 1."""
if rights.get(x):
rights[x].append(y)
else:
rights[x] = [y]
return rights
def get_multi_right(rights, multiples, x, i, keep=None):
"""Sets number of positions to right for repeated values without a larger value between."""
rights[x] = [0] * len(multiples[x])
for place in multiples[x]:
rights[x][place[1]] = i - place[0]
if not keep:
del(multiples[x])
return rights
def get_total(lefts, rights, x):
"""Returns total of value * number of subarrays value is maximum."""
total = x * lefts[x][0] * rights[x][0]
del(rights[x])
del(lefts[x])
return total
def get_multi_total(lefts, rights, x):
"""Returns total of value * number of subarrays value is maximum minus number of subarrays where value the
is repeated."""
frequency = 0
for left, right in zip(lefts[x], rights[x]):
frequency += left * right
for i in range(1, len(lefts[x])):
frequency -= lefts[x][i - 1] * rights[x][i]
total = x * frequency
del(rights[x])
del(lefts[x])
return total
def is_multiple(multiples, x, i, j):
"""Saves position of repeated values to later set rights."""
if multiples.get(x):
multiples[x] = *multiples[x], (i, len(multiples[x]))
elif not multiples.get(x):
multiples[x] = (j, 0), (i, 1)
return multiples
def do_the_thing(a):
"""Number of positions to the left of values are set as they are pushed to stack. Number of positioins to the right
are set as they are poppped. Totals are calculated once a value's number of positions to the right is calculated."""
total = 0
value, position = [], []
rights, lefts, multiples = {}, {}, {}
for i, x in enumerate(a):
if not value:
value.append(x)
position.append(i)
get_left(lefts, x, i + 1)
elif x < value[-1]:
get_left(lefts, x, i - position[-1])
value.append(x)
position.append(i)
elif x == value[-1]:
temp_pos = position.pop()
is_multiple(multiples, x, i, temp_pos)
if position:
get_left(lefts, x, i - position[-1])
else:
get_left(lefts, x, i + 1)
position.append(i)
elif x > value[-1]:
while value and x >= value[-1]:
temp_value = value.pop()
temp_pos = position.pop()
if x == temp_value:
is_multiple(multiples, x, i, temp_pos)
if not value:
get_multi_right(rights, multiples, temp_value, i + 1, keep=True)
else:
if multiples.get(temp_value):
get_multi_right(rights, multiples, temp_value, i)
total += get_multi_total(lefts, rights, temp_value)
else:
get_right(rights, temp_value, i - temp_pos)
total += get_total(lefts, rights, temp_value)
if value:
get_left(lefts, x, i - position[-1])
else:
get_left(lefts, x, i + 1)
value.append(x)
position.append(i)
while value:
temp_value = value.pop()
temp_pos = position.pop()
if not multiples.get(temp_value):
get_right(rights, temp_value, len(a) - temp_pos)
if multiples.get(temp_value):
get_multi_right(rights, multiples, temp_value, len(a))
total += get_multi_total(lefts, rights, temp_value)
else:
total += get_total(lefts, rights, temp_value)
return total
# a = [1, 2, 4, 3]
a = [randint(-10000, 10000) for _ in range(13500)]
print(do_the_thing(a))
