Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

509. Fibonacci Number

Time: $O(n)$

Space: $O(1)$

			


class Solution {
 public:
  int fib(int N) {
    if (N < 2)
      return N;

    vector<int> dp{0, 0, 1};

    for (int i = 2; i <= N; ++i) {
      dp[0] = dp[1];
      dp[1] = dp[2];
      dp[2] = dp[0] + dp[1];
    }

    return dp.back();
  }
};




			


class Solution {
  public int fib(int N) {
    if (N < 2)
      return N;

    int[] dp = {0, 0, 1};

    for (int i = 2; i <= N; ++i) {
      dp[0] = dp[1];
      dp[1] = dp[2];
      dp[2] = dp[0] + dp[1];
    }

    return dp[2];
  }
}




			


class Solution:
  def fib(self, N: int) -> int:
    if N < 2:
      return N

    dp = [0, 0, 1]

    for i in range(2, N + 1):
      dp[0] = dp[1]
      dp[1] = dp[2]
      dp[2] = dp[0] + dp[1]

    return dp[2]