C# with Dictionary, why is my solution too slow?


  • 0
    H

    I thought this would be fast enough, but if k is a large number like 10000, it still needs to compare pretty much everything in the dictionary. Is there a way to speed this up?

    public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t)
            {
                Dictionary<int, long> dic = new Dictionary<int, long>();
    
                // Key = place in nums[], Value = actualy integer
                for (int i = 0; i < nums.Count(); i++)
                {
                    if (i > k) 
                        dic.Remove(i - k - 1);
    
                    if (dic.Any(x => Math.Abs(x.Value - nums[i]) <= t))
                        return true;
    
                    dic.Add(i, nums[i]);
                }
    
                return false;
            }

  • 0
    L

    Expensive time cost on that linq code


  • 0
    J

    C# with Dictionary, why is my solution too "slow"?
    Because Dictionary is "Fast" (having time complexity O(1)) when you search for an item by key. but here what you did is that you iterate the values of the Dictionary (dic.Any()) causing a time complexity of O(n) which is "slow".


Log in to reply
 

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