Optimizing Max Two Events Problem With Memoization And Binary Search
Recursive approach leads to TLE due to O(2^n) TC. Optimal approach uses memoization with TC: O(nlogn) and SC: O(n^2).
Problem
Recursive approach: leading to TLE
TC: O(2^n) exponential, since at every max() call we have two choices take or dontTake the current index which makes the time complexity exponential.
SC: O(n) for recursive stack space
class Solution {
public int maxTwoEvents(int[][] events) {
Arrays.sort(events,(a,b)-> a[0]-b[0]);
return max(0,-1,events,2);
}
public int max(int index ,int prev, int[][] events, int k){
//base case
if(index == events.length) return 0;
if( k==0) return 0;
int take = 0;
//take
if(prev ==-1 ||...