Programming Puzzle: Arithmetic Subsequences

Sam Berg, Mon May 30 2022 • project leetcode

As someone who's long struggled with technical interviews at elite companies, I've wanted to get better at solving small, challenging programming problems. Dynamic programming problems have been particularly hard for me, so I've been practicing those lately and settled into a bit of a groove, solving many problems successfully with my first implementation.

Then came Leetcode # 413, "Arithmetic Slices"...

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.

I actually solved this one on the first try, but my solution was in the bottom 5% of time complexity. If I'm not in the top 75% I try to optimize my solution. In this article I'll show what I did to get my algorithm to perform better than 95% of the other submissions.

For the rest of this article, when I say "subsequence" I mean "arithmetic subsequence."

Approach I: Mindless Memoization (O(n²) Time complexity)

On my first attempt I did the usual and solved some examples using my big wet human brain. This helps me see whether there are any patterns that I can put into my algorithm.

[1,2,3] -> 1
[1,2,3,4] -> 3
[1,2,3,4,5] -> 6
[1,2,3,4,5,6] -> 10
[1,2,3,5,7] -> 2
[1,2,3,5,8,9,10,11] -> 4

The first thing worth noticing is that the number of sequences in a given array of length N is a function of the number of sequences in the subarrays within that array. So, f([1,2,3,4]) depends on f([1,2,3]), Since we have a situtation where an answer can be derived from one or more subproblems, this suggests we could find a solution using dynamic programming,

As is typical with DP, I wanted to save (memoize) answers to subproblems so that I don't have to recompute their answers. I decided to create a two-dimensional array, memo, that would map each subarray to a number of subsequences. Next I need to find the base cases, which here is when N < 4. If an array has fewer than 3 elements, it definitelty doesn't contain a subsequence (which requires at least three elements). And if an array has three elements then it can contain 0 or 1 subsequences.

So I created a table of what I wanted the memoization to look like for an example. The rows and columns specify the start and end indices (respectively) of subarrays.

Since the start must be equal to or less than the end, only half the table needs to be filled.

Example:

[1,2,3,4,6,8]

Memoization Entry

memo_2,5 = subsequences(array_2,5)

subsequences(array_2,5) = subsequences([3,4,6,8]) = 1
[3,4,6,8] contains the one subsequence, [4,6,8]

Memoization Table


	0	1	2	3	4	5
0	0	0	1	3	3	4
1		0	0	0	1	2
2			0	0	0	1
3				0	0	1
4					0	0
5						0

Okay, great, now how do I create this table with a program? I know that I can start with the base cases, filling in all table entries for subarrays with fewer than four elements. But then need to figure out how to use those base cases.

Finding A Pattern

Let's take one example. Let's say for the example array [1,2,3,4,6,8] we want to find subsequence(arr<sub>0,3</sub>). We're then looking at the subarray [1,2,3,4].

4 is part of the new subsequences [2,3,4] and [1,2,3,4] so we found two new subsequences which we'll add to subsequence(arr_0,2)=1. So memo_0,3=1+2=3.

If we find a new subsequence member it could either be the first subsequence found for a range or append to an existing subsequence. If it's a new one, we've found 1 new subsequence of length 3. If we're adding to an existing subsequence then we've found a new subsequence of length end-start plus a new subsequence for every subsequence of length 3 to end-start-1.

As we iterate through the subarrays, we will find one of three scenarios in each iteration:

We find a non-arithmetic sequence: memo_start,end = memo_start,end-1
We find a new sequence:
memo_start,end = 1 + memo_start,end-1
We add to an existing sequence: new_sequences_found_last_iteration = memo_start,end-1 - memo_start,end-2 memo_start,end = 1 + new_sequences_found_last_iteration + memo_start,end-1 // equivilent memo_start,end = 1 + 2*memo_start,end-1 - memo_start,end-2

All we have left now is figuring out how to check for those three cases. We know a given element is the last element of if memo_{element-2,element} == 1. That's the 2^nd case down. The third case is actually trivial. If we're not adding to an existing subsequence, then new_sequences_found_last_iteration == 0, so this case is actually accounted for in the math. Programatically, there are only two cases:

We find a non-arithmetic sequence
We find a new sequence

Implementation

class Solution {

    public int numberOfArithmeticSlices(int[] nums) {
        if(nums.length < 3) return 0;

        int[][] memo = new int[nums.length][nums.length];

        // memoize all 1,2 and 3 length subarrays
        for(int i=0; i<nums.length; i++) {            
            memo[i][i]=0;
            if(i<nums.length-1) memo[i][i+1] = 0;
            if(i<nums.length-2) {                
                if(nums[i+2] - nums[i+1] == nums[i+1] - nums[i]) {                    
                    memo[i][i+2] = 1;                
                }                
            }
        }        

        for(int i=0; i<nums.length; i++) {
            for(int j=i+3; j<nums.length; j++) {
                if(memo[j-2][j] == 0) {
                    memo[i][j] = memo[i][j-1];
                } else {
                    memo[i][j] = 1 + memo[i][j-1] - memo[i][j-2] + memo[i][j-1];
                }
            }
        }        

        return memo[0][nums.length-1];
    }
}

Approach II: Splitting the Problem (O(n) Time complexity)

The above program has to look at every subarray of the given input array. But is this really necessary? All we need to do is find the subsequences in the array and then compute the number of nested subsequences within those.

So we can divide this task into two pieces:

Find the longest subsequences in the array
Sum the number of nested subsequences in each subsequence

This approach was pretty tricky. It took a while to get the bugs out of the method that finds the subsequences (slices).

Step 1

private int expandSequence(int[] nums, int end) {
     int start = end-2;
     int magicDiff = nums[end-1] - nums[end-2];            

     while(end < nums.length && nums[end] - nums[end-1] == magicDiff) {
         end++;
     }

     return end-1;
 }

private List<int[]> findSlices(int[] nums) {
    List<int[]> res = new ArrayList<>();

    int start=0, end=2;


    while(end < nums.length) {
        int magicDiff = nums[end] - nums[end-1];            

        if(magicDiff == nums[end-1] - nums[end-2]) {
            end = expandSequence(nums, end);                
            res.add(new int[] {start, end});

            end++;                
            start=end-2;
        } else {
            start = end-1;
            end = end+1;
        }

    }


    return res;
}

Step 2

private int[] computeNSubarrays(int n) {
    int[] memo = new int[n+1];
    Arrays.fill(memo, -1);
    memo[1] = 0;
    memo[2] = 0;
    memo[3] = 1;

    for(int i=4; i<=n; i++) {
        memo[i] = 2*memo[i-1] - memo[i-2] + 1;
    }

    return memo;
}

Driver

public int numberOfArithmeticSlices(int[] nums) {        
    int res = 0;
    if(nums.length < 3) return res;

    int[] memo = computeNSubarrays(nums.length);        
    List<int[]> slices = findSlices(nums);
    
    for(int[] slice : slices) {
        res += memo[slice[1]-slice[0]+1];
    }

    return res;
}