Algorithm Problems

For general techniques, see Algorithm Techniques.

For helpful reference, see Coding Cheat Sheet.

An algorithm interview is like being in a race in a maze with hidden clues and signs to tell you where you should go, all while trying to get to the finish line in under 30 minutes. If you miss a sign, you're fucked. If you go too slow, you're fucked. So just go steady, watch the signs and down blow past them!

Rules:

1. Do not jump to quick solutions
2. Think about information that you have access to
3. Write psuedo code that works. If pseudo code doesn't work, code won't work
4. Think simple.
5. Validate psuedocode with a simple case

Leedcode 692.

Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

This problem is broken in two parts:

1. Track/store the words and their frequency
2. Order the words and their frequency

For storing the words and their frequency there are two ways to do it:

1. hashmap of string and int, increment count every time you see the int
2. Using a trie

For ordering you can do the following:

1. Using an ordered set and return only the elements needed.
   1. This is bad because you are sorting all the words when you only need some of them.
2. Maintain a priority queue of all the words with a custom ordering and then pop off only the needed elements.
   1. This is not great because you are storing a priority queue with every possible word.
3. Build a MIN HEAP.
   1. If the min heap is bigger than the size we are looking for, when inserting an element check it against the current min. If it is bigger, insert it and pop off the min.

Implementation of the logic is straight forward. The tricky part is setting the custom ordereding in C++. Use the following for ordering a prioirty queue with the frequency and then lexicographically as a fallback.

typedef pair<string, int> p_d;
 
class Compare{
public:
    bool operator() (const p_d& a, const p_d& b){
        if(a.second == b.second){
            return a.first > b.first;                
        }else {
            return a.second < b.second;
        }
    }
};
 
priority_queue<p_d, vector<p_d>, Compare> heap;

To create a custom compare ordered container and not fall into C++ errors, creating a compare class works.

Leetcode 329.

Given an integer matrix, find the length of the longest increasing path.

Solved this with a dfs approach. Spent a bit of time with seen, and didn't even need it in the end! The numbers are increasing so you don't need to check for that.

array of positions getNeighbors(pos, the matrix)
    return top if inbounds and bigger
 
int explore and return the longest path (Pos, seen set of positions)
    have we seen it?
        yes: return 0
    add this position to seen
    getNeighbors of this position (in bounds and increasing positions)
 
    int path = 0;
    iterate over neighbors
       path = max(1 + explore(neighbor), path)
 
    remove this pos from seen
    return path
 
keep running max
start from every element in the array
explore it, get longest path, compare to runnign max
return the max

class Solution {
public:
 
    vector<vector<int>> memo;
    int rows;
    int cols;
 
    bool inBounds(vector<int> &p){
        if(p[0] < 0 || p[0] >= rows || p[1] < 0 || p[1] >= cols){
            return false;
        }
        return true;
    }
 
    vector<vector<int>> getNeighbors(vector<vector<int>>& matrix, vector<int> &p){
        int val = matrix[p[0]][p[1]];
        vector<int> l = p, r = p, t = p, b = p;
 
        l[1]--; 
        r[1]++; 
        t[0]--; 
        b[0]++;
 
        vector<vector<int>> out;
        if(inBounds(l) && matrix[l[0]][l[1]] > val)      { out.push_back(l); }
        if(inBounds(r) && matrix[r[0]][r[1]] > val)      { out.push_back(r); }
        if(inBounds(t) && matrix[t[0]][t[1]] > val)      { out.push_back(t); }
        if(inBounds(b) && matrix[b[0]][b[1]] > val)      { out.push_back(b); }
 
        return out;        
    }
 
    int explore(vector<vector<int>>& matrix, vector<int> &p){
 
        if(memo[p[0]][p[1]] > 0){ return memo[p[0]][p[1]]; }
        int path = 1;
        vector<vector<int>> nays = getNeighbors(matrix, p);
        for(auto& n : nays){
            path = max(path, 1 + explore(matrix,n));
        }
        memo[p[0]][p[1]] = path;
        return path;
    }
 
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if(matrix.size() == 0){ 
            return 0; 
        }
 
        rows = matrix.size();
        cols = matrix[0].size();
 
        memo = vector<vector<int>>(rows, vector<int>(cols, 0));
 
        int pathMax = 0;
        for(int r = 0; r < rows; r++){
            for(int c = 0; c < cols; c++){
                vector<int> p = {r,c};
                pathMax = max(pathMax, explore(matrix, p ) );
            }
        }
        return pathMax;
    }
};

Leetcode 704.

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.

This is BEDROCK code that I sometimes forget. Binary Search of sorted data. This is what gets you O( Log N ) search of data.

Algorithm:

Left pointer = 0 and right pointer = to last element
While left is less then or equal to right
    Find middle
    Check if our target is in the middle, return it if we found it
    If our target is less than the middle element
      explore left, mid;
    If our target is greater than the middle
      explore mid+1 and right;
return -1 if not found.

Code:

int search(vector<int>& nums, int target) {
  int left = 0;
  int right = nums.size();
  int mid;
  while(left<=right){
    mid = left + (right-left)/2;
    if (nums[mid]==target){
      return mid;
    }
    else if (nums[mid] > target)
      right = mid -1;
    else left = mid+1;
 
  }
  return -1;  
}

Leetcode 283.

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

This is a classic problem of iterating over an array with two pointers, a standard one and a fast one.

Algorithm:

Create a pointer called last_good that starts at zero
Iterate i from 0 to end
  if Nums[i] is not 0
    swap it with last good, and increment last good

Leetcode 10.

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

This problem can be solved recursively without too much code, once you break into these 3 cases!

• Base Case: Pattern is empty
• Case 1: We don't have a star after next character in pattern
• Case 2: We have a star after the next character in pattern

We call isMatch(string s, string p) recursively, giving a new input and a new pattern string, and we operate on the first character. This calls for using the string::substr() function which is slow, but easy. We can also speed this up by implementing start pointers.

Algorithm:

Code:

bool isMatch(string s, string p) {
  int p_len = p.length(), s_len = s.length();
 
  // base case
  if(p_len == 0)
  {
    return s_len == 0;
  }
 
  // CASE 1
  if(p_len == 1 || (p_len > 1 && p[1] != '*') )
  {
    if(s_len == 0)
      return false;
 
    if(p[0] == '.' || p[0] == s[0])
      return isMatch(s.substr(1), p.substr(1));
    return false;
  }
 
  // CASE 2 second char is a *
  else
  {
    if( isMatch( s, p.substr(2) ) )
      return true;
 
    int i = 0;
    while(i < s_len && (s[i] == p[0] || p[0] == '.'))
    {
      if(isMatch(s.substr(i+1), p.substr(2)))
        return true;
      i++;
    }
    return false;  
  }
}

