Abstract / Summary

Given an integer n and a factor k, repeatedly generate arrays by replacing each element with the sum of it and its neighbor until one element remains and return that value.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 52% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Simulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes the maximum value in a sequence generated by a simple recurrence relation. The sequence is defined for indices from 0 up to a given non-negative integer n. For each index i, the value nums[i] is derived from previously computed entries, using integer division by two and a parity check. The function returns the largest element produced in the range.

Core Logic

The algorithm begins by handling the smallest inputs directly. When n is 0 or 1, the function returns n itself, because the sequence for these cases consists of a single element equal to the index.

if n <= 1:
    return n

A list named nums is allocated with a length of n + 1. All entries are initialized to zero, and the second element is set to one, establishing the base of the recurrence.

nums = [0] * (n + 1)
nums[1] = 1

The main loop iterates from index 2 up to n. For each i, the integer half of i is obtained by a right-shift operation, which is equivalent to floor division by two but executes faster at the machine level.

for i in range(2, n + 1):
    half = i >> 1

A parity test determines whether i is odd. If i is odd, the value at i is the sum of the two preceding half-indices; otherwise, it copies the value at the half-index. The conditional uses a bitwise AND to test the least-significant bit, again favoring low-level efficiency.

    if i & 1:
        nums[i] = nums[half] + nums[half + 1]
    else:
        nums[i] = nums[half]

After the loop finishes, the built-in max function scans the populated list and yields the greatest element, which the function returns.

return max(nums)

Edge Cases Handled

The early return for n <= 1 covers the situation where the list would otherwise have insufficient length to accommodate the base assignment nums[1] = 1. This prevents an index-out-of-range error for n = 0.

The loop starts at i = 2, ensuring that the recurrence never accesses indices below zero. The use of half = i >> 1 guarantees that for any i the computed half is a valid index already processed, because half is always less than i.

When i is odd, the expression half + 1 is also guaranteed to be within bounds, as the maximum value of half + 1 equals i // 2 + 1, which never exceeds i. Therefore the algorithm safely references only previously filled entries.

Performance Optimizations

The implementation makes several low-level choices that reduce overhead.

The right-shift operator (>> 1) replaces explicit integer division by two, eliminating the need for a division operation and leveraging faster bitwise arithmetic.

The parity check (i & 1) substitutes a modulo operation with a single bitwise AND, which is similarly inexpensive.

Pre-allocating the list nums with a fixed size avoids dynamic resizing during the loop, ensuring that each assignment operates on existing memory.

Using the built-in max after the loop processes the list in a single pass, rather than maintaining a running maximum during iteration. This choice keeps the loop body minimal and lets the interpreter handle the final reduction efficiently.

Flow Summary

The function first checks for trivial inputs, then constructs a list sized for the required range. It seeds the list with the known base case, iterates through each index applying a recurrence that depends only on already computed values, and finally extracts the largest element. The combination of early exit, bitwise operations, and pre-allocation yields a concise and performant solution for generating the sequence and determining its maximum.

Imagine you have a long row of empty treasure boxes and you want to fill them with secret numbers. First, you place a zero in the very first box and a one in the second box. Now you need a magic rule to fill all the rest. To figure out what goes in a box, you look at its address, which is just a fancy way of saying its number in the row.

If the address is an even number, like two or four, you cut that number in half and peek inside the box at that new, smaller address to see what value is hiding there. You simply copy that value into your current box.

If the address is an odd number, like three or five, you find the midpoint by cutting the address in half and ignoring the tiny fraction left over. Then you add together the value in the box at that midpoint and the value in the box right next to it.

You keep doing this job for every box until you reach the very last one you planned to fill. Once all the boxes hold their special numbers, you look through the whole group to find which box holds the biggest treasure of all.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java					TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java		Go			TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	chandansgowda		Python
	charles-wangkai				Java
	DimitrisJim								C
	everthis			JS
	fartem					Ruby
	fsq	C++
	halfrost						Go
	JoshCrozier			JS
	Krazune	C++
	lkwq007		Python
	MacJim	C++
	suxrobGM							C#
	trung-hn		Python
	varunu28				Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
Krazune	C++
lkwq007	Python
MacJim	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality