C# - minor optimization checking min/max beats 100%


  • 1

    I found that just adding a check for the min/max bounds before diving into the O(n) search shaved off quite a bit of time from the OJ timer from 350ms to 230ms (beats 100%). Of course this is only because their test cases clearly are checking for this, if they weren't it wouldn't make any difference. In any case, cost is basically none, may as well do it!

    public class TwoSum 
    {
        Dictionary<int,bool> map = new Dictionary<int,bool>();
        int max = int.MinValue;
        int min = int.MaxValue;
        
        public TwoSum() { }
        
        public void Add(int number) 
        {
            map[number] = map.ContainsKey(number);
            max = Math.Max(max, number);
            min = Math.Min(min, number);
        }
        
        public bool Find(int value) 
        {
            if (value < min + min || value > max + max) return false;
            foreach (int x in map.Keys)
            {
                int y = value - x;
                if (map.ContainsKey(y) && (x != y || map[y] == true)) return true;
            }
            return false;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.