This code can be optimized by creating an overloaded function that takes in a start index for p and s.

Credit to this article for explaining the recursive way.

Leetcode 44.

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

This is a DP problem but can be solved recursively. I solved it recursively but it still fails leetcode. But I am getting comfortable with breaking the cases down. These kinds of problems lend themselves well to flowcharts!

Algorithm:

Code:

bool helperMatch(string &s, int p_s, string &p, int p_p) {
 
  // EMPTY CASE
  if(p_p >= p.length()) {
    if(p_s >= s.length()){
      return true;
    }else{
      return false;
    }
  }
  // p[0] is a '?' or a character
  else if(p[p_p] == '?' || isalpha(p[p_p])){
    // s is empty
    if(p_s >= s.length()){
      return false;
    } 
    // s not empty
    else{
      // character match
      if(p[p_p] == '?' || p[p_p] == s[p_s]){
        return helperMatch(s,p_s + 1, p, p_p + 1);
      }
      // characters don't match
      else{
        return false;
      }
    }
  }
  // p[0] is a '*'
  int i = 0;
  while(i <= s.length())
  {
    if( helperMatch( s, p_s + i, p, p_p + 1 ) ){
      return true;
    }else{
      i++;
    }
  }
  return false;
}
bool isMatch(string s, string p) {
  int i = 1;
  while(i < p.length()){
    if(p[i-1]=='*' && p[i] == '*'){
      p.erase(i,1);
    }else{
      i++;
    }
  }
  return helperMatch(s, 0, p, 0);
}

Leetcode 42.

Ah what a classic! Couple of ways of doing this one. Also good to know the brute force.

For every height h, find the maximum left height, and the maximum right height. The water at that h will be the minimum of the two minus h.

The DP solution is really straight forward! You just do two passes, use the minimum from each pass and add it to a result. O(1) time by O(n) space.

Algorithm:

Create res, and max_h, set to 0
Create a vector of left max heights
Iterate h over heights from 0 to end
  max_h = max of h and max_h
  left max push in max_h - h, this is the max this height can support
Reset max_h to 0
Iterate h over heights from end to 0
  max_h = max of h and max_h
  res += min(left max at i, max_h - h)
return res

Code:

int trap(vector<int>& height) {
    int res = 0, max_h = 0;
    // iterate from left
    vector<int> left_max;
    for(int i = 0; i < height.size(); i++)
    {
        max_h = max(max_h, height[i]);
        left_max.push_back(max_h - height[i]);
    }
    // reset the maximum
    max_h = 0;
    for(int i = height.size() - 1; i >= 0; i--)
    {
        max_h = max(max_h, height[i]);
        res += min(left_max[i], max_h - height[i]);
    }
    return res;
}

This is the nifty 0(1) time and space solution. Start with two pointers at the end and track max left and max right. Move up the pointer of the smallest element. This solution works because you are moving the smaller of the sides, so you are always calculating the minimum water with you can trap for each element, which is what we need.

Algorithm:

Create a left pointer L = 0, right pointer R to size - 1
Create left max LM and right max LM and a res of 0
While L < R
  IF H[L] is smaller than H[R]
      Set LM to MAX(LM, H[L])
      RES += LM - H[L]
      Increment L
  Else
      Set RM to MAX(RM, H[R])
      RES += RM - H[R]
      Decrement R
Return Res

Code:

int trap(vector<int>& h) {
    // left pointer, right pointer, left max, right max, result
    int l = 0, r = h.size() - 1, lm = 0, rm = 0, res = 0;
 
    while(l < r)
    {
        // move up the pointer to the smaller element
        if(h[l] < h[r])
        {
            lm = max(h[l], lm);
            res += lm - h[l++];
        }else
        {
            rm = max(h[r], rm);
            res += rm - h[r--];
        }
    }
    return res;
}

Leetcode 72 (Hard).

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

1. Insert a character
2. Delete a character
3. Replace a character

I learned how to solve this using DP. It is really cool how the memo table maps to the problem. The 3 operations, insert, delete, and replace map amazingly well to it.

This is a great video on the problem.

Algorithm:

Code:

int minDistance(string word1, string word2) {
 
  int m = word1.length(), n = word2.length();
 
  // return non zero length if a length is zero
  if(n*m == 0) return n+m;
 
  // init memo vector to all zero's
  vector<vector<int>> memo(m + 1, vector<int>(n + 1,0));
 
  // init left and top rows
  for(int i = 0; i <= m; i++)
    memo[i][0] = i;
  for(int j = 0; j <= n; j++)
    memo[0][j] = j;
 
  for(int i = 1; i <= m; i++)
  {
    for(int j = 1; j <= n; j++)
    {
      if(word1[i-1] == word2[j-1])
      {
        memo[i][j] = memo[i-1][j-1];
      }
      else
      {
        memo[i][j] = min(min(memo[i][j-1], memo[i-1][j-1]), memo[i-1][j]) + 1;
      }
    }
  }
  // Return the last element
  return memo[m][n];
}

Leetcode 161.

Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.

I initially solved this problem using 3 hard-coded cases. This was not very elegant and I learned a trick how to get the data in function in a way that eliminates code.

The trick was to ensure that string 1 is always bigger than string 2. The way to do that was to call the function recursively with the flipped strings in the case that string 1 was smaller than string 2.

We also rely on the fact that that the substrings after the non matching character should be the same.

Algorithm:

Set bigger equal to string 1 length, and smaller equal to string 2 length
If bigger < smaller
  return call functions with flipped strings
 
if bigger == smaller we need to do a replace
  iterate i over bigger
    if s1[i] != s2[i]
      return s1.substring(i+1) == s2.substring(i+1)
  if we get here that means strings were equal to return false
if bigger - smaller = 1
  iterate i over smaller
    if s1[i] != s2[i]
      return s1.substring(i+1) == s2.substring(i)
  return true if we get here
return false if we get here, because it means strings are more than 1 away from each other

Code:

bool isOneEditDistance(string s, string t) {
 
  // we want bigger s, and smaller t
  int bigger = s.length(), smaller = t.length();
 
  if(bigger < smaller) 
    return isOneEditDistance(t, s);
 
  // replace or equal
  if(bigger == smaller)
  {
    for(int i = 0; i < bigger; i++)
    {
      if(s[i] != t[i])
        return(s.substr(i+1) == t.substr(i+1));
    }
    // if we get to here, no replacement was made and the strings are equal
    // so we return false
    return false;
  }
 
  // Delete one character from bigger s
  else if(bigger - smaller == 1)
  {
    for(int i = 0; i < smaller; i++)
    {
      if(s[i] != t[i])
        return(s.substr(i+1) == t.substr(i));
    }
    // if we get here it means the last character in the bigger string is what remains
    return true;
  }
  return false;
}

