CODEWITHSUNDEEP
pythonmath
idk31909310
idk31909310

Reputation: 135

Sum of all odd length subarrays

I am trying to solve the Leetcode problem '1588. Sum of All Odd Length Subarrays'. 'Given an array of positive integers arr, return the sum of all possible odd-length subarrays of arr, where a subarray is a contiguous subsequence of the array'.

My attempt was the following:

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        sub_array_size = 1
        odd_array_sum = 0
        index = 0
        while sub_array_size <= len(arr):
            for element in arr:
                index = arr.index(element)
                if index <= (len(arr) - sub_array_size):
                    for i in range(sub_array_size):
                        odd_array_sum += arr[index + i]
                else:
                    continue
            
            sub_array_size += 2
        
        return odd_array_sum

It has worked for some test cases but failed for most, e.g. arr = [7, 6, 8, 6]. My idea was start with length = 1, increment this by 2 each time we go through the list, then while the index of the element you're on is small enough such that a sub-array of that given odd length can be made, add the elements which would be contained in that sub-array to the sum, and continue this until you find an index too large for this to be possible, then increase the length of the sub-array and start from the beginning of the list again if sub_array_size <= len(arr), otherwise stop as you can't find anymore odd-length subarrays.

Note that I think I can put 'break' instead of 'continue' to reduce run time as once the index is too large for the given element, all elements after it will have an index too large also so don't need to be checked, but just left it as continue for now as I wasn't 100% sure break wouldn't skip over 'sub_array_size += 2', but I think it wouldn't.

I can't understand where I've gone wrong and want to figure out where the error is instead of just looking up a solution online.

Upvotes: 1

Views: 185

Answers (1)

trincot
trincot

Reputation: 350270

The immediate problem is that index = arr.index(element) will not always give you the index of the iterated value. If that value has more than one occurrence, then eventually you will get a lesser index than expected.

You can correct this by iterating the index. You can for instance use enumerate and get both the index and value at the same time:

            for index, element in enumerate(arr):

This will solve the problem at hand.

But this is not a very efficient solution. If it passes the larger tests, it will rank among the slower submissions.

Instead of iterating all possible list slices (of odd length), try to find for each index, how many odd slices include that index, and then multiply the value at that index with that frequency.

Here is a spoiler that implements that idea:

def sumOddLengthSubarrays(self, arr: List[int]) -> int: n = len(arr) return sum( ( (1 + i // 2) * ((n - i + 1) // 2) + ((i + 1) // 2) * ((n - i) // 2) ) * val for i, val in enumerate(arr) )

Upvotes: 1

Related Questions