-
Notifications
You must be signed in to change notification settings - Fork 15
/
LargestPit.java
63 lines (60 loc) · 2.09 KB
/
LargestPit.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package by.andd3dfx.numeric;
/**
* For given array of heights find the largest pit
*/
public class LargestPit {
/**
* Given an Array A of integers, here is one way to look for the depth bestDepth of the deepest pit (P,Q,R) using a
* variable status to know in every iteration where we are in the pit: going up or down. status will contain one the
* values ‘P’ then ‘Q’ then ‘R’.
*
* According to: https://www.quora.com/What-is-the-algorithm-for-finding-the-deepest-pit-in-an-array
*/
public static int find(int[] heights) {
if (heights.length < 3) {
return 0;
}
int bestDepth = -1;
int currMinDepth = 0;
int P = heights[0];
int Q = heights[0];
int R = heights[0];
int status = 'P';
int i = 0;
while (i < heights.length - 1) {
if (heights[i] > heights[i + 1]) {
if (status == 'R') {
currMinDepth = Math.min(P - Q, R - Q);
if (currMinDepth > 0 && currMinDepth > bestDepth) {
bestDepth = currMinDepth;
}
P = heights[i];
}
Q = heights[i + 1];
status = 'Q';
i++;
continue;
} else if (heights[i + 1] > heights[i]) {
if (status == 'Q' || status == 'R') {
R = heights[i + 1];
i++;
status = 'R';
if (i == heights.length - 1) {
currMinDepth = Math.min(P - Q, R - Q);
if (currMinDepth > bestDepth) {
bestDepth = currMinDepth;
}
}
continue;
}
if (status == 'P') {
P = heights[i + 1];
i++;
continue;
}
}
i++;
}
return bestDepth;
}
}