Why is the LeetCode showing incorrect results?
Maksim Burtsev
1801

Hello everybody.

When solving problems, I noticed that LeetCode does not correctly evaluate code performance. For example, let’s take today's challenge. After I Submit. My result:
image
Oh well. I thought probably someone made it even cooler. I looked at two results better than mine ... How can this be faster? My solution is O (n), their solutions are O (n ^ 2). I decided performance on my own:

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApp7
{
    class Program
    {
        static void Main(string[] args)
        {
            var count = 10_000_000;

            // #0 ----------
            var sol_my = new SolutionMy();
            var sw = Stopwatch.StartNew();

            for (var i = 0; i < count; ++i)
            {
                sol_my.NumJewelsInStones("aA", "aAAbbbb");
            }

            Console.WriteLine(sw.ElapsedMilliseconds);

            // #1 -----------
            var sol1 = new Solution1();
            sw = Stopwatch.StartNew();

            for (var i = 0; i < count; ++i)
            {
                sol1.NumJewelsInStones("aA", "aAAbbbb");
            }

            Console.WriteLine(sw.ElapsedMilliseconds);

            // #2 -----------
            var sol2 = new Solution2();
            sw = Stopwatch.StartNew();

            for (var i = 0; i < count; ++i)
            {
                sol2.NumJewelsInStones("aA", "aAAbbbb");
            }

            Console.WriteLine(sw.ElapsedMilliseconds);

            Console.ReadLine();
        }
    }

    public class SolutionMy
    {
        public int NumJewelsInStones(string J, string S)
        {
            var result = 0;
            Span<bool> table = stackalloc bool[256];

            for (var i = 0; i < J.Length; ++i)
            {
                table[(int)J[i]] = true;
            }

            for (var i = 0; i < S.Length; ++i)
            {
                if (table[(int)S[i]])
                {
                    result++;
                }
            }

            return result;
        }
    }

    public class Solution1
    {
        public int NumJewelsInStones(string J, string S)
        {
            int count = 0;
            for (int i = 0; i < S.Length; i++)
            {
                if (J.Contains(S[i]))
                {
                    count++;
                }

            }

            return count;
        }
    }

    public class Solution2
    {
        public int NumJewelsInStones(string J, string S)
        {

            if (string.IsNullOrEmpty(J) || string.IsNullOrEmpty(S))
                return 0;

            HashSet<char> jewel = new HashSet<char>();

            int jewelCount = 0;

            for (int i = 0; i < J.Length; i++)
            {
                jewel.Add(J[i]);
            }
            for (int i = 0; i < S.Length; i++)
            {
                if (jewel.Contains(S[i]))
                {
                    jewelCount++;
                }
            }
            return jewelCount;
        }
    }
}

Result is:
234
450
2078
Just in case, let me remind you that such code needs to be run without a debugger in the release build. As you can see, my code works at least two times faster. This state of affairs kills the competitive spirit and demotivates me personally. I think LeetCode needs to do something about it.

Comments (6)