0

https://leetcode.com/problems/find-triangular-sum-of-an-array/

So I am solving this leetcode problem and have come up with the following solution

class Solution:
    def triangularSum(self, nums: List[int]) -> int:
        arrLen = len(nums)
        newArr = []

        while len(nums) != 2:
            for i in range(0, arrLen - 1):
                total = (nums[i] + nums[i + 1])
                total %= 10
                newArr.append(total)

            nums = newArr
            arrLen = len(nums)
            newArr = []
        
        res = nums[0] + nums[1]
        return res

So It passes the test case, but when I press submit I get a Time Limit Exceeded error. The details say, 1 / 300 test cases passed. STATUS: Time Limit Exceeded.

Did I do something wrong with my algorithm? Or is there some way to make it faster? I am really lost

Nin17
  • 2,821
  • 2
  • 4
  • 14
Hodala22
  • 19
  • 4
  • 1
    Problems like this often require you to figure out a mathematical trick so you don't just do all the loops, because for large input the number of loops will be too much. – Barmar Jun 21 '22 at 17:40
  • There is something wrong, but also yes, too slow. Consider nums =[8,8] – Christian Sloper Jun 21 '22 at 17:42
  • You need to use `% 10` in the final addition. – Barmar Jun 21 '22 at 17:43
  • Thanks I edited the final addition to do % 10. So I've learned about memoization before but only used it with recursion and dynamic programming. Would you recommend memoization for this? For example creating a dictionary and checking it before doing other operations? – Hodala22 Jun 21 '22 at 17:48
  • 2
    Here's a hint: The total of a row will be `nums[0] + nums[-1] + 2 * sum(nums[1:-1])`. In each iteration there will be 1 less numbers in the row. Figure out how these sums propagate through the entire computation, and figure out a closed-form formula for it. You also don't need to do `% 10` at every iteration, you can calculate the final total and then the modulus of that. – Barmar Jun 21 '22 at 17:48
  • @Barmar in the implementation I've done just doing ```%10``` at the end instead of at each iteration actually made it slower – Nin17 Jun 21 '22 at 17:56
  • @DanielHao I don't think this is related to Pascal's triangle, which is related to probability and binomial distributions. – Barmar Jun 21 '22 at 18:59
  • 1
    @Barmar it is, see my edit – Nin17 Jun 21 '22 at 19:04
  • @Barmar If that's not what you meant with your hint, then what is? – Kelly Bundy Jun 21 '22 at 19:10
  • @Nin17 I could be wrong, I'm not a math expert. – Barmar Jun 21 '22 at 19:11

2 Answers2

1

A quick search for "time limit exceeded" and leetcode gives the following result: enter link description here

With this information.

If your solution is judged Time Limit Exceeded, it could be one of the following reasons:

Your code has an underlying infinite loop. Your algorithm is too slow and has a high time complexity. The data structure you returned is in an invalid state. For example, a linked list that contains a cycle.

Think about those three things.

Dom
  • 2,980
  • 2
  • 28
  • 41
0

You can make it faster by using a list comprehension instead:

class Solution:
    def triangularSum(self, nums: List[int]) -> int:
        while len(nums) != 1:
            nums = [(nums[i]+nums[i+1])%10 for i in range(len(nums)-1)]
        return nums[0]

which gives an output of: enter image description here

Edit: Here's another method that is definitely faster:

class Solution:    
    def triangularSum(self, nums: List[int]) -> int:
        # The idea of this is similar to the Pascal's triangle. 
        # If you deconstruct graph from the first example of [1, 2, 3, 4, 5] which is 48 -> 8
        # The coefficient for each number is [1, 4, 6, 4, 1] which is equivalent of row (n-1) in Pascal's triangle

        coefs = self.getRow(len(nums) - 1)

        return sum(num*coef for num, coef in zip(nums, coefs))%10

    @staticmethod
    def getRow(rowIndex: int):
        result = 1 
        yield result
        for i in range(rowIndex, 0, -1):
            result = result * i // (rowIndex+1-i)
            yield result

which gives an output of enter image description here

Nin17
  • 2,821
  • 2
  • 4
  • 14