current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 7 down vote favorite

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)\$?

share|improve this question
up vote 8 down vote accepted

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

share|improve this answer
1  
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) – Simon Forsberg♦ Dec 24 '15 at 23:50
    
@SimonForsbergMcFeely Indeed. Thank you. – Dmitry Dec 24 '15 at 23:56
    
thanks, man! You are really smart and wise guy! Thanks a lot!:) – StepUp Dec 25 '15 at 18:02
up vote 2 down vote

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;
        }
    }
share|improve this answer
up vote -3 down vote

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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