4
\$\begingroup\$

Problem Statement: >

Given a sorted array, find the length of the longest arithmetic progression in it.

Examples: numbers = new int[]{1, 3, 4, 5, 7, 8, 9} The length is 5, and the sequence is 1, 3, 5, 7, 9 with increment 2 in each iteration.

Introduction of the algorithm

The longest arithmetic progressions algorithm can be solved using dynamic programming method. I spent several hours to study the algorithm. I read the paper called "Finding Longest Arithmetic Progressions", base on the author's introduction in the paper, the lower bound algorithm is O(nlogn) based on the algebraic decision tree model of computation. I will try to understand the lower bound algorithm later on, also I like to read the related question called Longest equally-spaced subsequence on stackoverflow.com.

Dynamic programming

The longest arithmetic progression can be found in O(n2) time using a dynamic programming algorithm similar to the following interesting subproblem , which can be called AVERAGE.

AVERAGE subproblem

It is to determine whether the input contains a three-term arithmetic progression, or equivalently, if any array element is the average of two others.

Test case analysis

I like to use a 7 x 7 matrix to define the lookup table based on the test case {1,3,4,5,7,8,9}.

Base case is to set lookup[i][n-1] = 2 for any i from 0 to n - 1.

     0 1 2 3 4 5 6
_________________________
0| 0 0 0 0 0 0 2
1| 0 0 0 0 0 0 2
2| 0 0 0 0 0 0 2
3| 0 0 0 0 0 0 2
4| 0 0 0 0 0 0 2
5| 0 0 0 0 0 0 2
6| 0 0 0 0 0 0 2

Checking out 8, found 7, 8, 9. We have lookup[4][5] = lookup[5][6] + 1. In other words, 8 is the average of 7 and 9, since 8 = (7 + 9)/ 2. This is also a simple example of AVERAGE subproblem.

     0 1 2 3 4 5 6
_________________________
0| 0 0 0 0 0 0 2
1| 0 0 0 0 0 0 2
2| 0 0 0 0 0 0 2
3| 0 0 0 0 0 0 2
4| 0 0 0 0 0 3 2
5| 0 0 0 0 0 0 2
6| 0 0 0 0 0 0 2

The idea of applying test case analysis is to tutor myself to learn how to solve the algorithm using dynamic programming method step by step, later on I can apply this technique to other dynamic programming algorithm as well.

Practice for mock interview

I was told to practice this algorithm when I practice mock interviews February 18, 2018 weekend. I wrote a C# solution based on the above test case. The algorithm is not too hard, but it is hard for me to come out the idea to define the subproblem AVERAGE the first time.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TwoPointerTechniques
{
    class Program
    {
        /// <summary>
        /// Based on the code from the following blog:
        /// https://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_22_-_Longest_arithmetic_progression.jsp
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            var sortedArr = new int[] { 1, 3, 4, 5, 7, 8, 9 };
            var n = sortedArr.Length;
            var lookup = FindArithmeticProgressionLength3(sortedArr);

            Debug.Assert(lookup[0] == 5);
        }

        /// <summary>
        /// How to find if a sorted array contains an Arithmetic Progression (AP) of length 3?
        /// </summary>
        /// <param name="numbers"></param>
        /// <returns></returns>
        public static int[] FindArithmeticProgressionLength3(int[] numbers)
        {
            var n = numbers.Length;
            var lookup = new int[n][];

            for (int i = 0; i < n; i++)
            {
                lookup[i] = new int[n];
            }

            int maxAP = 2;

            int apTerm = 0;
            int apStart = 0;

            // Any 2-letter series is an AP
            // Here we initialize only for the last column of lookup because
            // all i and (n-1) pairs form an AP of size 2  
            for (int i = 0; i < n; i++)
            {
                lookup[i][n - 1] = 2;
            }

            // Loop over the array and find two elements 'left' and 'right' such that 
            // numbers[left] + numbers[right] = 2 * numbers[middle]
            for (int middle = n - 2; middle >= 1; middle--)
            {
                var left = middle - 1;
                var right = middle + 1;

                while (left >= 0 && right <= n - 1)
                {
                    int isAP = (numbers[left] + numbers[right]) - 2 * numbers[middle];

                    if (isAP < 0)
                    {
                        right++;
                    }
                    else if (isAP > 0)
                    {
                        left--;
                    }
                    else
                    {
                        lookup[left][middle] = lookup[middle][right] + 1;

                        maxAP = Math.Max(maxAP, lookup[left][middle]);

                        if (maxAP == lookup[left][middle])
                        {
                            // Store the Arithmetic Progression's term
                            // And the start point of the AP
                            apTerm = numbers[middle] - numbers[left];
                            apStart = left;
                        }

                        right++;
                        left--;
                    }
                }
            }

            return new int[] { maxAP, apStart, apTerm };
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ One of my motivation to ask the question is to provide helpful link for the algorithm as a mock interviewer. I plan to give the algorithm to the interviewee in mock interview one day, the interviewee likes to find a good web link to look up after the mock interview. To prepare this algorithm, I still miss the optimal solution based on the time complexity O(nlogn), the dynamic programming solution is not optimal in time complexity. \$\endgroup\$ – Jianmin Chen Feb 26 '18 at 1:37
1
\$\begingroup\$

In FindArithmeticProgressionLength3 is always an array of dimension n x n. Why did you use jagged arrays instead of

var lookup = new int[n, n];

// several lines skipped ...

for (var i = 0; i < n; i++)
{
    lookup[i, n - 1] = 2;
}

As an 2-dimensional array is only one object compared to n+1 objects with the jagged array you should consider using that. And also the risk of failing to initialize the array (either to forget one of the lookup[n] to allocate or an out-of-Memory exception) is reduced to one single line of Code.

\$\endgroup\$
  • 2
    \$\begingroup\$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - From Review \$\endgroup\$ – Ben Steffan Feb 24 '18 at 21:30
  • 4
    \$\begingroup\$ @BenSteffan Actually, I think this is a perfectly valid point. While formulated as a question, it is a valid review point. \$\endgroup\$ – Simon Forsberg Feb 24 '18 at 22:40
  • 1
    \$\begingroup\$ @SimonForsberg No, I disagree. Maybe there is a valid point of reasoning behind this, but since the answer does not attempt at all to explain why their solution is preferable, I fail to see how this constitutes a valid Code Review point. Imo, the first paragraph of "What goes into an answer in "How do I write a good answer? applies here, in particular "Answers that merely provide an alternate solution with no explanation or justification do not constitute valid Code Review [...]". \$\endgroup\$ – Ben Steffan Feb 25 '18 at 14:46
  • 2
    \$\begingroup\$ @BenSteffan Seems like this answer has been fixed now which I hope brings the answer more to your liking. Although there is room for several other answers as well. \$\endgroup\$ – Simon Forsberg Feb 25 '18 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.