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

Reset to default
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\$ Commented Dec 24, 2015 at 23:50
  • \$\begingroup\$ thanks, man! You are really smart and wise guy! Thanks a lot!:) \$\endgroup\$ Commented 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\$ Commented 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\$ Commented Dec 25, 2015 at 0:50
  • \$\begingroup\$ Oh, I see. Okay, it would work. But still, a O(n) time solution is possible. \$\endgroup\$ Commented Dec 25, 2015 at 0:52

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.