Arithemtic Slices Solution - Leetcode
Understand Arithmetic Slices(413 Leetcode) With Brute Force and Optimal Solution
This document presents the solution to the problem 413 - Arithmetic Slices - Leetcode.
Note: Make sure to go through the code comments as well. It’ll help you understand the concept better.
A sequence of numbers 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, these are arithmetic sequences:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The following sequence is not arithmetic.
1, 1, 2, 5, 7
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 the 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.
Example:
A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
Let’s start with a brute force approach for the input
input = []int{
1, 2, 3, 4, 5, 9, 10, 12, 14, 16
}
This animation shows the progress of the loop for a brute force solution. The number at the top shows the count of all the arithmetic slices that have been counted. The green areas show the found arithmetic slices.
So, What are we doing in a brute force approach? We’re
- Starting with an element at index i.
- We check if the current element and the next 2 elements(i + 1 and i+2) can become an arithmetic slice.
- If yes then we increment the counter and check if the next element can be added in the arithmetic slice. For example,
we increment the counter after finding
1, 2, 3, and then move to4. - We repeat the 3rd step until we find an element that cannot be added into our current arithmetic slice. For example,
after finding the 1st arithmetic slice,
1, 2, 3, we add4and5to it. Then we find9that cannot be added into the current slice, so we stop there. - If we find an element that cannot be added to the slice then we move to the i + 1 index and restart from the step 1.
Please do provide some comments if you find the explanation a bit lacking.
Now that we’ve discussed the brute force approaches, what optimizations can we bring in this brute force approach?
- We start from 1 then we move to 2 and 3 and them to make our 1st Arithmetic Slice, and then we move to 4 and 5 and increase the count.
- The moment we encounter 9, we discard the current arithmetic slice, 1,2,3,4,5, and restart from 2. But the slices starting from 2 are already there in this arithmetic slice, i.e., 2,3,4 and 2,3,4,5.
- There are 3 arithmetic slices starting from 1
1, 2, 3, 4, 51, 2, 3, 41, 2, 3
- And, if we remove 1 then the remaining slices will be:
2, 3, 4, 52, 3, 43, 4, 5
- 2 slices starting from 2
2, 3, 4, 52, 3, 4
- 1 slice starting from 3
3, 4, 5
- So, the total number of slices is 6, 3 starting from 1, 2 starting from 2, and 1 starting from 3.
- Maybe, you’ve found the pattern here.
- That the number of arithmetic slices is
6=>3 + 2 + 1=>n + (n-1) + .. + 1=>n + sum of n -1 natural numbers
Here is the function to find the very first arithmetic slice starting from the index from:
// findNextArithmeticSlice return the starting index of the very encountered arithmetic slice.
// Along with that it also returns difference between the two elements.
func findNextArithmeticSlice(arr []int, from int) (int, int, bool) {
for i := from; i < len(arr); i++ {
curr := arr[i]
next := curr
next2 := curr
if i+1 < len(arr) {
next = arr[i+1]
} else {
return 0, 0, false
}
if i+2 < len(arr) {
next2 = arr[i+2]
} else {
return 0, 0, false
}
if next-curr == next2-next {
return i, next - curr, true
}
}
return 0, 0, false
}
This function is used by the function numberOfArithmeticSlices to get the very next slice from the current position.
Once found then it finds total width of the arithmetic slice starting from the current index and then performs the sum
of natural numbers to get the results.
func numberOfArithmeticSlices(A []int) int {
from := 0
totalNumOfArithmeticSlices := 0
for {
intoLoop := false
numOfArithmeticSlices := 0
start, diff, ok := findNextArithmeticSlice(A, from)
if !ok {
return totalNumOfArithmeticSlices
}
numOfArithmeticSlices++
for j := start + 3; j < len(A); j++ {
intoLoop = true
if A[j]-A[j-1] == diff {
numOfArithmeticSlices++
} else {
from = j - 1
break
}
if j == len(A)-1 {
from = len(A) - 2
}
}
if numOfArithmeticSlices > 1 {
numOfArithmeticSlices += (numOfArithmeticSlices - 1) * (numOfArithmeticSlices) / 2
}
totalNumOfArithmeticSlices += numOfArithmeticSlices
if !intoLoop {
return totalNumOfArithmeticSlices
}
}
}
The entire program is available here on GitHub as well.
