7
\$\begingroup\$

If I am not mistaken, this method has a complexity \$O(N^2)\$:

int[] exampleArray = { 4, 6, 2, 2, 6, 6, 1, 55, 55, 2, 5, 6, 90, 8, 8, 8, 10, 70 };
int k = GetMaximumCycle(exampleArray);

public static int GetMaximumCycle(int[] anArray)
{
   int length = anArray.Length;
   int result = 0;
   for (int i = 0; i < length; i++)
   {
      for (int j = 0; j < length; j++)
      {
          if (anArray[i] == anArray[j])
          {
             if (!(result > Math.Abs(i - j)))                            
                 result = Math.Abs(i - j);
          }                    
      }                
   }
   return result;
}

I compare values and gets the maximum difference between items of array. The result variable is 10.

And if an input array is very large, this code works slowly. Is it possible to simplify the for loops or remove the second for loop to have a complexity of \$O(N)\$?

\$\endgroup\$
0

3 Answers 3

8
\$\begingroup\$

You can use a Dictionary<int, int> of positions of the first occurrence of each element value. Next, iterating over all elements of the input array, you do:

  • If the positions[value] is empty, store the current index i in it: positions[value] = i.
  • Else, calculate the distance (or cycle length).
  • If this distance is greater than maximum, save it as a new maximum.

This algorithm has time complexity \$O(n)\$.

The code:

public static class CycleSearch
{
    public static int GetMaximumCycle(int[] array)
    {
        Dictionary<int, int> positions = new Dictionary<int, int>();

        int result = 0;
        for (int i = 0; i < array.Length; i++)
        {
            int value = array[i];
            int position;
            if (!positions.TryGetValue(value, out position))
            {
                positions[value] = i;
            }
            else
            {
                int cycleLength = i - position;
                if (cycleLength > result)
                {
                    result = cycleLength;
                }
            }
        }
        return result;
    }
}

Usage:

int[] exampleArray = { 4, 6, 2, 2, 6, 6, 1, 55, 55, 2, 5, 6, 90, 8, 8, 8, 10, 70 };
Console.WriteLine(CycleSearch.GetMaximumCycle(exampleArray));

Output:

10

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You don't need to create an entire array that covers the full range of values for this, you could use a Dictionary (a.k.a. hash map) \$\endgroup\$ Dec 24, 2015 at 23:50
  • \$\begingroup\$ thanks, man! You are really smart and wise guy! Thanks a lot!:) \$\endgroup\$
    – StepUp
    Dec 25, 2015 at 18:02
2
\$\begingroup\$

There is no real reason why your method should be restricted to array and int. You can make it easily generic (the below code is based on @Dmitry`s answer):

    public static class CycleSearch
    {
        public static int GetMaximumCycle<T>(IEnumerable<T> sequence)
        {
            var positions = new Dictionary<T, int>();

            int result = 0;
            int index = 0;
            foreach (var value in sequence)
            {
                int position;
                if (!positions.TryGetValue(value, out position))
                {
                    positions[value] = index;
                }
                else
                {
                    int cycleLength = index - position;
                    if (cycleLength > result)
                    {
                        result = cycleLength;
                    }
                }
                index += 1;
            }
            return result;
        }
    }
\$\endgroup\$
-3
\$\begingroup\$

You are correct, it is \$O(n^2)\$.

I seriously doubt it is possible to reduce time complexity to \$O(n)\$, however there is a solution with \$O(n\log n)\$ time and \$O(n)\$ space complexity: sort the set of (value, index) pairs, and obtain the result in a single linear pass.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ The result returned are the difference of the indexes. Sorting the array would swap the indexes. \$\endgroup\$ Dec 24, 2015 at 23:48
  • \$\begingroup\$ @SimonForsbergMcFeely I am afraid you didn't pay attention. I suggested to sort the pairs, so each element keeps its original index along. \$\endgroup\$
    – vnp
    Dec 25, 2015 at 0:50
  • \$\begingroup\$ Oh, I see. Okay, it would work. But still, a O(n) time solution is possible. \$\endgroup\$ Dec 25, 2015 at 0:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.