Arithmetic Slices

LeetCode 413 | Difficulty: Medium

Medium

Problem Description

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

- For example, `[1,3,5,7,9]`, `[7,7,7,7]`, and `[3,-1,-5,-9]` are arithmetic sequences.

Given an integer array nums, return the number of arithmetic subarrays of nums.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: nums = [1,2,3,4]
Output: 3
Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.

Example 2:

Input: nums = [1]
Output: 0

Constraints:

- `1 <= nums.length <= 5000`

- `-1000 <= nums[i] <= 1000`

Topics: Array, Dynamic Programming, Sliding Window

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

---

Solutions

Solution 1: C# (Best: 92 ms)

Metric	Value
Runtime	92 ms
Memory	24 MB
Date	2020-03-12

Solution

public class Solution {
    public int NumberOfArithmeticSlices(int[] A) {
        if(A.Length<3) return 0;
    int[] dp = new int[A.Length];
    int sum=0;
    for (int i = 2; i < A.Length; i++)
    {
        if (A[i] - A[i - 1] == A[i - 1] - A[i - 2])
        {
            dp[i] = dp[i-1]+1;
            sum+=dp[i];
            
        }
    }
    return sum;
    }
}

📜 1 more C# submission(s)

Submission (2022-03-03) — 150 ms, 36.8 MB

public class Solution {
    public int NumberOfArithmeticSlices(int[] A) {
        if(A.Length<3) return 0;
    int[] dp = new int[A.Length];
    int sum=0;
    for (int i = 2; i < A.Length; i++)
    {
        if (A[i] - A[i - 1] == A[i - 1] - A[i - 2])
        {
            dp[i] = dp[i-1]+1;
            sum+=dp[i];
            
        }
    }
    return sum;
    }
}

---

Complexity Analysis

Approach	Time	Space
Sliding Window	$O(n)$	$O(k)$
Dynamic Programming	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.