Arithmetic Slices

We iterate through the array and identify contiguous subarrays that form arithmetic sequences with at least three elements.

Here’s a step-by-step guide to implementing this:

Initialize a variable count to store the number of arithmetic slices and length to store the length of the current arithmetic slice.
Iterate through the array starting from index 1, checking the difference between consecutive elements.
If the difference between the current element and the previous element is the same as the difference in the last step, increase the length of the current arithmetic slice.
If the difference changes, calculate the number of arithmetic slices within the current slice and add it to the count. Reset the length of the current arithmetic slice.
Return the count.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        count = 0
        length = 0

        for i in range(1, len(nums)):
            # Check if the current difference is the same as the previous one
            if i >= 2 and nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]:
                length += 1
            else:
                # If the difference changes, calculate the count of slices for the current arithmetic slice
                count += (length * (length + 1)) // 2
                length = 0

        # Add slices for the last arithmetic slice if there is one
        count += (length * (length + 1)) // 2

        return count

This code iterates through the nums array once, so the time complexity is O(n), where n is the length of the array. The space complexity is O(1), as we are using only a constant amount of extra space.

[]

i = 0 i = 1 (subarray size = 3) [1, 2, 3] [2, 3, 4]

[1,2,3,4] (subarray size = 4)

[1, 2, 3, 4] x x x

[1,1,2,4,4]

Fill out the following sections:

Define the Terms Arithmetic Slice

Numbers must be in sequence
These numbers must have the same difference
At least 3 elements

1, 3, 5, 7, 9 This has a difference of 2 for all elements which are next to each other.

We can 0 as the difference

3, -1, -5, -9

-1-3 = -4 -5-(-1) = -4 -9-(-5) -4

The difference can be 0, negative or positive.

1, 1, 2, 5, 7

The first two elements give us 0 difference The second and third elements give us 1 as the difference We can immediately return

Define the Interface Input: array of integers Output: integer (0 or more) Return the number of arithmetic slices in the array A.

Example 0: What if we have 1 or 2 elements in the input array We return 0 This is implicit from the problem statement. 0
[1, 2, 3, 4]

UoW Find the diff between the two given numbers. This is WRONG Unit of Decomposition 3 elements => To find the diff and check if they are the same. Increment the counter if the diff is the same Should the recursive call consider three elements or four elements in the next call? Increment the index and make the recursive call counter is a variable that needs to be shared across the recursive calls

Consider all the possible subsets of a specific size from specific index. Start from index 0, with size 3, 4 and so on…

Recursive Approach

DP Top Down : Start from big to small / small to big is possible Bottom Up : Start from small to big

Recursion + memoization : Top down DP Iteration + memoization : Bottom Up DP (use values in DP table)

Analyze the Input and Output

Identify the Invariants

Difference must be the same for all elements in the AS

Identify the constraints

Search the Problem Space number of … (counting)

Classify the Problem

Counting Problem Combinatorics => DP

Analyze the Examples

We can have the entire array itself an AS
We could have several 3 element subarray as AS
Seems like a sliding window Initial size is 3 It can grow if we have more than 3 elements

Solve the Problem by Hand To form all the possible slices of atleast size 3, I need a start index and end index. Just because we need two pointers, does not mean we will need a 2-D array for DP approach What decides whether the dp array is 1D or 2D? ????

Identify the overlapping subproblems

Identify the state (i, j)

[1, 2, 3, 4] [1, 2, 3] [2, 3, 4]

Describe the Pattern

Brute Force Approach

Analyze Time and Space Complexity

Time: O( ) Space: O( )

Outline the Solution

Key Takeaways

i
[1, 2, 3, 4] 0 1 2 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def wrapper(a, i)
  if (i < 2)
     return 0
  end

  output = 0

  if (a[i] - a[i-1] == a[i-1] - a[i-2])
#      We just found one AS
      output = 1 + wrapper(a, i-1)
#  increment the counter here
      @count += output
  else
     wrapper(a, i-1)
  end

   return output
end

# @param {Integer[]} a
# @return {Integer}
def number_of_arithmetic_slices(a)
    @count = 0
    wrapper(a, a.size-1)
    @count
end

[]