patternjavaMinor
Highest pit - only climbing through the pit once
Viewed 0 times
oncethepitthroughhighestonlyclimbing
Problem
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 A[P+1] > ... > A[Q];
sequence A[Q], A[Q+1], ..., A[R] is strictly increasing, i.e. A[Q] −2) and sequence [A[3], A[4]] is strictly increasing (−2
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 A[P+1] > ... > A[Q];
sequence A[Q], A[Q+1], ..., A[R] is strictly increasing, i.e. A[Q] −2) and sequence [A[3], A[4]] is strictly increasing (−2
- Are there any edge cases I did not think about?
- At an interview, would adding unit tests for this method be a good idea?
Solution
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.
(See this running with some tests in ideone)
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 = 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)
Code Snippets
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;
}Context
StackExchange Code Review Q#86150, answer score: 6
Revisions (0)
No revisions yet.