Leetcode 583.

Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.

The cool thing about this problem is that when you solve it iteratively, the Dynamic problem version becomes really easy, and also a natural next step.

This problem breaks down into searching for the maximum common subsequence. This search breaks down in a recursive character by character scan that goes as follows:

1. Base Case if string1 or string2 are empty, return 0
2. Try checking the rest of the string without touching the first characters.
   1. Add 1 to this if equal.
3. Delete a character from string1 and recurse
4. Delete a character from string2 and recurse
5. Return the maximum of those 3 results

I first solved this problem by starting from the beginning of the strings and recursively calling with trimmed substrings. This solves the problem with $O(2^{max(m+n)})$.

If you change the recursive function just a bit, it makes it a breeze to convert to DP using a memo matrix. All you have to do is start from the end, instead of passing substrings, pass two pointers.

Here is the algorithm:

FUNCTION: maxSub(string S1 and S2, pointers M and N, memo matrix)
  if M or N are 0, return 0
  if memo[M][N] is valid, return it
 
  int x = 1 if S1[M-1] is equal to S2[N-1]
  int SAME = maxSub(S1, S2, M-1, N-1, memo) + x
  int DEL_S1 = maxSub(S1, S2, M-1, N, memo)
  int DEL_S2 = maxSub(S1, S2, M, N-1, memo)
 
  return the max of the 3
 
