Skip to main content

413. Arithmetic Slices

medium

Count contiguous subarrays of length >= 3 that form arithmetic progressions. A one-pass O(1)-space DP keyed on the running streak length.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 1 <= nums.length <= 5000
  • -1000 <= nums[i] <= 1000

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If nums[i] - nums[i-1] == nums[i-1] - nums[i-2], the arithmetic streak extends.

Hint 2

Let curr = number of arithmetic slices ending at i. When the streak continues, curr = prev + 1. Otherwise curr = 0.

Hint 3

Total answer is the sum of curr over all i.

Solution approach

Reveal approach

Define curr as the number of arithmetic subarrays ending exactly at index i. When nums[i] - nums[i-1] equals nums[i-1] - nums[i-2], the arithmetic streak extends and curr = previous curr + 1 (every existing arithmetic slice ending at i-1 plus the new length-3 slice [i-2, i-1, i]). When the difference changes, reset curr = 0. The total count is the sum of curr across all i from 2 to n-1. O(n) time, O(1) space. Equivalently, find each maximal arithmetic run of length L and add L*(L-1)/2 - terms, but the running-sum form is shorter to code.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Arithmetic Slices and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →