LeetCodeRelated practiceN-th Fibonacci Number
Overlapping Subproblems / MemoizationSolved Nov 12, 2025
Asked at 12 companies
6 recent
- tcs
- Bloomberg
- Microsoft
- Amazon
- Meta
- LTI
- Cognizant
- Infosys
- Accenture
+2 moreShow fewer
- Spotify
- Morgan Stanley
Community-reported · source · updated 2026-10-08. ● asked in the last 6 months.
Go step by step: try it yourself before the video and the visual. Progress saves on this device.
0 / 130 pointsSolved (Medium) 0/40Reviews 0/50Mastered 0/25Practice steps 0/15
Step 1
Know these before you start
Practise each one here, or tick what you already know
Concept videoStep 2
Try it on paper
5–10 minutes, no code yet
In the wild · Folders and JSON: Finding every file in a folder means listing the folder and doing the same for each folder inside it. Code that reads nested JSON walks it the same way.
ProblemProblem statementGiven an integer N, calculate the N-th Fibonacci number.ReadHide
Problem Description
Given an integer N, calculate the N-th Fibonacci number.
Code it here
Tab indents · ⌘/Ctrl+Enter runs · Esc leaves the editor
Step 6
Get it accepted
All test cases pass
Step 7
Review it so it sticks
Re-solve from memory after
The step that matters most: without reviews most of a solved problem fades within weeks. Three short re-solves, each just as you start to forget, are what make it yours.
Your notes
Three lines in your own words. They come back with this problem's reviews, so you can check yourself after recalling the solution.
Solve it yourself before you look
Reading the solution first feels like progress, but it makes the next similar problem — and the interview version — much harder, because you skipped the part where you figure it out. Give it an honest 20–30 minutes. Stuck? Re-read the pattern, watch the concept video, or try the brute force first.
Hidden: approach · solution code · optimal solution
Approach
Define $F(N) = F(N-1) + F(N-2)$. The base cases are $F(0)=0$ and $F(1)=1$. Use memoization to turn the inefficient exponential complexity into linear time.
Approaches
1. Memoization/DP (Optimal) - O(N) ⭐
Idea: Pure recursion leads to re-calculating the same subproblems repeatedly, resulting in O(2^N) time complexity. Memoization (caching results) reduces this to O(N).
- Use a global array or Hash Map (memo table) initialized to -1.
- In
F(N), check if the result is in the memo table. If yes, return it (O(1)). - Otherwise, calculate
F(N-1) + F(N-2), store the result in the memo table, and return it.
2. Brute Force (Pure Recursion) - O(2^N)
Idea: Direct implementation of the recursive definition without caching. This is exponential and will time out for large N.
Solution code
import sys
class Solution:
# Optimized: O(N) Time, O(N) Space - Memoization
def fib_memo(self, N: int, memo={}) -> int:
if N in memo:
return memo[N]
if N <= 1:
return N
# Cache the result
result = self.fib_memo(N - 1, memo) + self.fib_memo(N - 2, memo)
memo[N] = result
return result
# Brute Force: O(2^N) Time, O(N) Space - Pure Recursion
def fib_pure_recursion(self, N: int) -> int:
if N <= 1:
return N
# Exponential calculation due to overlapping subproblems
return self.fib_pure_recursion(N - 1) + self.fib_pure_recursion(N - 2)Other ways to solve it
- Thought of another approach (slower, or cleverer)? Code it here: the same tests check any approach.
- Community solutions on LeetCode ↗ for many more versions, in many languages. Read them after you've solved it.
Revising this one?
- →Solve it from memory before peeking
- →Say the pattern out loud, not just the code
- →Explain it like you would to a friend
- →Try it again in a different language