2
\$\begingroup\$

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))
\$\endgroup\$
12
  • \$\begingroup\$ please add a link to original statement of the problem. \$\endgroup\$
    – juvian
    Jun 19, 2018 at 2:24
  • \$\begingroup\$ I'm not sure I can do that as it's from a copyrighted site. Suffice it to say the problem is to find the sum of the maximum value of all subarrays of an array of integers. \$\endgroup\$
    – Paul K
    Jun 19, 2018 at 3:00
  • \$\begingroup\$ seems like a common problem: geeksforgeeks.org/largest-sum-contiguous-subarray \$\endgroup\$
    – juvian
    Jun 19, 2018 at 5:37
  • \$\begingroup\$ That's a different problem. That finds the subarray with the largest sum. I am looking for the sum of the maximum values in each possible subarray. \$\endgroup\$
    – Paul K
    Jun 19, 2018 at 6:07
  • 1
    \$\begingroup\$ Do this: when you look at the right, consider numbers lower or equal but when you look at the left, you only consider lower numbers. That way you dont repeat calculating and dont have to consider those special cases. This ends up being O(n) if you implement it right \$\endgroup\$
    – juvian
    Jun 19, 2018 at 22:45

1 Answer 1

1
\$\begingroup\$

Here is my implementation, a bit shorter code wise but follows same principle:

arr = [4, 1, 4]

def getHigherElementForEachIndex(arr, allowEqual):
    to_right = [0] * len(arr)
    stack = []

    for idx, num in enumerate(arr):
        if len(stack) == 0:
            stack.append(idx)
        elif num < arr[stack[-1]] or (allowEqual and num == arr[stack[-1]]):
            stack.append(idx)
        else:
            while len(stack) > 0 and ((allowEqual and num > arr[stack[-1]])  or (not allowEqual and num >= arr[stack[-1]])):
                idx2 = stack.pop()
                to_right[idx2] = idx
            stack.append(idx)   

    while len(stack) > 0:
        idx2 = stack.pop()  
        to_right[idx2] = len(arr)

    return to_right 

to_right = getHigherElementForEachIndex(arr, True)
to_left = list(reversed([len(arr) - x - 1 for x in getHigherElementForEachIndex(list(reversed(arr)), False)]))


sol = 0

for idx in range(0, len(arr)):
    sol += arr[idx] * (idx - to_left[idx]) * (to_right[idx] - idx)

print(sol)
\$\endgroup\$
2
  • \$\begingroup\$ This isn't a codereview, but an alternative solution. Would you mind adding some explanation of why you've chosen to solve the problem as you did? \$\endgroup\$ Jun 20, 2018 at 6:48
  • \$\begingroup\$ @яүυк its the same solution as OP, but he uses 2 stacks (1 for indexes and 1 for values) while I just use 1 (the index one). And I refactored the method to take array as argument so I do one pass to the right and 1 to the left, while OP did both at same time. However to handle equal values it was necessary to have different behavior for both runs, so thats another reason I do them separately. \$\endgroup\$
    – juvian
    Jun 20, 2018 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.