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\$
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\$
  • 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\$ – Simon Forsberg Dec 24 '15 at 23:50
  • \$\begingroup\$ thanks, man! You are really smart and wise guy! Thanks a lot!:) \$\endgroup\$ – StepUp Dec 25 '15 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\$
  • 1
    \$\begingroup\$ The result returned are the difference of the indexes. Sorting the array would swap the indexes. \$\endgroup\$ – Simon Forsberg Dec 24 '15 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 '15 at 0:50
  • \$\begingroup\$ Oh, I see. Okay, it would work. But still, a O(n) time solution is possible. \$\endgroup\$ – Simon Forsberg Dec 25 '15 at 0:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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