Minimum Garden Perimeter to Collect Enough Apples: Binary Search on Math

Given an infinite 2D grid centered at the origin, every point (i, j) contains |i| + |j| apples. You need to find the minimum perimeter of a square plot centered at the origin that collects at least neededApples total apples. The plot extends from (-n, -n) to (n, n) for some integer n, and its perimeter is 8n.

This is LeetCode 1954: Minimum Garden Perimeter to Collect Enough Apples, a medium problem that combines mathematical derivation with binary search. The trick is recognizing that the total apple count has a closed-form formula, which turns the problem into a classic binary search on the answer.

Why this problem matters

This problem is a clean example of a two-step pattern that shows up often in competitive programming and interviews. First, you derive a mathematical formula that replaces an expensive simulation. Then you binary search over the formula to find the optimal answer. The math reduces an O(n^2) summation to O(1), and the binary search reduces a linear scan to O(log n). Together, they turn a potentially intractable problem into something that runs in microseconds.

It also tests whether you can reason about symmetry and summation. The 2D grid has four-fold symmetry, and the apple counts along rows and columns follow arithmetic progressions. If you can exploit that structure, the formula falls out naturally.

The brute force approach

The simplest approach is to try every possible value of n starting from 1, compute the total apples inside the square from (-n, -n) to (n, n), and return 8 * n as soon as the total meets the target.

Computing the total naively means iterating over all (2n+1)^2 points and summing |i| + |j|. That is O(n^2) per candidate n, and you might need to check up to around 100,000 values of n for the largest inputs. That is far too slow.

Even if you compute the sum more cleverly using symmetry, you still have a linear scan over n. You can do better.

The key insight: closed-form formula plus binary search

By symmetry, you can compute the total apples inside the square of side 2n without iterating over every point. The sum of |i| + |j| over all points (i, j) with |i| <= n and |j| <= n works out to a clean formula:

f(n) = 2 * n * (n + 1) * (2 * n + 1) / 3

You can derive this by separating the sum into the |i| part and the |j| part, then using the formula for the sum of integers from 0 to n. Each coordinate contributes 2 * (2n + 1) * n * (n + 1) / 2 across the grid, and combining them gives the formula above.

Once you have f(n), the problem becomes: find the smallest n such that f(n) >= neededApples. Since f(n) is strictly increasing, this is a textbook binary search on the answer.

Walking through it step by step

Let's trace through an example with neededApples = 100. We binary search for the smallest n where f(n) = 2n(n+1)(2n+1)/3 is at least 100.

The candidates and their apple totals: n=1 gives 4, n=2 gives 20, n=3 gives 56, n=4 gives 120, n=5 gives 220, and so on. The answer is n=4, since 120 is the first value that reaches 100.

For the simplest case, neededApples = 1, the answer is n = 1 (total apples = 4, which is at least 1), so the perimeter is 8 * 1 = 8.

The optimized solution

def minimum_perimeter(needed_apples):
    lo, hi = 1, 100000

    while lo < hi:
        mid = (lo + hi) // 2
        total = 2 * mid * (mid + 1) * (2 * mid + 1) // 3

        if total >= needed_apples:
            hi = mid
        else:
            lo = mid + 1

    return 8 * lo

Here is what each piece does:

1. lo = 1, hi = 100000. The smallest possible n is 1 (a 2x2 square). The upper bound 100,000 is large enough to cover the constraint neededApples up to 10^15. At n = 100000, f(n) is roughly 1.3 * 10^15, which exceeds the maximum input.

2. while lo < hi. We narrow the range down to a single value. When lo == hi, that is our answer.

3. total = 2 * mid * (mid + 1) * (2 * mid + 1) // 3. This computes f(mid), the total apple count for a garden of side 2 * mid. Integer division is safe here because 2n(n+1)(2n+1) is always divisible by 3 (among three consecutive factors n, n+1, 2n+1, at least one is divisible by 3).

4. if total >= needed_apples: hi = mid. If the current n collects enough apples, it might be the answer, or a smaller n might work. Keep mid in range and search left.

5. else: lo = mid + 1. If the current n does not collect enough, we need a strictly larger garden.

6. return 8 * lo. The perimeter of a square from (-n, -n) to (n, n) is 4 * 2n = 8n.

Why this approach is correct

The correctness depends on two properties.