FUNCTION isValid(S1, S2)
  M = S1 length, N = S2 length
  Make a memo vector that is M+1 and N+1, init all to -1
  return ( M + N - 2* maxSub(S1, S2, M, N, memo)

Code:

// make our own fancy 3 way max function
int max(int x, int y , int z)
{
  return ::max(::max(x,y),z);
}
 
// return max equal sub string of s1 and s2
int maxSub(string& s1, string& s2, int m, int n, vector<vector<int>> &memo)
{        
  if(m * n == 0) return 0;
 
  // If it's in the memo, return it!
  if (memo[m][n] != -1) { return memo[m][n]; }
 
  int x = (s1[m - 1] == s2[n - 1]) ? 1 : 0;
  int same   = maxSub(s1, s2, m - 1, n - 1,memo) + x;
  int del_s1 = maxSub(s1, s2, m - 1, n,memo);
  int del_s2 = maxSub(s1, s2, m, n - 1,memo);
 
  memo[m][n] = max(same, del_s1, del_s2);
  return memo[m][n];
}
 
int minDistance(string word1, string word2) {
  int m = word1.length(), n = word2.length();
 
  vector<vector<int>> memo(m+1, vector<int>(n+1, -1));
  int max_sub = maxSub(word1, word2, m, n, memo);
 
  return(m + n - 2*max_sub);
}

Leetcode 718.

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

This is a very simple DP algorithm! The brute force way is $O(n^3)$ and fails at pretty small strings.

For brute force, iterate over every possible combination of indices for A and B. For each possible index, if the characters are the same, run a while loop and see how far you can go till both characters are not longer the same.

The DP algorithm is really simple. You create a 2D memo matrix that is 1 larger on both axes. Then iterate over i and j and if the characters at A[i-1] and B[j-1] are equal, set the element memo[i][j] to one larger than the upper left diagonal.

Algorithm:

Code:

int findLength(vector<int>& A, vector<int>& B) {
  int m = A.size(), n = B.size();
 
  vector<vector<int>> memo(m+1, vector<int>(n+1, 0));
 
  int ans = 0;
  for(int i = 1; i <= m; i++)
  {
    for(int j = 1; j <= n; j++)
    {
      if(A[i-1] == B[j-1])
      {
        memo[i][j] = memo[i - 1][j - 1] + 1;
        ans = max(memo[i][j], ans);
      }
    }
  }
  return ans;
}

Find duplicate and missing number. Input is an array of unsorted consecutive integers. Has 1 duplicated number, and a missing number. For example {5, 2, 3, 2, 1}, missing 4, duplicate 2.

I got this problem for a phone screen. I first solved in in O(N log(n)) by sorting first, then with a hint I was able to solve it in O(N) using a set and tracking max and min in a two pass. Dima told me to always watch out for max and min when consecutive numbers are involved.

Algorithm O(N log n):

Sort input array
Iterate i start at index 1 over array
    if(num[i] == num[i - 1] then it is a duplicate
    else if(num[i] == num[i]-2 it is a missing element
 
return duplicate and missing

Algorithm O(N):

create min set to INT_MAX and max set to INT_MIN
create unordered set
iterate n over input
    if n in set
        dupe = n
    insert n in set
    min = min ( min and n)
    max = max ( max and n)
 
iterate i from min to max
   if i is not found in our set, we have our missing!

Leetcode 287.

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Crazy cool algorithm called Floyd's Algorithm!!

For this to work conceptually we have to treat it as a linked list. The cool thing is that because there is one duplicate, and they are consecutive numbers, they won't point out of bounds.

This is a two part problem, we first detect a cycle in the linked list, and then we detect where the cycle started which is the duplicate.

Algorithm:

p = nums[0] and q = to num [0]
DETECT CYCLE
while true
    move p twice
    move q once
    if p == q, break ( we have a cycle )
 
FIGURE OUT WHERE CYCLE IS BASED ON FLOYD'S ALGO
q = nums[0]
while(p != q)
  move p once
  move q once
 
return q :)

Code:

int findDuplicate(vector<int>& nums) {
 
  int p = nums[0], q = nums[0];
 
  while(true)
  {
    p = nums[p]; p = nums[p];
    q = nums[q];
    if( p == q)
      break;
  }
 
  q = nums[0];
  while(p != q)
  {
    p = nums[p];
    q = nums[q];
  }
 
  return p;
}

Hackerrank.

You're given a list of n integers arr[0..(n-1)]. You must compute a list output[0..(n-1)] such that, for each index i (between 0 and n-1, inclusive), output[i] is equal to the median of the elements arr[0..i] (rounded down to the nearest integer).

I first solved this with a set, but this took n/2 time to find the middle elements. I then solved it with two heaps with.

Code:

vector <int> findMedian(vector <int> arr) {
  vector<int> out;
  priority_queue<int> max_heap;
  // just have to remember a default priority_queue in c++ is a max_heap
  priority_queue<int, vector<int>, greater<int>> min_heap;
 
  for(auto& num : arr){
    // If both heaps empty
    if(max_heap.size() == 0 && min_heap.size() == 0){
      max_heap.push(num);
    }
    // we assume that max heap will not be empty
    else{
      if(num > max_heap.top()){
        min_heap.push(num);
      }else{
        max_heap.push(num);
      }
    }
 
    // Balance the heaps CAREFUL WITH SIZE TYPES
    if((int)max_heap.size() - (int)min_heap.size() > 1){
      min_heap.push(max_heap.top());
      max_heap.pop();
    }
    else if((int)min_heap.size() - (int)max_heap.size()  > 1){
      max_heap.push(min_heap.top());
      min_heap.pop();
    }
 
    // Calculate median
    if(max_heap.size() == min_heap.size()){
      out.push_back( (max_heap.top() + min_heap.top() ) / 2 );
    }else if(max_heap.size() > min_heap.size()){
      out.push_back(max_heap.top());
    }else{
      out.push_back(min_heap.top());
    }
  }
  return out;
}

Interview problem.

Create an iterator for a list of sorted lists that implements a constructor SortedIterator(), next(), and hasNext() functions.

Great problem. I first dove into this problem by suggesting sorting out input lists. This would not work on large sets. Do not liberally try sorting data first. Explore the problem and see what can be done. In the end this problem can be solved with a min heap, by keeping track of the smallest leading element of the array, along with its indices.

I initially solved this problem with a multimap to take care of the i, j indices. A multimap has worse time complexity than a heap becasue it has O(log(n)) insertion times, and you need to do an insertion with every next() operation.

Algorithm:

class HeapElement
HeapElemetn constructor
value
  i, j
// convert to min heap
overload the < operator
  a.i > b.i
 
priority_queue<HeapElement> minHeap
 
FUNC constructure( lists )
  for i to lists size
  if list[i] not empty
    insert HeapElement(list[i][0], i, 0) into min heap
 
FUNC next()
  if hasNext() is false
     return -1
 
   get a copy of top element of heap, call it prevTop
   pop off the top element
   int out = prevTop.val
   prevTop.j++ 
   if prevTop.j is bounds of its list
     set prevTop.val to value at prevTop i j
     insert heapElement into min_heap;
   return out;
 
FUNC hasNext()
   return size of heap > 0

Code:

// this will contain the data in our heap
class HeapElement {
  public:
    int val, i, j;
    HeapElement(int _val, int _i, int _j) : val(_val), i(_i), j(_j){}
};
 
// Overload the less than operator
bool operator<(const HeapElement &a, const HeapElement &b){
  return a.val > b.val;
}
 
class SortedIterator {
private:
  // we need a reference to our input list
  const vector<vector<int>> &lists;
  priority_queue<HeapElement> minHeap;
public:
  // Constructor
  SortedIterator(const vector<vector<int>> &_lists) : lists(_lists){
    for(int i = 0; i < (int)lists.size(); i++){
      if(lists[i].size() > 0){
        minHeap.push(HeapElement(lists[i][0], i, 0));
      }
    }
  }
 
  // our iterator next function
  int next(){
    if(hasNext() == false){
      return -1;
    }
    HeapElement prevTop = minHeap.top(); 
    minHeap.pop();
    int out = prevTop.val;
 
    if(++prevTop.j < (int)lists[prevTop.i].size()){
      prevTop.val = lists[prevTop.i][prevTop.j];
      minHeap.push(prevTop);
    }
    return out;
  } 
 
  // check if we have a next value 
  bool hasNext(){
    return minHeap.size() > 0;
  }
};

Leedcode 62.

Find the unique paths a robot can take to get to an end of an array. He can only move one down or one right.

We solve this problem by creating a 2d vector of the path space. We then add up the possible ways we can enter a square, but adding the possible ways its top square has, and its left square has. The top row and left column start with 1, but theres only one way to enter those.

Algorithm:

create memo array
set memo[0][:] to 1
set memo[:][0] to 1
 
for i 1 to m
    for j 1 to m
        memo[i][j] = memo[i-1][j] + memo[i][j-1]
 
return memo[size - 1][memo[0]size-1]

Code:

int uniquePaths(int m, int n) {
    // vector of all 1's
    vector<vector<int>> memo(m,vector<int>(n,1));
 
    for(int i = 1; i < m; i++)
        for(int j = 1; j < n; j++)
            memo[i][j] = memo[i-1][j] + memo[i][j-1];
 
    return memo[m-1][n-1];
}

Leetcode 227

I solved this problem in a pretty complicated, but fun way! The bulk of the work is processing the string, which is a pain in C++. Learn the ways of string manipulation! While avoiding having to learn how to use stringstreams of course :).

 
[1] very long complicated solution show
class Solution {
public:
    enum NodeType { NUM, MULTIPLY, DIVIDE, ADD, SUBTRACT};
    typedef list< pair<NodeType, int> > MyList;
    MyList exp;
    list< MyList::iterator > listAS;
    list< MyList::iterator > listMD;
 
    void process(string& s) {
        // get rid of spaces
        int i = 0;
        while(i < s.length())
        {
            if (s[i] == ' ') s.erase(i,1);
            else i++;
        }
        s += ' ';
        int p = 1, start = 0;
        while(p < s.length())
        {
            if(!isdigit(s[p]))
            {
                string snum = s.substr(start, p - start);
                exp.push_back( make_pair(NUM, stoi(snum)) );
                switch(s[p]){
                    case '/': 
                        exp.push_back( make_pair(DIVIDE,0) ); 
                        listMD.push_back( prev(exp.end()) ); 
                        break;
                    case '*': 
                        exp.push_back( make_pair(MULTIPLY,0) );  
                        listMD.push_back( prev(exp.end()) ); 
                        break;
                    case '+': 
                        exp.push_back( make_pair(ADD,0) );  
                        listAS.push_back( prev(exp.end()) ); 
                        break;
                    case '-': 
                        exp.push_back( make_pair(SUBTRACT,0) );
                        listAS.push_back( prev(exp.end()) ); 
                        break;
                }
                start = p + 1;
            }
            p++;
        }
        return;
    }
 
    int calculate(string s) {
 
        process(s);
 
        for(auto& it : listMD)
        {
            if(it→first == DIVIDE)
                prev(it)→second = prev(it)→second / next(it)→second;
            else if(it→first == MULTIPLY)
                prev(it)→second = prev(it)→second * next(it)→second;
            exp.erase(next(it));
            exp.erase(it);
        }
        for(auto& it : listAS)
        {
            if(it→first == ADD)
                prev(it)→second = prev(it)→second + next(it)→second;
            else if(it→first == SUBTRACT)
                prev(it)→second = prev(it)→second - next(it)→second;
            exp.erase(next(it));
            exp.erase(it);
        }
 
        return exp.front().second;
    }
};

Here is a much more concise solution I found online:

int calculate(string s) {
  stack<int> myStack;
  char sign = '+';
  int res = 0, tmp = 0;
  for (unsigned int i = 0; i < s.size(); i++) {
    if (isdigit(s[i]))
      tmp = 10*tmp + s[i]-'0';
    if (!isdigit(s[i]) && !isspace(s[i]) || i == s.size()-1) {
      if (sign == '-')
        myStack.push(-tmp);
      else if (sign == '+')
        myStack.push(tmp);
      else {
        int num;
        if (sign == '*' )
          num = myStack.top()*tmp;
        else
          num = myStack.top()/tmp;
        myStack.pop();
        myStack.push(num);
      } 
      sign = s[i];
      tmp = 0;
    }
  }
  while (!myStack.empty()) {
    res += myStack.top();
    myStack.pop();
  }
  return res;
}

Leetcode 92.

Reverse a linked list from position m to n. Do it in one-pass.

I struggled to get the cases down with this one. You have to think simply! You maintain 3 pointers, prev and cur, and next, which you get from cur. With this amazingly simple algorithim you don't even need a temp object.

What you do is move prev and cur till cur is on the first node m to be reversed.

ListNode* reverseBetween(ListNode* head, int m, int n) {
  ListNode dh;
  dh.next = head;
  ListNode *pre = &dh, *cur = head;
 
  n = n - m;
 
  // move pre and cur down till we hit m
  while(m > 1){
    pre = pre->next;
    cur = cur->next;
    m--;
  }
 
  // handle our swaps
  while(n > 0){
    ListNode* next = cur->next;
    cur->next = next->next;
    next->next = pre->next;
    pre->next = next;
    n--;
  }
  return dh.next;
}

Leetcode 142.

Given a linked list, return the node where the cycle begins. If there is no cycle, return null. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Super super cool Floyd's algorithm for loop detection. The following algorithm does all the proper checks in case of null lists and also lists that are not cycles.

Algorithm:

Make pointer q and q both equal to head
 
while q and p, and p->next
  p advance twice
  q advance once
  if p == q, break
 
When we get here we either have a loop or an NULL end.
if( !p OR !p->next) // the OR order is important, so we don't have runtime errors 
  We have the end, so no loop! return NULL
 
We have loop, so we have to find where it starts
q = head
while p != q
  p advance once
  q advance once
 
return q // or q, it doesn't matter :)

Code:

ListNode *detectCycle(ListNode *head) {
 
  ListNode *q = head, *p = head;
 
  while(q && p && p->next != NULL)
  {
    p = p->next; p = p->next;
    q = q->next;
    if(q == p)
      break;
  }
 
  if(!p || p->next == NULL)
    return NULL;
 
  q = head;
  while(p != q)
  {
    p = p->next;
    q = q->next;
  }
  return q;   
}

Leetcode 708

Given a node from a Circular Linked List which is sorted in ascending order, write a function to insert a value insertVal into the list such that it remains a sorted circular list.

This problem becomes hard because of the cases you have to check for, for proper insertion of the value.

You have to check these cases:

1. case 1: Simple, value fits between a prev and curr pointer.
2. case 2: We have a pivot, prev > curr. That means we fit if we are greater than prev, OR we are less than curr.
3. case 3: We reach back to the start of the list. Just pop us in man.

Took me a while to nail down these cases. It is VERY easy to get lost in nested if statements.

class Solution {
  public:
 
    void insertAfter(Node* node, int i)
    {
      Node* temp = new Node(i);
      temp->next = node->next;
      node->next = temp;
    }
 
    Node* insert(Node* head, int insert_val) {
 
      // Lets take care of the NULL case
      if(head == NULL)
      {
        Node* temp = new Node(insert_val);
        temp->next = temp;
        return temp;
      }
 
      // two pointers
      Node *p = head, *n = head->next;
 
      while(n != head)
      {
        if(p->val <= insert_val && insert_val <= n->val)
        {
          insertAfter(p, insert_val);
          return head;
        }
        else if(p->val > n->val)
        {
          if(p->val <= insert_val || insert_val <= n->val)
          {
            insertAfter(p, insert_val);
            return head;
          }
        }
        p = n;
        n = n->next;
      }
 
      insertAfter(p, insert_val);
 
      return head;
    }
};

Leetcode 655.

Print out a binary tree in the form of a 2d string array with spacing between each element.

The devil of this problem is to have the proper spacing between elements as you can down the levels. This problem requires the following information:

1. Get the heigh of the tree.
2. Figure out the width of the output based on the height
3. Do a DFS exploration of the tree and find correct indices for elements

I had to peek at the answer for this one, but practiced how to BFS iteratively with a queue and a nested while loop.

The algorithm for putting values in the correct places is also very smart, with a left and right pointer and then just placing items in the middle of them.

Leetcode 109.

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

The first step to realize is that you need to find the middle. Then you must realize that the middle is going to be a root node. Then you must realize that you need to split list in a left half and a right half. The left half of the list can be used to rescurse into, the head of which will be the left child, and same with the right list. You can do it!

Algorithm:

FUNCTION split(head)
   if head is null return head
   slow pointer and faster pointer equal to head
   prev pointer
   while fast and fast next is not null 
       prev = slow
       fast = fast next
       slow = slow next
    prev next = null
    return slow
 
FUNCTION treenode sortedListToBST(head)
    if head is null return NULL
    listnode mid = split(head)
    TreeNode root = new treenode mid val
    if mid != head
        left = sortedListToBST(head);
    right = sortedList(mid->next)
    return root 

ListNode* split(ListNode *head){
  if(head == NULL){
    return NULL;
  }
  ListNode *slow = head, *fast = head, *prev = head;
  while(fast != NULL && fast->next != NULL){
    prev = slow;
    slow = slow->next;
    fast = fast->next->next;
  }
 
  prev->next = NULL;
 
  return slow;
}
 
TreeNode* sortedListToBST(ListNode* head) {
  if(head == NULL){
    return NULL;
  }
  ListNode *mid = split(head);
  TreeNode *root = new TreeNode(mid->val);
 
  // left list is going to be started with head
  // right list is started with mid->next
 
  // if we have a real left list
  if(mid != head){
    root->left = sortedListToBST(head);
  }
  root->right = sortedListToBST(mid->next);
 
  return root;
}

Leetcode 103

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

Just have to realize to do a BFS with a queue and output the data reversed every other level. When doing BFS with a stack, you have to deliniate the current level and the next level. Doing it with a null node is a nice way.

Algorithm:

init a queue of nodes
put in the root in the queue
put in null node
 
output array (2d)
 
empty level array 
 
while queue inst' empty
    set cur to queue front
    pop it off
    if(cur is not null)
        put in our level array
        if children aren't null, push into queue
    else we reached the end of the level
        if rev is true
            reverse level array
        push in our level array
        clear the level array
        toggle rev
        if q isn't empty
            push in a null

Leetcode 124.

Given a non-empty binary tree, find the maximum path sum. There can be negative numbers.

I was asked this in an interview. The core concept is that at every node, the maximum will either be the following:

• left path plus node
• right path plus node
• both paths rooted through the node.

This problem can be simplified really well into short code by making use of max() calls on return data. Also we need to keep track of a global max, and also return the max path, either left or right.

explore function (node, global max) -> max path from this node
  if this node is null, return 0
 
  left max  = max(recursive call on left child, 0)
  right max = max(recursive call on right child, 0)
 
  max both  = node val + max (left, right max)
 
  global max = max(global max, both)
 
  return node val + max(left, right)

int explore(TreeNode* node, int& max_sum)
{
  if(node == NULL){
    return 0;
  }
 
  int max_left = max(explore(node->left, max_sum), 0);
  int max_right = max(explore(node->right, max_sum), 0);
 
  int max_both = node->val + max_left + max_right;
 
  max_sum = max(max_both, max_sum);
 
  return node->val + max(max_left, max_right);
}
 
int maxPathSum(TreeNode* root) {
  int max = INT_MIN;
  explore(root, max);
  return max;
}

I was given this problem at a interview and boy I did not get through. I then went back to code it a month later after more studying, and I still flubbed it!!!

Interval List Intersections

Leetcode 249.

What a great problem!!! The trick here is to realize that if two people are running on a circle, no one is really ahead of anyone at any given time. You can add a positive number to either and get to the same spot as the other one.

This thinking helps framing on how to deal with wrapping. In this problem, we need to create keys for each string that define their letters relative position. It is up to you to pick what is greater than what, just keep it simple. You got this man, it makes sense!

Algorithm:

FUNCTION: CALC DISTANCE BETWEEN CHARACTER A AND CHARACTER B -> return a char
  Int d = A - B
  if D is negative, then D += 'z' - 'a' + 1
  Reutrn D :)
