Earliest time frog can jump to the other side of a river in C#

Question

I'm new to C#, I programmed a little in Java in the past. I had the two previous exercises reviewed here (permCheck, cyclicRotation, with a 100% score, just like this one), and I'm applying what the accepted answers contributed to me.

Even though the site expects names like public int solution(int X, int[] A), I refactored the code after it was accepted, and applied those contributions I mentioned.

Is this how professional code should look like in terms of quality, or are there still things to improve in solutions of easy exercises like this written by me?

Task description

---

A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river.

You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds.

The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X (that is, we want to find the earliest moment when all the positions from 1 to X are covered by leaves). You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall in the river.

For example, you are given integer X = 5 and array A such that:

A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
In second 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.

Write a function:

class Solution { public int solution(int X, int[] A); }

that, given a non-empty array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.

If the frog is never able to jump to the other side of the river, the function should return −1.

For example, given X = 5 and array A such that:

A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
the function should return 6, as explained above.

Write an efficient algorithm for the following assumptions:

N and X are integers within the range [1..100,000]; each element of array A is an integer within the range [1..X].

/// <summary>
/// Check if a given array contains the integers 1..N
/// </summary>
/// <returns>
/// -1 if <paramref name="fallenLeaves"/> does not contain all integers
///     1..N, where N = <paramref name="requiredAmountOfLeaves"/>
/// a possitive int i, if the required amount of ints were present at 
///     <paramref name="fallenLeaves"/>
/// </returns>

const int FROG_CANT_JUMP_TO_THE_OTHER_SIDE = -1;

public static int GetSecondsRequired
    (int requiredAmountOfLeaves, int[] fallenLeaves)
{
    bool[] leavesAsSteps = new bool[requiredAmountOfLeaves + 1];
    int espectedSum = 0, correctSum = 0;
    for (int i = 1; i <= fallenLeaves.Length; i++)
    {
        if (i <= requiredAmountOfLeaves)
        //get summatory of 1..N
            correctSum += i;
        if (fallenLeaves[i - 1] <= requiredAmountOfLeaves &&
            !leavesAsSteps[fallenLeaves[i - 1]])
        {
        //accumulate where the expected leaf fell and set its location to true
            espectedSum += fallenLeaves[i - 1];
            leavesAsSteps[fallenLeaves[i - 1]] = true;
        }
        if (espectedSum == correctSum && i >= requiredAmountOfLeaves)
        //if all the espected leaves fell, then return the array's 
        //index where the last expected leaf was found
            return i - 1;
    }
    return FROG_CANT_JUMP_TO_THE_OTHER_SIDE;
}

Answer 1

Readability

• The code needs more spacing. Considering the comments, the indentation and the ifs, it's hard to read without some good old empty lines.

• Use brackets when using conditions, especially if you have comments above your single line, it gets really confusing. Also, the readability is increased and, the biggest factor, you'll avoid weird bugs.

• If you really don't want to use brackets, at least indent your comments so it's clear the line under it is still into the if.

• Considering that we have your explanation of the problem, we can understand pretty clearly what your variable names mean. But still... it could be improved or at least well documented. fallenLeaves doesn't represent fallen leaves, it represent when leaves are falling at which position. expectedSum and correctSum don't mean much, to a point I'm wondering if they are well initialized.

Result for now :

public static int GetSecondsRequired(int requiredAmountOfLeaves, int[] fallenLeaves)
{
    bool[] leavesAsSteps = new bool[requiredAmountOfLeaves + 1];
    int espectedSum = 0, correctSum = 0;

    for (int i = 1; i <= fallenLeaves.Length; i++)
    {
        if (i <= requiredAmountOfLeaves)
        {
            //get summatory of 1..N
            correctSum += i;
        }

        if (fallenLeaves[i - 1] <= requiredAmountOfLeaves &&
            !leavesAsSteps[fallenLeaves[i - 1]])
        {
            //accumulate where the expected leaf fell and set its location to true
            espectedSum += fallenLeaves[i - 1];
            leavesAsSteps[fallenLeaves[i - 1]] = true;
        }
    
        if (espectedSum == correctSum && i >= requiredAmountOfLeaves)
        {
            //if all the espected leaves fell, then return the array's 
            //index where the last expected leaf was found
            return i - 1;
        }
    }

    return FROG_CANT_JUMP_TO_THE_OTHER_SIDE;
}

Algorithm

• You use i - 1 everywhere but one place, it would be smarter to reverse this. Use i everywhere and i + 1 at one place.
• You use the accessor fallenLeaves[i] often, you should consider storing it in a variable. It will make the code more readable. So : int currentFallenLeaf = fallenLeaves[i];
• The usage of expectedSum and correctSum is too complicated for the problem at hand. You don't need to check the sum, only that the number of true elements in leavesAsSteps (minus one because of the zero index) equals requiredAmountOfLeaves.
• You could check right at the beginning of the loop if you already marked the "leaf step" as true and that the leaf is valid, so that you don't do useless work.

public static int GetSecondsRequired(int requiredAmountOfLeaves, int[] fallenLeaves)
{
    // You should comment why there's a + 1 here.
    bool[] leavesAsSteps = new bool[requiredAmountOfLeaves + 1];
    int numberOfFallenLeaves = 0;

    for (int i = 0; i < fallenLeaves.Length; i++)
    {
        int currentFallenLeaf = fallenLeaves[i];

        // Have we already checked this number?
        // Is the leaf number out of range?
        // If so, let's just stop right there for this leaf.
        if (currentFallenLeaf > requiredAmountOfLeaves 
            || leavesAsSteps[currentFallenLeaf])
        {
            continue;
        }

        numberOfFallenLeaves++;
        leavesAsSteps[currentFallenLeaf] = true;        

        // Have we marked all our leaves? We're done.
        if (numberOfFallenLeaves == requiredAmountOfLeaves)
        {
            return i;
        }
    }

    return FROG_CANT_JUMP_TO_THE_OTHER_SIDE;
}