Array Majorant

using System;
using System.Collections.Generic;

class ArrayMajorant
{
    static int[] arrayMajorant(int[] array)
    {
        //Contain the number of different elements.
        int numberOfDifferentElements = 0;
        //First, allocate an array of size equal to the array we get.
        //Every index will be pointer to another array with 2 indices.
        //The first [0] will contain the number and the second [1] will contain its frequency.
        int[][] lengthOfElements = new int[array.Length][];
        for (int i = 0, length = array.Length; i < length; i++)
        {
            bool dontExist = true;
            for (int j = 0; j < numberOfDifferentElements; j++)
            {
                if (array[i] == lengthOfElements[j][0])
                {
                    lengthOfElements[j][1]++;
                    dontExist = false;
                }
            }
            //if current number do not exist
            if (dontExist)
            {
                lengthOfElements[numberOfDifferentElements] = new int[] { array[i], 1 };
                numberOfDifferentElements++;
            }
        }
        //Let's find the largest number
        int biggestIndex = 0;
        for (int i = 0; i < numberOfDifferentElements; i++)
        {
            if (lengthOfElements[biggestIndex][1] < lengthOfElements[i][1])
            {
                biggestIndex = i;
            }
        }
        return lengthOfElements[biggestIndex];
    }

    static int[] arrayMajorantDictionary(int[] array)
    {
        Dictionary<int, int> lengthOfElements = new Dictionary<int, int>();
        for (int i = 0, length = array.Length; i < length; i++)
        {
            if (lengthOfElements.ContainsKey(array[i]))
            {
                lengthOfElements[array[i]]++;
            }
            else
            {
                lengthOfElements.Add(array[i], 1);
            }
        }
        int maxKey = array[0];
        foreach (var number in lengthOfElements)
        {
            if (number.Value > lengthOfElements[maxKey])
            {
                maxKey = number.Key;
            }
        }
        return new int[] { maxKey, lengthOfElements[maxKey] };
    }

    static void Main()
    {
        int[] array = { 4, 1, 1, 4, 2, 3, 4, 4, 1, 2, 4, 9, 3};
        //With Dictionary:
        //int[] majorantDictionary = arrayMajorantDictionary(array);
        //Console.WriteLine("{0} ({1} times)", majorantDictionary[0], majorantDictionary[1]);
        //With Arrays:
        int[] majorant = arrayMajorant(array);
        Console.WriteLine("{0} ({1} times)", majorant[0], majorant[1]);
    }
}