FUNCTION GROUP SHIFTED -> RETURN vector of vector of strings
  create an OUTPUT vector of vector of strings
  Create a map of string, int : key is the "relationship between letters" and
  value is the OUTPUT index for this group of strings that has the same key
  Iterate s over input strings
    Create a temp key (string)
    Iterate i over s, starting at position 1.
      temp key += DISTANCE(s[i-1], s[i])
    IF key is found in map:
      add s to the right spot in OUTPUT
    else
      add s to a NEW spot in output and add this index to the MAP
  RETURN OUTPUT

Code:

// how much we have to add to a to get to b
char dist(char a, char b)
{
  int d = b - a;
  return (d < 0) ?  d += ('z' - 'a' + 1) : d;
}
 
vector<vector<string>> groupStrings(vector<string>& strings) {
 
  vector<vector<string>> out;
  unordered_map<string, int> shift_map;
 
  for(auto& s : strings)
  {
    // build our key for this string
    string key;
    for(int i = 1; i < s.length(); i++ )
    {
      key += dist(s[i-1], s[i]);
    }
 
    if(shift_map.find(key) == shift_map.end())
    {
      // not in the map, create new entry
      out.push_back({s});
      shift_map[key] = out.size() - 1;
    }
    else
    {
      out[shift_map[key]].push_back(s);
    }
  }
  return out;
}

