Recursion & Dynamic Programming Coding Challenges
- Fibonacci Number
class Solution:
def fib(self, N: int) -> int:
if N == 0 or N== 1:
return N
arr = [None]*(N+1)
arr[0]=0
arr[1]=1
for i in range(2,N+1,1):
arr[i] = arr[i-1]+arr[i-2]
return arr[N]
Complexity Analysis
- Time complexity: O(N). Each number, starting at 2 up to and including
N, is visited, computed, and then stored for O(1) access later on. - Space complexity: O(N). The size of the stack in memory is proportionate to
N.
2. Recursive Staircase
Complexity Analysis
- Time complexity : O(n) Single loop upto n.
- Space complexity : O(n). cache array of size n+1 is used.
3.Davis’ Staircase
Complexity Analysis
- Time complexity : O(n). Single loop upto n
- Space complexity : O(n). dp array of size n+1 is used.
4. House Robber
Complexity analysis
- Time complexity : O(n). Assume that nn is the number of houses, the time complexity is O(n)
- Space complexity : O(n)
5. Longest Common Substring
Complexity Analysis
- Time complexity : O(M.N)
We’re solving M⋅N subproblems. Solving each subproblem is an O(1) operation.
- Space complexity : O(M⋅N).
We’re allocating a 2D array of size M⋅N to save the answers to subproblems.
6. Longest Common Subsequence
Complexity Analysis
- Time complexity : O(M.N)
We’re solving M⋅N subproblems. Solving each subproblem is an O(1) operation.
- Space complexity : O(M⋅N).
We're allocating a 2D array of size M⋅N to save the answers to subproblems.
7. Maximum Subarray ( Kadane’s Algorithm) /Maximum Susequence
Complexity Analysis
- Time complexity : O(N) since it’s one pass along the array.
- Space complexity : O(N), since it’s a constant space solution.
8. Longest Increasing Subsequence. //To do : improve the time complexity
https://leetcode.com/problems/longest-increasing-subsequence/
Complexity Analysis
- Time complexity: O(n²). Two loops of n are there.
- Space complexity: O(n). dp array of size n is used.
9. Longest Palindromic Substring
Time Complexity
10. Longest Palindromic Subsequence
Complexity Analysis
- Time complexity : O(M.N)
We’re solving M⋅N subproblems. Solving each subproblem is an O(1) operation.
- Space complexity : O(M⋅N).
We’re allocating a 2D array of size M⋅N to save the answers to subproblems.
11. Maximum Product Subarray
12 Maximum Sum Circular Subarray
13 Subarray Sum Equals K
14 . Perfect Squares
https://leetcode.com/explore/interview/card/adobe/486/dynamic-programming/2546/
Complexity
- Time complexity: O(n*sqrt(n)). In main step, we have a nested loop, where the outer loop is of n iterations and in the inner loop, it takes at maximum sqrt(n) iterations.
- Space Complexity: O(n+1). We keep all the intermediate sub-solutions in the array
dp[].
15 Coin Change
Complexity
- Time complexity: O(n*m). In main step, we have a nested loop, where the outer loop is of n (amount) iterations and in the inner loop, it takes at maximum m (no of coins) iterations.
- Space Complexity: O(n+1). We keep all the intermediate sub-solutions in the array
dp[].
16 Decode Ways
Complexity Analysis
- Time Complexity: O(N), where N is length of the string. We iterate the length of
dparray which is N+1 - Space Complexity: O(N) The length of the DP array.
17. Count Square Submatrices with All Ones
Complexity Analysis
- Time complexity : O(mn). Single pass.
- Space complexity : O(m+1. n+1). Another matrix of same size+1 is used for dp.
