Scratch Algorithms

Here are problems I worked on, and didn't really understand.

Leetcode 220

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

You can get the N² solution with a little work and iterate through a sliding window. Getting a better solution is hard and you have to use a set. You also have to make use of upper_bound and lower_bound functions.

Here's the algorithm:

Initialize an empty set
Loop through the array, for each element x
Find the smallest element s in set that is greater than or equal to x, 
  return true if s - x <= t
Find the greatest element g in set that is smaller than or equal to x, 
  return true if x - g <= t
Put x in set
If the size of the set is larger than k, 
  remove the oldest item.
Return false

I tried getting it to work in C++ but lower_bound doesn't actually return the greatest element smaller than x.

Leetcode 139.

It's a DP problem. I solved it with my recursive chop up the string approach but it fails the time limit with a pretty small test case.

Leetcode 630.

Code No Memo:

int maxCourse(vector<vector<int>>& courses, int last_end, int i)
{
  if(i >= courses.size()) return 0;
 
  int take = 0;
  // check if i is possible and try taking it
  if(last_end + courses[i][0] <= courses[i][1])
  {
    take = maxCourse(courses, last_end + courses[i][0], i+1) + 1;
  }
  int no_take = maxCourse(courses, last_end, i+1);
 
  return max(take, no_take);
}
 
int scheduleCourse(vector<vector<int>>& courses) {
  // sort by end
  sort(courses.begin(), courses.end(),[](vector<int>&a, vector<int>&b){return a[1]<b[1];});
 
  return maxCourse(courses, 0, 0);
}

Code With Memo

int maxCourse(vector<vector<int>>& courses, int last_end, int i,vector<vector<int>> &memo)
{
  if(i >= courses.size()) return 0;
  if(memo[last_end][i] != -1)
    return memo[last_end][i];
 
  int take = 0;
  // check if i is possible and try taking it
  if(last_end + courses[i][0] <= courses[i][1])
  {
    take = maxCourse(courses, last_end + courses[i][0], i+1, memo) + 1;
  }
  int no_take = maxCourse(courses, last_end, i+1);
 
  memo[last_end][i] = max(take, no_take);
  return memo[last_end][i];  
}
 
int scheduleCourse(vector<vector<int>>& courses) {
  // sort by end
  sort(courses.begin(), courses.end(),[](vector<int>&a, vector<int>&b){return a[1]<b[1];});
  // memo is gonna be last time and i. Need to find max time
  vector<vector<int>> memo(courses.back()[1]+1,vector<int>( courses.size()+1,-1));
 
 
  return maxCourse(courses, 0, 0,memo);
}