Leetcode 296.

TODO

    int minTotalDistance(vector<vector<int>>& grid) {
        if(grid.size() == 0){
            return 0;
        }
 
        // find all peeps
        vector<Point> peeps;
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                if(grid[i][j] == 1){
                    peeps.push_back(Point(i,j));
                }
            }
        }
 
        int minDist = INT_MAX;
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                // iterate through all our peeps
                int totalDist = 0;
                for(auto& peep : peeps){
                    totalDist += Point::dist(peep, Point(i,j));
                }
                minDist = min(totalDist, minDist);
            }
        }
        return minDist;
    }
 

Facebook recruiting question.

We are giving an array that represents the path a yearbook will take to get signed. The index of each element represents the student. We optimize by keeping track of what students are part of a circuit of signatures. Those student's path do not then need to be calculated.

Algorithm:

FUNCTION Explore(Yearbook PATH, vertex V, set SEEN)
  if V in SEEN
    return
  insert V in SEEN
  explore(PATH[V-1])
 
FUNC signature(Yearbook PATH)
  out vector initalized to PATH size + 1 of -1's
  iterate i from 1 to PATH size inclusive
    if out[i] != -1
      explore(i)
      iterate E over elements in SEEN
        out[E] = SEEN size
  out.erase(out.begin)
  return out

void explore(vector<int> &arr, unordered_set<int> &seen, int v)
{
  if(seen.count(v) > 0){
    return;
  }
  seen.insert(v);
  explore(arr, seen, arr[v-1]);
  return;
}
 
vector <int> findSignatureCounts(vector <int> arr) {
  int n = arr.size();
  vector<int> out(n, -1);
  for(int i = 1; i <= n; i++){
    // an unexplored yearbook
    if(out[i-1] == -1){
      unordered_set<int> seen;
      explore(arr, seen, i);
      for(auto& e : seen){
        out[e-1] = seen.size();
      }
    }
  }
  return out;
}

Leetcode 207.

I spent all day on this :) and learned a lot! This problem requires you to understand that this a graph cycle detection problem. Once you realize that, you can solve the problem.

There is another way of solving this problem with an “in degree” array where you track count of dependencies. Video about it here.

The input is directed graph that is not guaranteed to be strongly connected. An approach is to a DFS on the starting vertex of every edge. Then walk through that path and mark it seen. If you end up a previously seen node, you have a cycle, so there's no way you can take the classes!

Keep in note that you have remove a leaf nodes from the seen list once we finish on it.

We also keep a “good” list of vertices we have visited and fully explored. That way we don't have to explore them again! This is an optimization that changes our complexity from $O(V²+E²)$ to $O(V+E)$.

Algorithm:

OPTIMIZATION: Build unordered set of explored vertices called GOOD
Build adjacency list Adj (unoredered map of vector<int>)
  Iterate over edges, adj[left vertex].push_back(right vertex)
 
Iterate v over Adj list
  OPT: If v is in good, CONTINUE, no need to check
  create seen set of ints
  If cycleDFS of v vertex returns TRUE, we have a cycle
    return false
 
