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?