509. Fibonacci Number

🟩 Easy

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).

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.

Constraints

• 0 <= n <= 30

Solution

My Solution (Recursive)

func fib(n int) int {
    if n <= 1 {
        return n
    }

    return fib(n-1) + fib(n-2)
}

Optimal Solution (Iterative with Space Optimization)

func fib(n int) int {
    if n <= 1 {
        return n
    }
    
    // Only keep track of last two numbers
    prev2, prev1 := 0, 1
    
    // Build up to n iteratively
    for i := 2; i <= n; i++ {
        // Calculate current number and update previous two
        curr := prev1 + prev2
        prev2, prev1 = prev1, curr
    }
    
    return prev1
}

Approach

This solution uses iterative approach with space optimization:

1. Key Insight:

   • Each Fibonacci number only depends on previous two

   • No need to store entire sequence

   • Can use variables instead of array

2. Implementation Strategy:

   • Keep track of only last two numbers

   • Update in each iteration

   • Use parallel assignment for clean swaps

3. Processing Rules:

   • Handle base cases (n ≤ 1) directly

   • Build sequence iteratively

   • Return last calculated number

Complexity Analysis

Time Complexity: O(n)

• Single pass from 2 to n

• Each number calculated exactly once

• All operations are O(1)

• Linear growth with input size

Space Complexity: O(1)

• Only constant extra space used:

  • Two variables for previous numbers

  • One variable for current calculation

  • Loop counter

Why it works

• Mathematical Properties:

  • F(n) = F(n-1) + F(n-2)

  • Only need previous two numbers

  • Sequence grows linearly

• Optimization Details:

  • No recursion overhead

  • No array allocation

  • Minimal variable usage

  • Clean variable swapping

• Key Improvements over Recursive:

  • No stack overflow risk

  • No duplicate calculations

  • Better space efficiency

  • Faster execution

• Alternative Approaches (Not Implemented):

  • Matrix exponentiation: O(log n) time

  • Closed form (Binet's formula)

  • Dynamic programming with array

  • Tail recursion

• Edge Cases Handled:

  • n = 0 returns 0

  • n = 1 returns 1

  • n = 2 first calculated case

  • Works up to n = 30 (constraint)

result

Leetcode: link