// Return true if there is a cycle, false otherwise
FUNCTION cycleDFS( take in Adj, seen, and vertex v)
  OPT: If v is in good, return false, no need to check
  check if v in seen
    If true, return true, there is a cycle
  iterate over n Neighbors of vertex v
    OPT: If n is in good, continue
    If cycleDFS of n is true
      return true
  // if we are here there are no cycles
  Remove v from seen, so we can backtrack without false positives
  return false

class Solution {
public:
    // This marks nodes that are already explored as good
    unordered_set<int> good;
 
    bool cycleDFS(unordered_map<int, vector<int>>& adj, int v, unordered_set<int>& seen)
    {
        if(good.find(v) != good.end())
            return false;
 
        // If we found this node before, we have a cycle
        if(seen.find(v) != seen.end())
            return true;
 
        seen.insert(v);
 
        // Iterate over neighbors
        for(auto& n : adj[v])
        {
            if(good.find(n) != good.end())
                continue;
            if( cycleDFS(adj, n, seen) )
               return true;
        }
        // we have come to the end of this exploration. 
        seen.erase(v);
        good.insert(v);
        return false;
    }
 
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
 
        // Build the adjacency list
        unordered_map<int, vector<int>> adj;
        for(auto& e : prerequisites) {
            adj[e[0]].push_back(e[1]);
        }
 
        // Iterate over the adjancey list, and run cycleDFS on each node
        for(auto& v : adj)
        {
            // This is our optimization. If we enouter a vertex we have already
            // marked as good, we don't a DFS on it
            if(good.find(v.first) != good.end())
                continue;
            // we start an empty seen set for every exploration
            // if we didn't we would encounter nodes from other explorations
            unordered_set<int> seen {};
            if(cycleDFS(adj, v.first, seen))
            {
                return false;
            }
        }
        return true;
    }
};

Leetcode 210

This problem is an extension of Course Schedule. We use a topological sort algorithm to solve this problem. The only difference between this and the Course Schedule one problem is that we maintain a list of taken classes, which we use an output. We also iterate over all the classes n.

Algorithm:

class Solution {
public:
    // we need to keep a set to allow O(1) lookups of elements present,
    // but we still need to keep an order which will be output
    vector<int> taken_list;
    unordered_set<int> taken;
 
    bool DFS(unordered_map< int, vector<int> >& adj, unordered_set<int> &seen, int v)
    {
        if(taken.find(v) != taken.end())
            return true;
        if(seen.find(v) != seen.end())
            return false;
 
        // only run neighbor check on vertices that have adj list
        if(adj.count(v) > 0)
        {
            // insert v into seen to mark that we saw it on this path
            seen.insert(v);
            // iterate over v's neighbors
            for(auto& n : adj[v])
            {
                // if we taken this class we don't need dfs
                if(taken.find(n) != taken.end())
                    continue;
                if( DFS(adj, seen, n) == false)
                    return false;
            }
            seen.erase(v);
        }
        // add the class to the taken list
        taken.insert(v);
        taken_list.push_back(v);
        return true;
    }
 
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        taken_list.reserve(numCourses);
        // build adj list
        unordered_map< int, vector<int> > adj;
        for(auto& e : prerequisites){
            adj[e[0]].push_back(e[1]);
        }
 
        for(int v = 0; v < numCourses; v++)
        {
            // if we already took the class, then we don't have to explore it
            if(taken.find(v) != taken.end())
                continue;
            unordered_set <int> seen;
            if( DFS(adj, seen, v) == false)
                return {};
        }
        return taken_list;
    }
};

Leetcode 630.

There are n different online courses numbered from 1 to n. Each course has some duration (course length) t and deadling d day. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day. Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.

The technique here is a two stage process. First we sort by end dates. That lets us start trying to fit courses. We keep track of time and start at 0.

Then we try the next course. If you can take it, great, take it! If you can't take it, we try something special.

What we do is see if we can replace it with a course that we already took, that is longer. If we can do that, then great, take that one instead AND shift back our time by the time that we saved. SO the only thing we end up needing is a multiset of durations of courses we've taken. Then at the end we just return the size of the set!

Algrithm:

make a multiset of numbers
sort by end date
start a last_end int to 0
iterate i from 0 to end of courses
  if we can take the class : if last_end + courses[i][0] <= courses[i][1]
    take it: last_end += courses[i][0], set insert courses[i][0]
  if we CAN't take the class
    is the largest element in the taken set longer or EQUAL to this course we can't take?
      delete the largest elemetn in the set, and insert this new one. 
       last_end doesnt' stay the same! It gets shifted back by our time saved
 return size of set

Code:

int scheduleCourse(vector<vector<int>>& courses) {
  // set of durations of classes that we have taken
  multiset<int, greater<int>> taken;
 
  // sort our courses by end date
  sort(courses.begin(), courses.end(),
      [](vector<int>&a, vector<int>&b){return a[1]<b[1];});
 
  int last_end = 0;
  for(int i = 0; i < courses.size(); i++)
  {
    // can you this course? is the end time smaller equal to deadline
    if(courses[i][0] + last_end <= courses[i][1])
    {
      last_end += courses[i][0];
      taken.insert(courses[i][0]);
    }
    else
    {
      // lets try to swap this course the biggest possible taken one
      int old_len = *taken.begin();
      if(old_len >= courses[i][0])
      {
        // swap the courses
        taken.erase(taken.begin());
        taken.insert(courses[i][0]);
        // we also have to shift over our time savings!
        last_end -= old_len - courses[i][0];
      }
    }
  }
  return taken.size();
}

Leetcode 452.

There are a number of balloons whose width is defined by the position in 1D space as start and end pairs. Some of theses balloons may overlap. Calculated the mininum number of arrows required to pop all balloons.

This is an iteresting problem that is smiliar to the meeting room problem. You sort by end position and greedily check if the next balloon overlaps. If it does, great, we already have an arrow to pop it. If it doesn't overlap, then we need a new arrow for it.

Algorithm:

FUNCTION findMinArrows( 2d array of baloon bounds)
  sort INPUT array by end locations
  ANS = 0, LAST_END = LONG_MIN
  Iterate i from 0 to INPUT size
    if start of INPUT[i] is greater than LAST_END
      // need a new arrow!
      ANS++
      LAST_END = end of INPUT[i]
  return ANS

Code:

int findMinArrowShots(vector<vector<int>>& points) {
  // Sort by end first
  sort(points.begin(), points.end(),[](vector<int>&a, vector<int>&b){return a[1]<b[1];});
 
  // Initialize last end to smaller number than possible with int
  long last_end = LONG_MIN, ans = 0;
  for(int i = 0; i < points.size(); i++)
  {
    // If the current point ends after the previous, we need a new arrow
    if(points[i][0] > last_end)
    {
      ans++;
      // Update last end
      last_end = points[i][1];
    }
  }
  return ans;
}

