<413> Arithmetic Slices

Posted on Edited on In Views:

Description

Question: A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], …, A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Leetcode link: 413. Arithmetic Slices

Quick Sum-up:

  • Input: an array
  • Output: a number indicating valid arithmetic slices

Idea

We can observe that the result of an array with k elements depends on whether the difference of k^th and (k-1)^th element is the same as the difference of its previous k-1 elements. If they are same, the number of previous result should be considered again in the join with k^th element, plus a newly generated (k-2, k-1, k) slice. Otherwise, we don’t have to consider previous results. That’s what variable “dp” does. => Pass, 44ms

Test cases

Input Expected Output
board=[] 0
board=[1,2] 0
board=[1,2,3] 1
board=[1,2,3,4] 3

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} A
 * @return {number}
 */
var numberOfArithmeticSlices = function(A) {
    if (A.length < 3)
        return 0
    
    let dp = 0
    let sum = 0
    
    for (let i = 2; i < A.length; i++) {
        if (A[i]-A[i-1] == A[i-1]-A[i-2]) {
            dp++
            sum += dp
        } else {
            dp = 0
        }
    }
    
    return sum
};