Skip to main content

509. Fibonacci Number

easy

Compute the nth Fibonacci number where each term is the sum of the previous two. The canonical DP introduction — recurrence, memoization, and O(1)-space iteration in one short problem.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2), for n > 1. Given n, calculate F(n).

Constraints

  • 0 <= n <= 30

Examples

Example 1

Input
n = 2
Output
1

Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2

Input
n = 3
Output
2

Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3

Input
n = 4
Output
3

Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Naive recursion recomputes the same subproblems exponentially many times.

Hint 2

Memoize to cache each F(k) once — O(n) time, O(n) space.

Hint 3

Only the last two values matter. Track two rolling variables and overwrite as you go for O(1) extra space.

Solution approach

Reveal approach

Use bottom-up iteration with two rolling variables. Initialize prev = 0 (F(0)) and curr = 1 (F(1)). Loop i from 2 to n: compute next = prev + curr, shift prev = curr, curr = next. Return curr. Handle n = 0 separately by returning 0. The recurrence is identical to Climbing Stairs offset by one index, which is why both problems share the same constant-space pattern.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • fibonacci
  • memoization

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Adobe

Practice these live with InterviewChamp.AI

Drill Fibonacci Number and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →