Run length increasing solution

Complete the Run length increasing exercise before reviewing the solution.

Review the Run length increasing solution with AP CS Tutor Brandon Horn.

Runs.java

public static boolean runLengthIncreasing(int[] arr)
{
    int almostRunLength = 0;
    int almostMaxRunLength = 0;
    
    for(int i = 1; i < arr.length; i++)
    {
        if(arr[i - 1] == arr[i])
        {
            almostRunLength++;
            
            // We already know this is a real run.
            
            if(i == arr.length - 1 || arr[i + 1] != arr[i])
            {
                if(almostRunLength > almostMaxRunLength)
                    almostMaxRunLength = almostRunLength;
                else
                    return false;
            }
        }
        else
            almostRunLength = 0;
    }
    
    return true;
}

The loop traverses arr from left to right as required. The loop skips the first element to allow comparison of consecutive elements without going out of bounds (arr[i - 1] and arr[i]).

almostRunLength stores 1 less than the actual length of the run that includes arr[i], or 0 if arr[i] is not the second or subsequent element of a run. (almostRunLength doesn’t include the first element of the run.)

almostMaxRunLength stores 1 less than the length of the longest known run, or 0 if a run has not yet been encountered.

The condition arr[i - 1] == arr[i] evaluates to true if arr[i] is the second or subsequent element of a run. almostRunLength is incremented for the second and subsequent element of each run. If arr[i] is not the second or subequent element of a run, almostRunLength is set to 0 to await the next run.

The condition i == arr.length - 1 || arr[i + 1] != arr[i] evaluates to true if arr[i] is the last element of a run. If arr[i] is the last element of the run and the length of that run is > almostMaxRunLength, the max length is updated. If the length of the run is <= almostMaxRunLength, the method stops and returns false since the run is not strictly longer than the longest previously known run.

The method returns true if execution proceeds past the loop. If none of the run lengths are not strictly longer, than all of the run lengths are strictly longer. (If the opposite of a condition is known to be false, the condition is true.)

This solution handles the end of each run in the body of the outermost if. It is possible to handle the end of each run in the outermost else; however, this requires a special case outside the loop to handle a run that ends at arr.length - 1.

This is a variation of finding the minimum or maximum. The maximum is updated each time a longer run is found.

It is also possible to solve this problem by storing the immediately preceeding run length (instead of the maximum); however, the implementation is nearly identical. The immediately preceeding run length is the maximum so far or the method would have returned false earlier.

Comments

Comment on Run length increasing exercise