GeeksforGeeks problem.

There is one meeting room in a firm. There are N meetings in the form of start times and end times. The task is to find the maximum number of meetings that can be accommodated in the meeting room. Print all meeting numbers.

I first solved this recursively by sorting with start times, and then recursively trying the maximum of every possible path. You get the right answer but with a $O(2^n)$ time. Amazingly if you sort by end times, and iterate over the meetings and pick the one that fits, you will come to the right answer. This is called a greedy appraoch.

Algorithm:

sort by end times
set last end to a negative number
iterate i over meetings
  if start time of i is greater or equal to last end, 
     ans++, last meeting = this one
     print out the meeting
return ans

Code:

int greedyMeeting(vector<vector<int>> &m)
{
  sort(m.begin(), m.end(),[](vector<int>&a, vector<int>&b){ return a[1]<b[1];});
  int last_end = -1, ans = 0;
  for(int i = 0; i < (int)m.size(); i++)
  {
    if(m[i][0] >= last_end)
    {
      // take the meeting
      last_end = m[i][1];
      ans++;
      cout << "Taking meeting number: " << ans << " - "
        << m[i][0] << ":" << m[i][1] << endl;
    }
  }
  return ans;
}

Leetcode 251

Given an array of meeting time intervals consisting of start and end times \[\[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

Fantastic question! My first approach was to do the brute force. You check every interval and see if it conflicts with each other. My first issue was figuring out how to check for overlap. I had nested if statements and it was not concise.

To do this, you simply check if the maximum start is greater or equal to the minumum end, If that's true then there is no overlap.

The next approach was to sort by starting inveral. You do this in C++ by creating a compare function like so:

bool compare(const vector<int>& a, const vector<int>&b)
{
  // a will go before b if this is true:
  return ( a[0] < b[0] );
}
 
sort(my_vector.begin(), my_vector.end(), compare);

After sorting the intervals by start time, I then created a list of rooms, (which just contained indices of intervals). I then processed each interval in order. For every interval I check through my room's list. If I find a room with no overlap, I insert the index of that interval and return. If i dont find a room, I create a new room and put the interval index in there.

There is a lot of wasted processing here.

First, we don't even need to a full list of intervals in a room, we can just keep track of the last meeting because they are in order.

Second, we are iterating through each room every time to find a fit. What we should be doing is using a set, and more importantly in C++ a multiset of rooms. That way we always just check the room with the earliest end time.

Third, all we need to store are end times! We then compare a start time with the earliest end time and we're good! Very elegant solution to this.

bool compare(const vector<int> &a, const vector<int> &b)
{
  // element a[0] should come before b[0] if it is smaller
  return a[0] < b[0];
}
 
class Solution{
public:
 
  void process(multiset<int> &rooms, vector<int>& interval)
  {
    // check to see if earliest ending meeting is <= to our start
    if(*rooms.begin() <= interval[0])
    {
      // erase our old meeting because we are gonna put in the new one :)
      rooms.erase(rooms.begin());
    }
    // put in the new end time
    rooms.insert(interval[1]);
  }
 
  int minMeetingRooms(vector<vector<int>> &intervals)
  {
    if(intervals.size() == 0) return 0;
    // sort our intervals by start time, earliest first
    sort(intervals.begin(), intervals.end(), compare);
 
    // make a multiset of rooms so we can store end times of the last meeting
    // there may be end times that end at the same time, so we need to allow for
    // dupes
    multiset<int> rooms = { intervals[0][1] };
 
    for(int i = 1; i < intervals.size(); i++)
    {
      process(rooms, intervals[i]);
    }
 
    return rooms.size();
  }
};

Leetcode.

Frog jump problem. Fucking confuused. Wtf??? I think i solved it but have no idea how it works out.vTheres a test case that I don't understand. I figured out what I did wrong, i misread the probem!!! k is the previous jump. My memo approach was spot on tho. NEED TO WRITE NOTES ON THIS.

Had to memo it to make it.

Leetcode 55.

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.

This is a deceivingly medium kind of problem. You would think that it would be very easy, but nopppeeeee. It is actually a dynamic problem that can be solved with just a few lined of code in a greedy way.

The idea is to iterate i from 0 to either the end of the array or the until we reach a maximum reach that we can.

FUNC: isPossible(array INPUT)
  MAX_REACH = 0, i = 0;
  Increment i from 0 to either INPUT size or MAX_REACH
    MAX_REACH = max ( MAX_REACH, INPUT[i]+i )
  return true if i got to the end of the array

This a problem that requires us to use constant extra memory, forcing us to use the input array itself to encode more data on it without losing the element information. Information about key assumptions must be had.

The minimum positive element is going to be anywhere between 1 and n+1. Here is why. If we have the perfectly ordered array with n = 5: [1 2 3 4 5] The next positive element is 6 (n+1). The smaller possible positive element is going to be 1. This means our range spans the same number of elements as we have in the input. Which means if there was a way to overlay this boolean state of whether or not we have seen this number in the array, we can solve this problem with no further memory required.

We do this in three steps:

First pass: Search for a 1, and if we find any numbers out of possible solutions (negative or greater than n), we reset them to 1.

Second pass: Map the value of each element to its index and then set that value to negative if present in the array. Hard problems would not be hard if they were easy to explain.

Thirst pass: Look for the first non present negative number. If not found, handle the edge case and return n+1.

YOU GO THIS!

https://www.youtube.com/watch?v=9lQnt4p7_nE

1. Sort input candidates.
2. Make a boolean flag array to track used elements.
3. Recurse over the candidates, choosing and building a solution, and then unchoosing.
4. If the next option is the same, skip it.

Implement your own power function. The following is the naive algorithm and takes too much time:

class Solution {
public:
    double myPow(double x, int n) {
 
        double ans = 1;
 
        if(n == 0)
            return 1;
 
        for(int i = 1; i <= abs(n); i++)
        {
            ans = x * ans;
        }
 
        if(n < 0)
            ans = 1/ans;
 
        return ans;
 
    }
};

class Solution {
public:
    double fastPow(double x, long long n)
    {
        if ( n == 0)
            return 1.0;
        double half = fastPow(x, n / 2);
        if( n % 2 == 0)
        {
            return half * half;
        }
        else
        {
            return half * half * x;
        }
    }
 
    double myPow(double x, int n) {
        long long N = n;
        if(N < 0)
        {
            x = 1/x;
            N = -N;
        }
 
        return fastPow(x, N);
    }
};