A Better Frog Crossing Algorithm

Question

I am solving the following problem from Codility:

A small frog wants to get to the other side of a river. The frog is currently located at position 0, and wants to get to position X. Leaves fall from a tree onto the surface of the river. You are given a non-empty zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in minutes. 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.

I used the following solution but only got a score of 81:

The code is in C#.

using System;
using System.Collections.Generic;

class Solution {
    public int solution(int X, int[] A) {
        bool[] tiles = new bool[X];

        for (int i = 0; i < A.Length; i++)
        {
            tiles[A[i] - 1] = true;

            bool complete = true;

            for (int j = 0; j < tiles.Length; j++)
            {
                if (!tiles[j])
                {
                    complete = false;
                    break;
                }
            }

            if (complete)
                return i;
        }

        return -1;
    }
}

My algorithm runs at O(NX). What could be a better algorithm that will only require O(N)?

Answer 1

Change your code to something like this:

public int solution(int X, int[] A) 
{
    bool[] tiles = new bool[X];
    int todo = X;

    for (int i = 0; i < A.Length; i++)
    {
        int internalIndex = A[i] - 1;
        if (internalIndex < X && !tiles[internalIndex])
        {
            todo--;
            tiles[internalIndex] = true;
        }

        if (todo == 0)
            return i;
    }

    return -1;
}

This algorithm only requires O(A.length) time, since it always keeps track of how many "holes" we still have to fill with leaves.

How is this done here?

todo is the number of leaves still required to build the "bridge" of leaves. Whenever a leaf falls down, we first check whether there not already is a leaf at the position it falls down. If not, we decrement todo, fill the hole and go on. As soon as todo reaches 0, the entire river is covered ;)