509. Fibonacci Number

Leetcode #: 509
Name: Fibonacci Number
Difficulty: Easy
Companies asked: Amazon, Google, Meta
Link: https://leetcode.com/problems/valid-parentheses/

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
F(2) = F(2–1) + F(2–2)
F(2) = F(1) + F(0)
Because we know F(1) = 1 and F(0) = 0, we can replace those terms
F(2) = 1 + 0
F(2) = 1

Recursive

Time: O(2^n) | Space: O(n)

Iterative

Time: O(n) | Space: O(n)

Iterative

Time: O(n) | Space: O(1)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
John Kim

John Kim

75 Followers

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com