CODEWITHSUNDEEP
python
Hodala22
Hodala22

Reputation: 19

find triangular sum of an array (leetcode question)

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

Upvotes: 0

Views: 329

Answers (2)

Nin17
Nin17

Reputation: 3492

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

Upvotes: 0

Dom
Dom

Reputation: 3100

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.

Upvotes: 1

Related Questions