Finding the lowest value and corresponding key in a large NSDictionary

Question

I have a NSDictionary with NSString as keys and NSNumber as values such as the following

NSDictionary *dictionary = @{@"Apple" : [NSNumber numberWithInt: 6],
                             @"Banana" : [NSNumber numberWithInt: 1],
                             @"Peach" : [NSNumber numberWithInt: 14],
                             @"Lychee" : [NSNumber numberWithInt: 1]};

Here, I would like to find the lowest key and value, which in this example would be tie between Lychee : 1 and Banana: 1. Ordinarlly for a smaller dictionary, I would just sort through all the values as suggested by this answer and retrieve the first (or the tied) object in the array based on the ranking. However, I was wondering if there is a way to do it if the NSDictionary is very large, where I could just pluck the lowest key-value pairs?

Thanks!

Answer 1

As @Tommy said, there's no option other than to do a linear search. Sorting the dictionary will impose a function of O(n log(n)), while a linear search is obviously O(n). You'd need to use the following:

NSDictionary *dictionary = @{@"Apple" : [NSNumber numberWithInt: 6],
                             @"Banana" : [NSNumber numberWithInt: 1],
                             @"Peach" : [NSNumber numberWithInt: 14],
                             @"Lychee" : [NSNumber numberWithInt: 1]};
NSString *lowestKey = nil;
int lowestValue = 0;
for (NSString *key in dictionary)
{
    int value = [dictionary[key] intValue];
    if (!lowestKey || value < lowestValue)
    {
        lowestKey = key;
        lowestValue = value;
    }
}
NSLog(@"Lowest: %@: %d", lowestKey, lowestValue);

Answer 2

This code has several advantages: enumerateKeysAndObjectsUsingBlock: doesn't need to lookup any keys but accesses the keys and values directly from the dictionary's data structures, avoiding expensive lookups. Using an NSNumber compare operation makes the code work for large integers, fractional numbers and NSDecimalNumber.

__block NSString* lowestKey = nil;
__block NSNumber* lowestNumber = nil; 

[dictionary enumerateKeysAndObjectsUsingBlock:^(id key, NSNumber* obj, BOOL *stop) {
    if ([lowestNumber == nil || [obj compare:lowestNumber] == NSOrderedAscending)
    {
        lowestKey = key;
        lowestNumber = obj;
    }
}];