LeetCode 2620 - Counter

LeetCode Problem 2620

Difficulty: 🟢 Easy
Topics: —

Solution

Problem Understanding

The problem is asking us to implement a simple counter function with a closure-like behavior. Given an integer n, we need to return a function counter() that, when called the first time, returns n, and then increments the returned value by one for every subsequent call. Essentially, each call to the counter() function should produce a sequence starting from n and increasing by 1 each time: n, n+1, n+2, ....

The input n can be any integer between -1000 and 1000. The expected output is the sequence of integers produced by calling the counter() function repeatedly, as specified by a list of "call" operations.

The constraints indicate that the number of calls is at most 1000, which is very small, so performance is not a limiting factor. However, we need to ensure the counter behaves correctly with negative numbers and zero, as these are valid inputs.

Important edge cases include initializing the counter at a negative number, zero, or the maximum/minimum allowed values. The problem guarantees that the calls are always valid and the counter function is always called sequentially, so we do not need to handle invalid operations.

Approaches

The simplest approach is a naive one where you store the current counter value externally and manually update it every time the function is called. While this works perfectly, it does not leverage closures and would require additional external bookkeeping if implemented in a global context.

The optimal approach leverages closures (or function encapsulation) to maintain the internal state of the counter. By using a closure, the internal counter value persists across multiple calls without needing external variables. Each time the returned function is invoked, it increments and returns the stored value. This is simple, efficient, and idiomatic in both Python and Go.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(1) per call	O(1)	Maintain an external counter variable outside the function and increment it manually.
Optimal	O(1) per call	O(1)	Use a closure to encapsulate the counter state internally, automatically incrementing on each call.

Algorithm Walkthrough

1. Define a function createCounter that accepts an integer n as input. This will be the initial value of our counter.
2. Inside createCounter, define an inner function counter() that will serve as our returned function. This function will access a variable current that holds the current value of the counter.
3. Initialize a variable current with the value of n.
4. Every time the counter() function is called, it should first store the current value to return, then increment current by 1.
5. Return the stored value to the caller.
6. Finally, createCounter should return the counter() function itself.

The invariant here is that current always holds the next value that the counter function should return. Because current is enclosed within the closure, each call correctly updates the internal state without affecting external variables.

Python Solution

from typing import Callable

def createCounter(n: int) -> Callable[[], int]:
    current = n
    
    def counter() -> int:
        nonlocal current
        result = current
        current += 1
        return result
    
    return counter

In this implementation, we define createCounter which initializes current to n. The inner function counter() uses nonlocal to modify current from the enclosing scope. It first stores the current value in result, increments current, and then returns result. This ensures the first call returns n and subsequent calls increment correctly.

Go Solution

package main

func createCounter(n int) func() int {
    current := n
    return func() int {
        result := current
        current++
        return result
    }
}

In Go, closures work similarly. The variable current is captured by the returned anonymous function, and its value persists across calls. Each invocation increments current and returns the previous value. Go does not require nonlocal because the closure automatically has access to outer scope variables.

Worked Examples

Example 1: n = 10

Call	current	Returned
counter()	10	10
counter()	11	11
counter()	12	12

Example 2: n = -2

Call	current	Returned
counter()	-2	-2
counter()	-1	-1
counter()	0	0
counter()	1	1
counter()	2	2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) per call	Each call involves a simple variable increment and return.
Space	O(1)	Only a single integer is stored in the closure regardless of the number of calls.

Since we are storing just one integer, the space usage does not grow with the number of calls. Each call performs a constant amount of work, making this optimal for the constraints.

Test Cases

# test cases
c1 = createCounter(10)
assert c1() == 10  # first call returns initial value
assert c1() == 11  # increments by 1
assert c1() == 12  # increments by 1

c2 = createCounter(-2)
assert c2() == -2  # first call returns initial value
assert c2() == -1
assert c2() == 0
assert c2() == 1
assert c2() == 2

c3 = createCounter(0)
assert c3() == 0  # counter starting at zero
assert c3() == 1
assert c3() == 2

c4 = createCounter(1000)
assert c4() == 1000  # maximum allowed value
assert c4() == 1001

c5 = createCounter(-1000)
assert c5() == -1000  # minimum allowed value
assert c5() == -999

Test	Why
createCounter(10)	Normal positive starting value
createCounter(-2)	Negative starting value
createCounter(0)	Zero starting value
createCounter(1000)	Maximum allowed value
createCounter(-1000)	Minimum allowed value

Edge Cases

One important edge case is when n is negative. The counter must correctly handle negative values, incrementing toward zero and beyond. The closure handles this naturally by incrementing the integer regardless of sign.

Another edge case is starting at zero. Some implementations might incorrectly initialize counters to 1 if they assume positive starting values. Our implementation directly uses n, so zero is returned correctly.

Finally, we need to consider the maximum and minimum bounds of n (1000 and -1000). The algorithm handles these without overflow in Python due to arbitrary-precision integers. In Go, int is platform-dependent, but the constraints ensure that the counter will remain within the 32-bit signed integer range during typical use cases.

This solution ensures correctness for all valid inputs, preserves state through closures, and provides constant-time performance for each call.