C# O(n) solution, only one for-loop


  • 1
    Z

    Type long is used in case the subtraction result rolls over the maximum or under the minimum for integers.

    public class Solution {
        public int[] TwoSum(int[] nums, int target) {
            Dictionary<long, int> valueIndex = new Dictionary<long, int>();
            
            for (int i = 0; i < nums.Length; i++)
            {
                long complement = (long)target - nums[i];
                
                if(valueIndex.ContainsKey(complement)) return new[] { valueIndex[complement], i };
                else
                {
                    if (!valueIndex.ContainsKey((long)nums[i])) valueIndex.Add((long)nums[i], i);
                }
            }
            
            return new int[]{ 0, 0 };
        }
    }
    
    }
    

    }


  • 0
    J

    EDIT: My initial judgment of the implementation was given too hastily. I have an update in another reply below.

    While you are only explicitly using a single for loop, you are in fact using nested for loops by calling the ContainsKey() method. Behind the scenes, ContainsKey() loops through all of the values contained in the backing array. When you call ContainsKey(), it will call FindEntry(), which you can read implementation details about here in the source code:

    http://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,bcd13bb775d408f1


  • 0
    Z

    @j.reddick Good to know! On that note, I think TryGetValue would have been slightly better than ContainsKey, since it eliminates the need to do a secondary lookup on that key.

    Other than that, I'm not sure of any way around the dictionary's internal loop. I think that's as fast as it gets for lookup (correct me if I'm wrong), and it's something approaching O(1). So my function is still basically O(n), if n is the input size.


  • 0
    J

    @zach.borst.94 You know, I was thinking about it after I left this reply and was too hasty in my response. I was thinking about the ContainsValue method doing another full loop of the entries in the Dictionary. ContainsKey is utilizing the hash, which is what you correctly were trying to do. Looking at the implementation again, I notice I skimmed over it real quick and just saw the loop in there and made the bad judgment. The for loop in the FindEntry() method seems to be looking for a next entry node only if there happens to be more than one key with the same hash value.


  • 0
    Z

    @j.reddick Oh, I see where you were coming from. In that case, yes, ContainsValue is significantly slow and would have made my function O(n^2) in the worst case.

    The performance penalty for key look-up, is not very significant or totally avoidable, but still interesting to know.


Log in to reply
 

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