Abstract / Summary

Given an integer n return the nth number in the fibonacci sequence starting with 0 and 1

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 74% (4+ million submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• Math
• Memoization
• Recursion

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 presented implementation computes the n-th Fibonacci number using an iterative dynamic-programming approach. A fixed-size integer array stores intermediate results, and the algorithm builds the sequence from the base cases up to the requested index. The design emphasizes simplicity and direct access to previously computed values, eliminating the overhead of recursive calls.

Key Steps

The core of the solution consists of three distinct phases: initialization of the storage structure, establishment of the base cases, and iterative construction of the sequence.

Allocation and Zero-Initialization

int f[50] = { 0 };

A stack-allocated array of length 50 is created and automatically filled with zeros. This guarantees that f[0] starts at the correct value for the Fibonacci series without requiring an explicit assignment.

Setting the First Two Values

f[1] = 1;

The second element of the array is explicitly set to one, establishing the two canonical base cases: F(0) = 0 and F(1) = 1. With these values in place, the subsequent loop can rely on them to generate higher terms.

Iterative Generation

for (int i = 2; i <= n; i++)
    f[i] = f[i-1] + f[i-2];

Starting at index two, the loop computes each Fibonacci number as the sum of the two preceding entries. The loop condition i <= n ensures that the computation stops exactly at the requested index, avoiding unnecessary work.

Returning the Result

return f[n];

After the loop completes, the array entry at position n holds the desired Fibonacci number, which is returned directly to the caller.

Edge Cases Handled

When the input n equals zero, the algorithm returns f[0], which remains zero due to the initial zero-initialization of the array. For n equal to one, the explicit assignment f[1] = 1 provides the correct result without entering the loop. The fixed array size of 50 comfortably accommodates any n up to 49, ensuring that the loop never accesses out-of-bounds memory for typical problem constraints. The loop guard i <= n also prevents execution when n is less than two, thereby skipping the iterative step entirely for the smallest inputs.

Performance Optimizations Observed

The implementation avoids the exponential blow-up associated with naïve recursive Fibonacci calculations by storing each computed value exactly once. Access to previously computed terms is performed in constant time via direct array indexing, which is faster than recomputing or using more complex data structures. The use of a statically sized array eliminates dynamic memory allocation overhead, keeping the memory footprint predictable and cache-friendly. By iterating only up to the required index, the algorithm performs the minimal amount of work necessary to produce the result.

Imagine you are building a tall tower out of colorful blocks. The first block is just a single one, and the second block is also just a single one. To find out how many blocks come next, you look at the two towers you just finished and stack them together to make a new one.

This code uses a special list, kind of like a row of boxes, to keep track of the height of each tower as it gets built. It starts by setting the first tower to a height of one. Then, the computer follows a rule to keep adding up the heights of the last two towers to get the height for the next one. It repeats this over and over again until it finishes building the tower at the height requested. Once the computer finishes putting all the blocks in their spot, it knows exactly how big the final tower is.

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		JS	Go	Rust				PHP	TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	aylei							Rust
	BigEggStudy				C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	everthis					JS
	fartem								Ruby
	fpdjsns	C++
	fsq	C++
	halfrost						Go
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	Krazune										C
	lkwq007		Python
	muhammadfarhankt						Go
	pruthvikp		Python
	qiyuangong			Java
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	varunu28			Java
	vthwang			Java
	yuanliu666									Kotlin
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, PHP, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
aylei	Rust
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
fsq	C++
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C
lkwq007	Python
muhammadfarhankt	Go
pruthvikp	Python
qiyuangong	Java
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vthwang	Java
yuanliu666	Kotlin
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