title: A Better Frog Crossing Algorithm
body: <p>I am solving the following problem from Codility:</p>
  
  <p>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.</p>
  
  <p>I used the following solution but only got a score of 81:</p>
  
  <p>The code is in C#.</p>
  
  <pre><code>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 &lt; A.Length; i++)
          {
              tiles[A[i] - 1] = true;
  
              bool complete = true;
  
              for (int j = 0; j &lt; tiles.Length; j++)
              {
                  if (!tiles[j])
                  {
                      complete = false;
                      break;
                  }
              }
  
              if (complete)
                  return i;
          }
  
          return -1;
      }
  }
  </code></pre>
  
  <p>My algorithm runs at O(NX). What could be a better algorithm that will only require O(N)?</p>