1
\$\begingroup\$

I am trying to print longest consecutive element in sorted array for that I have written following brute force algorithm

void Main()
{
    var arr = new[] { 1, 2, 4, 5, 6 ,7,8,10,11,12};

    int max = 0;
    int count = 1;
    int startIndex = 0;
    int start=0;
    int endIndex=0;
    for (int i = 0; i < arr.Length - 2; i++)
    {
        startIndex = i;
        while (i<arr.Length-1 && Math.Abs(arr[i] - arr[i + 1]) == 1)
        {
            i++;
            count++;
        }
        if (max < count)
        {
            max=count;
            start=startIndex;
            endIndex=i;
            count=1;

        }



    }
    for (int k = start; k <= endIndex; k++)
    {
        Console.WriteLine(arr[k]);

    }
}

I need some review comments on my solution( I don't want optimize solution)

\$\endgroup\$
5
  • \$\begingroup\$ @Paparazzi: I have verified the result for some random array elements and it's giving the expected result \$\endgroup\$ Sep 22, 2017 at 11:25
  • \$\begingroup\$ This does give the correct answer var arr = new[] { 1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 16 }; \$\endgroup\$
    – paparazzo
    Sep 22, 2017 at 11:36
  • \$\begingroup\$ You are right. It's giving wrong result 9,10,11 \$\endgroup\$ Sep 22, 2017 at 11:38
  • \$\begingroup\$ Where is the bug ? \$\endgroup\$ Sep 22, 2017 at 11:38
  • \$\begingroup\$ I told you once and you replied it is giving the expected result. \$\endgroup\$
    – paparazzo
    Sep 22, 2017 at 15:20

3 Answers 3

4
\$\begingroup\$

I'm assuming in real production the values aren't hard coded and will be passed in. Then you will want to make some guard clauses. What is the array is empty or value of one?

You also have more variables than you need, which isn't so bad just still if you know the start and the length of the run you don't need end position. You can also move startofrun inside the loop. Also better naming of variable would help.

You don't need to do math.abs when dealing with ints. Just add one and see if the next one is the same value.

Also while it's legal in C# to increase the for loop counter it's not intuitive to someone coming after you. I would recommend both of them being while loops since the control variable is changing in the loop

For a reference a method like this. I took out the printing as that's not what this method is intended for

static IEnumerable<int> LongestStreak(params int[] values)
{
    // guard clauses
    if (values == null)
    {
        return Enumerable.Empty<int>();
    }

    // If zero or one then return it right away
    if (values.Length <= 1)
    {
        return values;
    }

    int currentPosition = 0;
    int currentLongestRun = 0;
    int startOfLongestRun = 0;
    while (currentPosition < values.Length - 2)
    {
        int startOfRun = currentPosition;
        while (currentPosition < values.Length - 1 &&
               values[currentPosition] + 1 == values[currentPosition + 1])
        {
            currentPosition++;
        }

        if (currentPosition - startOfRun > currentLongestRun)
        {
            startOfLongestRun = startOfRun;
            currentLongestRun = currentPosition - startOfRun;
        }
        // move to check next sequence
        currentPosition++;
    }

    // C# zero based array so need to add one to the streak
    int[] result = new int[currentLongestRun + 1];
    Array.Copy(values, startOfLongestRun, result, 0, currentLongestRun + 1);
    return result;

}
\$\endgroup\$
1
  • \$\begingroup\$ A single loop would be simpler. Still nice answer. \$\endgroup\$
    – paparazzo
    Sep 22, 2017 at 15:22
2
\$\begingroup\$

You are not resetting count when max >= count

You are making this harder than it needs to be

static List<int> LongestSequence(List<int> Sequence)
{
    if (Sequence == null || Sequence.Count == 0)
        Sequence = new List<int>() { 1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 16 };

    List<int> longestSequence = new List<int>();
    List<int> currentSequence = new List<int>() { Sequence[0] };

    for (int i = 0; i < Sequence.Count - 1; i++)
    {
        if (Sequence[i] + 1 == Sequence[i + 1])
        {
            currentSequence.Add(Sequence[i + 1]);
        }
        else
        {
            if(currentSequence.Count > longestSequence.Count)
            {
                longestSequence = new List<int>(currentSequence);
            }
            if(longestSequence.Count > Sequence.Count - i)
            {
                break;
            }
            currentSequence.Clear();
            currentSequence.Add(Sequence[i]);
        }
    }

    return longestSequence;
}
\$\endgroup\$
1
  • \$\begingroup\$ yes i like this approach much better than using while loops - which i prefer to avoid \$\endgroup\$
    – BenKoshy
    Sep 23, 2017 at 2:14
1
\$\begingroup\$

Some ideas / Suggestions

  • Use methods to make algorithm more readable. (see refactored code).
  • Some variables are unneeded.
  • Use more appropriate and precise names.
  • The assigning of temporary variables mixed with "permanent" variables is a little confused. You keep a variable outside the loop yet treat it as a temporary variable.

See an example of the refactored code here:

https://gist.github.com/BKSpurgeon/fc58f85015d0f4b81da0a206358dd314

(Sorry but formatting was come out horrible which was why i was forced to put it in a gist).

Hope that helps.

The main program:

private static void Main(string[] args)
    {
        var arr = new[] { 1, 2, 4, 5, 6, 7, 8, 10, 11, 12 };
        // we want to find the
        int longestConsequtiveStreak = 0; // and also
        int startIndexOfLongestStreak = 0;
        int endIndexOfLongestStreak = 0;

        // let's loop through the array to find the longest streak
        for (int i = 0; i < arr.Length - 2; i++)
        {
            // reset current variables
            int currrentStartIndex = i;
            int currentStreak = 1;

            while (theNextNumberIsConsequtive(arr, i))
            {
                i++;
                currentStreak++; // add to the streak
            }

            if (WeHaveALongerStreak(longestConsequtiveStreak, currentStreak))
            {// Then we should
                ResetAllVariables(ref longestConsequtiveStreak, ref startIndexOfLongestStreak, ref endIndexOfLongestStreak, i, currrentStartIndex, ref currentStreak);
            }
        }

        PrintStreak(arr, startIndexOfLongestStreak, endIndexOfLongestStreak);
    }

The helping methods:

    private static bool theNextNumberIsConsequtive(int[] arr, int i)
    {
        return i < arr.Length - 1 && IsTheNextNumberConsequtive(arr, i);
    }

    private static void PrintStreak(int[] arr, int startIndexOfLongestStreak, int endIndexOfLongestStreak)
    {
        for (int k = startIndexOfLongestStreak; k <= endIndexOfLongestStreak; k++)
        {
            Console.WriteLine(arr[k]);
        }
    }

    private static void ResetAllVariables(ref int longestConsequtiveStreak, ref int startIndexOfLongestStreak, ref int endIndexOfLongestStreak, int i, int currrentStartIndex, ref int currentStreak)
    {
        longestConsequtiveStreak = currentStreak;
        startIndexOfLongestStreak = currrentStartIndex;
        endIndexOfLongestStreak = i;
        currentStreak = 1;
    }

    private static bool WeHaveALongerStreak(int longestConsequtiveStreak, int currentStreak)
    {
        return longestConsequtiveStreak < currentStreak;
    }

    private static bool IsTheNextNumberConsequtive(int[] arr, int i)
    {
        return Math.Abs(arr[i] - arr[i + 1]) == 1;
    }
\$\endgroup\$

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