LeetCode 2630 - Memoize II

The problem asks us to implement a memoized version of a given function fn. A memoized function is one that caches the results of previous calls and returns the cached result if the same inputs are passed again.

leetcodehard

LeetCode Problem 2630

Difficulty: 🔴 Hard
Topics: —

Solution

Problem Understanding

The problem asks us to implement a memoized version of a given function fn. A memoized function is one that caches the results of previous calls and returns the cached result if the same inputs are passed again. The key requirement is that inputs are considered identical only if they are strictly equal (===), not just if they have the same content. This distinction matters for reference types like objects or arrays in JavaScript, where two objects with the same content are not equal unless they are the exact same instance.

The input is a function fn that can take any number and type of arguments, including primitives, objects, or even other functions. The output should be a memoized version of fn such that repeated calls with identical inputs do not trigger a new computation. The function must also track the number of calls actually made to fn for diagnostic purposes.

Constraints indicate the number of input sets can be up to 10^5, and the total number of individual inputs across all sets is also up to 10^5. This suggests that a naive approach that compares inputs deeply on every call would be too slow. Instead, caching must be based on reference equality, which is O(1) per argument comparison.

Important edge cases include:

  1. Primitive arguments that are equal in value but distinct in type or representation.
  2. Objects or arrays that have identical content but are distinct references. Each new instance should be treated as a unique input.
  3. Repeated references to the same object, which should hit the cache.

Approaches

The brute-force approach is to store each input set and compare incoming arguments to every cached set. This guarantees correctness because we explicitly check all previous calls, but it is inefficient: every function call may require iterating through all previous inputs, leading to O(n²) time complexity in the worst case. This would not scale to 10^5 calls.

The key insight for an optimal solution is to use a nested Map (hash table) structure keyed by reference for each argument. In JavaScript, a Map allows object keys and maintains identity-based equality. By nesting a Map for each argument in the function signature, we can traverse the structure based on the sequence of arguments. A cache hit is then detected in O(number of arguments) time. This approach scales linearly with the number of unique argument combinations.

Approach Time Complexity Space Complexity Notes
Brute Force O(n² * m) O(n) Compare each call to all previous calls, where n is the number of calls and m is the number of arguments
Optimal O(n * m) O(n * m) Use nested Maps to store argument sequences and results for reference-based caching

Algorithm Walkthrough

  1. Initialize a root Map to serve as the top-level cache.
  2. Define the memoized function wrapper that accepts arbitrary arguments.
  3. Start from the root Map, traverse a nested Map structure keyed by each argument in order.
  4. For each argument, check if the Map has a key for that exact argument reference.
  5. If it does not exist, create a new Map at that level and continue.
  6. After processing all arguments, check if a result has already been stored at the final level.
  7. If a result exists, return it immediately without calling fn.
  8. If no result exists, call the original fn with the arguments, store the result at the final Map level, and increment the call counter.
  9. Return the stored result.

Why it works: Each path through the nested Map corresponds uniquely to a sequence of argument references. Because Map keys use reference equality, this guarantees that only calls with the exact same arguments hit the cache. All other calls are computed anew and cached for future use.

Python Solution

from typing import Any, Callable

def memoize(fn: Callable) -> Callable:
    cache = {}
    call_count = {"calls": 0}

    def memoized(*args):
        current = cache
        for arg in args:
            if id(arg) not in current:
                current[id(arg)] = {}
            current = current[id(arg)]
        if "result" not in current:
            current["result"] = fn(*args)
            call_count["calls"] += 1
        return {"val": current["result"], "calls": call_count["calls"]}

    return memoized

In this Python implementation, we simulate JavaScript reference equality by using id(arg) as the key in the nested dictionaries. Each function call traverses the dictionary according to the sequence of argument IDs. If the path does not exist, we create it. The call counter tracks only actual executions of fn.

Go Solution

package main

import "sync"

type MemoizedFn struct {
	cache map[interface{}]interface{}
	mu    sync.Mutex
	calls int
	fn    func(args ...interface{}) interface{}
}

func Memoize(fn func(args ...interface{}) interface{}) func(args ...interface{}) map[string]interface{} {
	m := &MemoizedFn{
		cache: make(map[interface{}]interface{}),
		fn:    fn,
	}

	var memo func([]interface{}, map[interface{}]interface{}) map[interface{}]interface{}
	memo = func(args []interface{}, current map[interface{}]interface{}) map[interface{}]interface{} {
		if len(args) == 0 {
			return current
		}
		if _, exists := current[args[0]]; !exists {
			current[args[0]] = make(map[interface{}]interface{})
		}
		return memo(args[1:], current[args[0]].(map[interface{}]interface{}))
	}

	return func(args ...interface{}) map[string]interface{} {
		m.mu.Lock()
		defer m.mu.Unlock()
		current := memo(args, m.cache)
		if _, exists := current["result"]; !exists {
			current["result"] = m.fn(args...)
			m.calls++
		}
		return map[string]interface{}{
			"val":   current["result"],
			"calls": m.calls,
		}
	}
}

In Go, we handle reference equality using interface{} keys in maps. Synchronization with sync.Mutex ensures thread safety. Nested maps represent the sequence of arguments, and the call counter tracks actual function executions.

Worked Examples

Example 1: fn(a, b) = a + b with inputs [[2,2],[2,2],[1,2]]

Input Traversal Result Calls
(2,2) cache empty → new path 4 1
(2,2) path exists 4 1
(1,2) new path 3 2

Example 2: Objects [{},{},{}]

Each object is distinct by reference, so each call is a cache miss, incrementing the call counter each time.

Example 3: Same object o repeated

The reference is identical, so all calls after the first hit the cache and do not increment the call counter.

Complexity Analysis

Measure Complexity Explanation
Time O(n * m) Each call traverses m arguments in a nested Map structure, and there are n calls
Space O(n * m) Each unique combination of arguments creates a nested path in the cache

The complexity is linear with respect to the number of calls and the number of arguments per call. Only unique sequences consume additional space.

Test Cases

# Primitive arguments
assert memoize(lambda a, b: a + b)(2, 2) == {"val": 4, "calls": 1}  # basic addition
# Repeated reference objects
o = {}
memo = memoize(lambda a, b: {**a, **b})
assert memo(o, o) == {"val": {}, "calls": 1}  # first call
assert memo(o, o) == {"val": {}, "calls": 1}  # cache hit
# Distinct objects with same content
memo = memoize(lambda a, b: {**a, **b})
assert memo({}, {}) == {"val": {}, "calls": 1}
assert memo({}, {}) == {"val": {}, "calls": 2}
# Mixed primitives
assert memoize(lambda x, y: x * y)(3, 5) == {"val": 15, "calls": 1}
assert memoize(lambda x, y: x * y)(3, 5) == {"val": 15, "calls": 1}
Test Why
primitive addition validates basic caching for primitives
repeated object reference ensures reference equality is respected
distinct objects same content ensures different instances are not cached together
mixed primitive values confirms function works for different types

Edge Cases

  1. Empty arguments: A function with no parameters should still memoize correctly. The nested cache reduces to a single key and always returns the same result after the first call.
  2. Nested objects: Deeply nested objects are only compared by reference, avoiding expensive deep equality checks. This ensures performance for large structures.
  3. High volume calls: With up to 10^5 calls and inputs, a naive brute-force comparison would be too slow. Using a nested Map structure guarantees O(1) access per argument, keeping performance acceptable.

This implementation correctly handles