Highest pit - only climbing through the pit once

Question

Problem description:

A non-empty zero-indexed array A consisting of N integers is given. A pit in this array is any triplet of integers (P, Q, R) such that:

0 ≤ P < Q < R < N;

sequence [A[P], A[P+1], ..., A[Q]] is strictly decreasing, i.e. A[P] > A[P+1] > ... > A[Q];

sequence A[Q], A[Q+1], ..., A[R] is strictly increasing, i.e. A[Q] < A[Q+1] < ... < A[R].

The depth of a pit (P, Q, R) is the number min{A[P] − A[Q], A[R] − A[Q]}.

For example, consider array A consisting of 10 elements such that:

  A[0] =  0
  A[1] =  1
  A[2] =  3
  A[3] = -2
  A[4] =  0
  A[5] =  1
  A[6] =  0
  A[7] = -3
  A[8] =  2
  A[9] =  3

Triplet (2, 3, 4) is one of pits in this array, because sequence [A[2], A[3]] is strictly decreasing (3 > −2) and sequence [A[3], A[4]] is strictly increasing (−2 < 0). Its depth is min{A[2] − A[3], A[4] − A[3]} = 2.

Triplet (2, 3, 5) is another pit with depth 3.

Triplet (5, 7, 8) is yet another pit with depth 4. There is no pit in this array deeper (i.e. having depth greater) than 4.

Imagine I would write this code at an interview. What would you say?

Time complexity: \$O(n)\$

Space complexity: \$O(n)\$

Auxiliary space complexity: \$O(1)\$

public class FindDeepestPit {

    public static void main(String[] args) {
        int[] heights = { 0, 9, 6, -2, 7, 8, 0, -3, 2, 3 };
        int result = findDeepestPit(heights);
        System.out.println(result);
    }

    private static int findDeepestPit(int[] heights) {
        int firstIndex = 0;
        int deepest = -1;
        int depth = 0;
        boolean climbingUp = false;

        /*
        * mark current position as highest (firstIndex)
        * - go to next as long as we're going down
        * - when we're not going down anymore, switch to mark us going up
        * - go up until we can't go up anymore, then save the current depth of the pit, and mark the current position as highest
        * */

        for (int i = 0; i < heights.length - 1; i++) {
            int currentHeight = heights[i];
            int nextHeight = heights[i + 1];
            // find higher point
            if (!climbingUp) { // climbing down
                if (currentHeight < nextHeight) {
                    // we can't go further down here
                    climbingUp = true;
                    deepest = i;
                }
            } else { // climbing up
                if (currentHeight > nextHeight) {
                    // we can't get further up here.
                    int lastIndex = i;
                    int depthA = heights[firstIndex] - heights[deepest];
                    int depthB = heights[lastIndex] - heights[deepest];
                    int currDepth = Math.min(depthA, depthB);
                    depth = Math.max(depth, currDepth);
                    firstIndex = i;
                    climbingUp = false;
                }
            }
        }

        int depthA = heights[firstIndex] - heights[deepest];
        int depthB = heights[heights.length - 1] - heights[deepest];
        int currDepth = Math.min(depthA, depthB);
        depth = Math.max(depth, currDepth);

        return depth;
    }
}

Primary concerns:

• Is the approach clear?
• Are there any edge cases I did not think about?
• At an interview, would adding unit tests for this method be a good idea?

Answer 1

Your code over-complicates the basic premise. The idea of having an ascending or descending element is right, but can be simplified further by just tracking maxima/minima, there is no need to track the actual index of the deepest pit.

If you identify peaks, and pits, and as you walk through the data, identify whether the current value increases the depth of the current pit, and increase the max if it does, then your code can be reduced to just a single check that identifies inflections, and another max/min check that compares depths.

private static int deepest(int[] data) {

    if (data.length < 1) {
        return 0;
    }

    int inflection = 0;
    int max = 0;
    int descent = 0;
    boolean ascending = true;
    for (int i = 1; i < data.length; i++) {
        boolean goingup = data[i] == data[i - 1] ? ascending : data[i] >= data[i - 1];
        if (goingup != ascending) {
            ascending = goingup;
            descent = ascending ? (data[inflection] - data[i - 1]) : 0;
            inflection = i - 1;
        }

        max = Math.max(max, Math.min(descent, data[i] - data[inflection]));
    }
    return max;
}

(See this running with some tests in ideone)