The formula is correct. The total apple count f(n) = 2n(n+1)(2n+1)/3 can be verified against small cases. For n = 1, f(1) = 2 * 1 * 2 * 3 / 3 = 4. For n = 2, f(2) = 2 * 2 * 3 * 5 / 3 = 20. The formula comes from decomposing the double sum of |i| + |j| into separate sums over each coordinate, then applying the standard identity for the sum of integers. You can confirm by induction: the apples added when expanding from ring n-1 to ring n equal f(n) - f(n-1), which corresponds to exactly the points on the boundary of the new ring.

The function f(n) is strictly increasing. Since f(n) is a cubic polynomial with positive leading coefficient and n >= 1, it is strictly increasing. This guarantees the binary search finds the unique smallest n.

Complexity analysis

Each iteration does O(1) arithmetic, so the total work is essentially constant for any input within the constraints.

Building blocks

1. Binary search on answer

The core pattern here is the same one used in Koko Eating Bananas, Split Array Largest Sum, and dozens of other problems. You have a monotonic feasibility condition over a range of candidate answers. Binary search finds the boundary in logarithmic time.

The template:

lo, hi = lower_bound, upper_bound
while lo < hi:
    mid = (lo + hi) // 2
    if is_feasible(mid):
        hi = mid
    else:
        lo = mid + 1
return lo

In this problem, is_feasible(mid) is f(mid) >= neededApples. The only difference from problem to problem is what the feasibility check looks like.

2. Closed-form summation

Many grid and counting problems can be simplified by recognizing that the sum has a closed form. Here, the key identity is:

sum of k for k = 0 to n = n * (n + 1) / 2
sum of k^2 for k = 0 to n = n * (n + 1) * (2n + 1) / 6

The apple sum decomposes into sums of absolute values across rows and columns, which reduce to these standard identities. Recognizing when a brute-force summation can be replaced by a formula is a valuable skill that appears in many math-tagged problems.

Edge cases

Before submitting, make sure your solution handles these:

• neededApples = 1: the smallest garden with n = 1 has f(1) = 4 apples, which is at least 1. Perimeter = 8.
• Very large neededApples (up to 10^15): the upper bound of 100,000 is sufficient. f(100000) = 1,333,340,000,006,667 which exceeds 10^15. Make sure your language handles large integers (Python does this natively).
• neededApples equals f(n) exactly: the >= check handles this correctly. The binary search will land on exactly that n.
• Integer overflow in other languages: in C++ or Java, 2 * mid * (mid + 1) * (2 * mid + 1) can overflow 32-bit integers. Use long long or long respectively.

Common mistakes

1. Wrong formula. The most common error is getting the closed-form wrong. Off-by-one errors in the derivation (forgetting the origin point, miscounting the range) lead to a formula that is close but not correct. Always verify your formula against small cases like n = 1 and n = 2.

2. Setting hi = mid - 1 when feasible. When f(mid) >= neededApples, the current mid might be the answer. If you set hi = mid - 1, you could skip it entirely. Always use hi = mid in the "search for minimum" variant of binary search.

3. Upper bound too small. If your initial hi is not large enough to cover the worst case, the binary search will return a wrong answer. For this problem, hi = 100000 is safe, but hi = 10000 would fail for large inputs.

4. Forgetting the perimeter conversion. The binary search finds n, but the answer is 8 * n, not n. A careless return statement can cost you the problem.

From understanding to recall

The solution is short, maybe eight lines of Python. The formula, the binary search template, the 8 * n conversion. You understand all of it right now. But will you remember the exact formula three weeks from now when a similar problem appears?

The details that trip people up: is it 2n(n+1)(2n+1)/3 or n(n+1)(2n+1)/6? Is the perimeter 4n or 8n? These are the kinds of facts that fade unless you actively reinforce them.

Spaced repetition solves this. You type the solution from memory at increasing intervals. After a few rounds, the formula and the binary search template are locked in. When you see a problem that combines math with binary search on the answer, you do not have to rederive anything. You just write it.

Related posts

• Search Insert Position - Binary search fundamentals
• Koko Eating Bananas - Another binary search on answer problem

CodeBricks breaks LeetCode 1954 into its closed-form summation and binary-search-on-answer building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a math plus binary search problem shows up in your interview, you do not hesitate. You just write it.