##DeepestPit - problem description

Complexity:

· expected worst-case time complexity is O(M);

· expected worst-case space complexity is O(M), beyond input storage (not counting the storage required for input arguments).

My solution, as follows, gets a task score of 100% (100% for correctness and 100% for performance). (A previous version only got 26%, with 44% correctness and 0% performance.)

DeepestPit - problem description

Complexity:

• expected worst-case time complexity is O(M);
• expected worst-case space complexity is O(M), beyond input storage (not counting the storage required for input arguments).

My solution, as follows, gets a task score of 100% (100% for correctness and 100% for performance).

Following is a problem description from a Codility test, as a task in an interview. Posting the problem verbatim may be a copyright breach, so I've modified it to avoid that.

DeepestPit - problem description

A non-empty zero-indexed array B consisting of M integers is given. A pit in this array is any triplet of integers (X, Y, Z) such that:

· 0 ≤ X < Y < Z < M;

· sequence [B[X], B[X+1], ..., B[Y]] is strictly decreasing,
i.e. B[X] > B[X+1] > ... > B[Y];

· sequence B[Y], B[Y+1], ..., B[Z] is strictly increasing,
i.e. B[Y] < B[Y+1] < ... < B[Z].

The depth of a pit (X, Y, Z) is the number min{B[X] − B[Y], B[Z] − B[Y]}.

Complexity:

Following is based on a problem description from a Codility test, as a task in an interview.

##DeepestPit - problem description

A non-empty zero-indexed array B consisting of M integers is given. A pit in this array is any triplet of integers (X, Y, Z) such that:

• 0 ≤ X < Y < Z < M
• sequence [B[X], B[X+1], ..., B[Y]] is strictly decreasing, i.e. B[X] > B[X+1] > ... > B[Y]
• sequence B[Y], B[Y+1], ..., B[Z] is strictly increasing, i.e. B[Y] < B[Y+1] < ... < B[Z]

The depth of a pit (X, Y, Z) is the number min{B[X] − B[Y], B[Z] − B[Y]}.

Complexity:

Following is a problem description from a Codility test, as a task in an interview. Posting the problem verbatim is a copyright breach, so I'll modify it.

· 0 ≤ X < Y < Z < 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.

function solution(A)

that, given a non-empty zero-indexed array A consisting of N integers, returns the depth of the deepest pit in array A. The function should return −1 if there are no pits in array A.

For example, for the above array A, the function should return 4, as explained above.

• N is an integer within the range [1..1,000,000];

• each element of array A is an integer within the range [−100,000,000..100,000,000].

Write an efficient algorithm for the function.

· expected worst-case time complexity is O(N);

· expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

function solution(A) {
 // write your code in JavaScript (Node.js 8.9.4)
 var n = A.length,
 depth = -1;
 if (n < 3) {
 return depth;
 }
 var p, q, r;
 var i = 0, j, k;
 while (i < n - 2) {
 p = A[i];
 // console.log("i = ", i, "p = ", p)
 j = i + 1;
 while (A[j] < A[j - 1] && j < n - 1) {
 j++;
 }
 if (j === i + 1) {
 i++;
 continue;
 }
 j = j - 1;
 q = A[j];
 // console.log("i = ", i, "q = ", q)
 k = j + 1;
 while (A[k] > A[k - 1] && k < n) {
 k++;
 }
 if (k === j + 1) {
 i++;
 continue;
 }
 k = k - 1;
 r = A[k];
 depth = Math.max(depth, Math.min(p - q, r - q));
 // console.log("depth is", depth)
 i++;
 }
 return depth;
}

Edit: I have edited the while loops to check the previous element (j-1 and k-1, not q and r, respectively). I think this will work now.

Following is a problem description from a Codility test, as a task in an interview. Posting the problem verbatim may be a copyright breach, so I've modified it to avoid that.

· 0 ≤ X < Y < Z < M;

· sequence [B[X], B[X+1], ..., B[Y]] is strictly decreasing,
i.e. B[X] > B[X+1] > ... > B[Y];

· sequence B[Y], B[Y+1], ..., B[Z] is strictly increasing,
i.e. B[Y] < B[Y+1] < ... < B[Z].

The depth of a pit (X, Y, Z) is the number min{B[X] − B[Y], B[Z] − B[Y]}.

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

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

Triplet (2, 3, 4) is one of pits in this array, because sequence [B[2], B[3]] is strictly decreasing (7 > −4) and sequence [B[3], B[4]] is strictly increasing (−4 < 0). Its depth is min{B[2] − B[3], B[4] − B[3]} = 4. Triplet (2, 3, 5) is another pit with depth 8. Triplet (5, 7, 8) is yet another pit with depth 10. There is no pit in this array deeper (i.e. having depth greater) than 10.

function deepest_pit(B)

that, given a non-empty zero-indexed array B consisting of M integers, returns the depth of the deepest pit in array B. The function should return −1 if there are no pits in array B.

For example, for the above array B, the function should return 10, as explained above.

Write an efficient algorithm for the function.

• M is an integer within the range [1..1,000,000];

• each element of array B is an integer within the range [−100,000,000..100,000,000].

· expected worst-case time complexity is O(M);

· expected worst-case space complexity is O(M), beyond input storage (not counting the storage required for input arguments).

function deepest_pit(B) {
 // write your code in JavaScript (Node.js 8.9.4)
 var M = B.length,
 depth = -1;
 if (M < 3) {
 return depth;
 }
 var X, Y, Z;
 var i = 0, j, k;
 while (i < M - 2) {
 X = B[i];
 // console.log("i = ", i, "X = ", X)
 j = i + 1;
 while (B[j] < B[j - 1] && j < M - 1) {
 j++;
 }
 if (j === i + 1) {
 i++;
 continue;
 }
 j = j - 1;
 Y = B[j];
 // console.log("i = ", i, "Y = ", Y)
 k = j + 1;
 while (B[k] > B[k - 1] && k < M) {
 k++;
 }
 if (k === j + 1) {
 i++;
 continue;
 }
 k = k - 1;
 Z = B[k];
 depth = Math.max(depth, Math.min(p - Y, Z - Y));
 // console.log("depth is", depth)
 i++;
 }
 return depth;
}