Deepest Pit

C++. This is a question from Codility.

Question: 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, 1, 3, -2, 0, 1, 0, -3, 2, 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.

Write a function 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, consider array A consisting of 10 elements such that:

A = { 0, 1, 3, -2, 0, 1, 0, -3, 2, 3 }

the function should return 4, as explained above.

Assume that:

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]

Solution: Approaching it like x-y coordinate would make it easy, and sweeping from the beginning to the end on x axis would give the all possible pits. While sweeping, the model algorithm stores the detected pits into a container. Then, it sorts them in order. Finally, it returns the last one from the container.

#include <iostream>
#include <vector>
#include <algorithm>

int DeepestPit(std::vector<int> const & _dataSet);

int main()
{
	std::vector<int> const dataSet = { 0, 1, 3, -2, 0, 1, 0, -3, 2, 3 };

	//You can try other data sets for testing examples, for instance;
	//std::vector<int> dataSet = { 0, -1, -4, -2, -2, -1, 10, 0, 2, 1 };

	std::cout << "The result is " << DeepestPit(dataSet) << std::endl;

	return 0;
}

int DeepestPit(std::vector<int> const & _dataSet)
{
	int const N = _dataSet.size();
	
	if (N < 3) return -1;

	std::vector<int> pitStore;
	int P(0), Q(0), R(0);

	int const lastIndex = N - 2;
	for (int i = 0; i < lastIndex; ++i)
	{
		if (_dataSet[i] >= _dataSet[i + 1])
		{
			P = _dataSet[i];
			for (i; i < lastIndex; ++i)
			{
				while (_dataSet[i + 1] < _dataSet[i])
				{
					Q = _dataSet[i + 1];
					i++;
				}
				break;
			}
			i++;
			
			R = _dataSet[i];
			pitStore.push_back(std::min(P - Q, R - Q));
			while (_dataSet[i] < _dataSet[i + 1])
			{
				R = _dataSet[i + 1];
				pitStore.push_back(std::min(P - Q, R - Q));
				i++;
				
				if (i == N - 1) break;
			}
			i--;
		}
		else
		{
			while (_dataSet[i] > _dataSet[i + 1])
			{
				P = _dataSet[i];
				i++;
			}
		}
	}
	std::sort(pitStore.begin(), pitStore.end());

	if (pitStore.empty()) return -1;

	return pitStore.back();
}

#include <iostream>

#include <vector>

#include <algorithm>

int DeepestPit(std::vector<int> const & _dataSet);

int main()

{

std::vector<int> const dataSet = { 0, 1, 3, -2, 0, 1, 0, -3, 2, 3 };

//You can try other data sets for testing examples, for instance;

//std::vector<int> dataSet = { 0, -1, -4, -2, -2, -1, 10, 0, 2, 1 };

std::cout << "The result is " << DeepestPit(dataSet) << std::endl;

return 0;

}

int DeepestPit(std::vector<int> const & _dataSet)

{

int const N = _dataSet.size();

if (N < 3) return -1;

std::vector<int> pitStore;

int P(0), Q(0), R(0);

int const lastIndex = N - 2;

for (int i = 0; i < lastIndex; ++i)

{

if (_dataSet[i] >= _dataSet[i + 1])

{

P = _dataSet[i];

for (i; i < lastIndex; ++i)

{

while (_dataSet[i + 1] < _dataSet[i])

{

Q = _dataSet[i + 1];

i++;

}

break;

}

i++;

R = _dataSet[i];

pitStore.push_back(std::min(P - Q, R - Q));

while (_dataSet[i] < _dataSet[i + 1])

{

R = _dataSet[i + 1];

pitStore.push_back(std::min(P - Q, R - Q));

i++;

if (i == N - 1) break;

}

i--;

}

else

{

while (_dataSet[i] > _dataSet[i + 1])

{

P = _dataSet[i];

i++;

}

std::sort(pitStore.begin(), pitStore.end());

if (pitStore.empty()) return -1;

return pitStore.back();

}