LC-0413 Medium LeetCode

413. Arithmetic Slices

Array Dynamic Programming Sliding Window

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 65% Topics: Array, Dynamic Programming, Sliding Window

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Sliding Window 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        res, i = 0, 0
        while i+2 < len(A):
            start = i
            while i+2 < len(A) and A[i+2] + A[i] == 2*A[i+1]:
                res += i - start + 1
                i += 1
            i += 1

        return res

Solution from kamyu104/LeetCode-Solutions · MIT