aliakb
BAN USERHere's an adaptation of the LCS (longest common substring) algorithm. N^2.
static void FindSubarrays(int[] values, out int first, out int second, out int size)
{
var acc = new int[values.Length + 1, values.Length + 1];
size = 0;
first = -1;
second = -1;
for (int i = 0; i <= values.Length; i++)
{
for (int j = 0; j <= values.Length; j++)
{
if (i == 0 || j == 0 || values[i-1] >= values[j-1])
acc[i, j] = 0;
else
{
int maxDistance = MaxDistance(i, j);
acc[i, j] = Math.Min(acc[i - 1, j - 1] + 1, maxDistance);
if (size < acc[i, j])
{
size = acc[i, j];
first = i - size;
second = j - size;
}
}
}
}
}
static int MaxDistance(int i, int j)
{
int first = Math.Min(i, j);
int distance = Math.Abs(i - j);
return Math.Min(first, distance);
}
The question also says that all numbers are unique. That may be a key for a simpler solution, which I do not see yet.
- aliakb May 28, 2015
You can get your answer in O(log n) time using binary search. Because all numbers except one come in pairs, you can divide the whole range in half, and then deduce the half your unique number belongs to. Here's C# code for that:
- aliakb June 30, 2015