We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Hash Tables: Ice Cream Parlor
  2. Discussions

Hash Tables: Ice Cream Parlor

  • NSCoder
     + 2 comments

    There are better solutions than the suggested Binary Search including using a hashmap (quick) or a nested loop (cleaner/easier code)

    Time complexities for these alternatives

    Binary search + Array Sort = Ø(logn) + Ø(n) ＝＝ Ø(n)

    Hashmap Ø(n)

    Iterative Ø(n^2)

    NSInteger toInt(NSNumber *a){
    return [a integerValue];
}

void hashmapSolution(int m, int n, NSArray *flavorCost) {
 
    NSMutableDictionary *flavourMap = [NSMutableDictionary new];
    
    for (int i = 0; i < n; i++) {
        int flavor = toInt(flavorCost[i]);
        NSNumber *remainder = @(m - flavor);

        if (flavourMap[remainder] ) {
            printf("%ld %d\n", toInt(flavourMap[remainder])+1, i+1);
        }else{
            flavourMap[flavorCost[i]] = @(i);
        }
    }
}

    Any corrections are welcome