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

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:

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

Code:

  1. int search(vector<int>& nums, int target) {
  2. int left = 0;
  3. int right = nums.size();
  4. int mid;
  5. while(left<=right){
  6. mid = left + (right-left)/2;
  7. if (nums[mid]==target){
  8. return mid;
  9. }
  10. else if (nums[mid] > target)
  11. right = mid -1;
  12. else left = mid+1;
  13.  
  14. }
  15. return -1;
  16. }

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:

  1. Create a pointer called last_good that starts at zero
  2. Iterate i from 0 to end
  3. if Nums[i] is not 0
  4. 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:

  1. bool isMatch(string s, string p) {
  2. int p_len = p.length(), s_len = s.length();
  3.  
  4. // base case
  5. if(p_len == 0)
  6. {
  7. return s_len == 0;
  8. }
  9.  
  10. // CASE 1
  11. if(p_len == 1 || (p_len > 1 && p[1] != '*') )
  12. {
  13. if(s_len == 0)
  14. return false;
  15.  
  16. if(p[0] == '.' || p[0] == s[0])
  17. return isMatch(s.substr(1), p.substr(1));
  18. return false;
  19. }
  20.  
  21. // CASE 2 second char is a *
  22. else
  23. {
  24. if( isMatch( s, p.substr(2) ) )
  25. return true;
  26.  
  27. int i = 0;
  28. while(i < s_len && (s[i] == p[0] || p[0] == '.'))
  29. {
  30. if(isMatch(s.substr(i+1), p.substr(2)))
  31. return true;
  32. i++;
  33. }
  34. return false;
  35. }
  36. }

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 '*'.

  1. '?' Matches any single character.
  2. '*' 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:

  1. bool helperMatch(string &s, int p_s, string &p, int p_p) {
  2.  
  3. // EMPTY CASE
  4. if(p_p >= p.length()) {
  5. if(p_s >= s.length()){
  6. return true;
  7. }else{
  8. return false;
  9. }
  10. }
  11. // p[0] is a '?' or a character
  12. else if(p[p_p] == '?' || isalpha(p[p_p])){
  13. // s is empty
  14. if(p_s >= s.length()){
  15. return false;
  16. }
  17. // s not empty
  18. else{
  19. // character match
  20. if(p[p_p] == '?' || p[p_p] == s[p_s]){
  21. return helperMatch(s,p_s + 1, p, p_p + 1);
  22. }
  23. // characters don't match
  24. else{
  25. return false;
  26. }
  27. }
  28. }
  29. // p[0] is a '*'
  30. int i = 0;
  31. while(i <= s.length())
  32. {
  33. if( helperMatch( s, p_s + i, p, p_p + 1 ) ){
  34. return true;
  35. }else{
  36. i++;
  37. }
  38. }
  39. return false;
  40. }
  41. bool isMatch(string s, string p) {
  42. int i = 1;
  43. while(i < p.length()){
  44. if(p[i-1]=='*' && p[i] == '*'){
  45. p.erase(i,1);
  46. }else{
  47. i++;
  48. }
  49. }
  50. return helperMatch(s, 0, p, 0);
  51. }

Leetcode 42.

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

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.

Dynamic Programming (NOT BAD)

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:

  1. Create res, and max_h, set to 0
  2. Create a vector of left max heights
  3. Iterate h over heights from 0 to end
  4. max_h = max of h and max_h
  5. left max push in max_h - h, this is the max this height can support
  6. Reset max_h to 0
  7. Iterate h over heights from end to 0
  8. max_h = max of h and max_h
  9. res += min(left max at i, max_h - h)
  10. return res

Code:

  1. int trap(vector<int>& height) {
  2. int res = 0, max_h = 0;
  3. // iterate from left
  4. vector<int> left_max;
  5. for(int i = 0; i < height.size(); i++)
  6. {
  7. max_h = max(max_h, height[i]);
  8. left_max.push_back(max_h - height[i]);
  9. }
  10. // reset the maximum
  11. max_h = 0;
  12. for(int i = height.size() - 1; i >= 0; i--)
  13. {
  14. max_h = max(max_h, height[i]);
  15. res += min(left_max[i], max_h - height[i]);
  16. }
  17. return res;
  18. }

Two Pointer

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:

  1. Create a left pointer L = 0, right pointer R to size - 1
  2. Create left max LM and right max LM and a res of 0
  3. While L < R
  4. IF H[L] is smaller than H[R]
  5. Set LM to MAX(LM, H[L])
  6. RES += LM - H[L]
  7. Increment L
  8. Else
  9. Set RM to MAX(RM, H[R])
  10. RES += RM - H[R]
  11. Decrement R
  12. Return Res

Code:

  1. int trap(vector<int>& h) {
  2. // left pointer, right pointer, left max, right max, result
  3. int l = 0, r = h.size() - 1, lm = 0, rm = 0, res = 0;
  4.  
  5. while(l < r)
  6. {
  7. // move up the pointer to the smaller element
  8. if(h[l] < h[r])
  9. {
  10. lm = max(h[l], lm);
  11. res += lm - h[l++];
  12. }else
  13. {
  14. rm = max(h[r], rm);
  15. res += rm - h[r--];
  16. }
  17. }
  18. return res;
  19. }

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:

  1. int minDistance(string word1, string word2) {
  2.  
  3. int m = word1.length(), n = word2.length();
  4.  
  5. // return non zero length if a length is zero
  6. if(n*m == 0) return n+m;
  7.  
  8. // init memo vector to all zero's
  9. vector<vector<int>> memo(m + 1, vector<int>(n + 1,0));
  10.  
  11. // init left and top rows
  12. for(int i = 0; i <= m; i++)
  13. memo[i][0] = i;
  14. for(int j = 0; j <= n; j++)
  15. memo[0][j] = j;
  16.  
  17. for(int i = 1; i <= m; i++)
  18. {
  19. for(int j = 1; j <= n; j++)
  20. {
  21. if(word1[i-1] == word2[j-1])
  22. {
  23. memo[i][j] = memo[i-1][j-1];
  24. }
  25. else
  26. {
  27. memo[i][j] = min(min(memo[i][j-1], memo[i-1][j-1]), memo[i-1][j]) + 1;
  28. }
  29. }
  30. }
  31. // Return the last element
  32. return memo[m][n];
  33. }

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:

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

Code:

  1. bool isOneEditDistance(string s, string t) {
  2.  
  3. // we want bigger s, and smaller t
  4. int bigger = s.length(), smaller = t.length();
  5.  
  6. if(bigger < smaller)
  7. return isOneEditDistance(t, s);
  8.  
  9. // replace or equal
  10. if(bigger == smaller)
  11. {
  12. for(int i = 0; i < bigger; i++)
  13. {
  14. if(s[i] != t[i])
  15. return(s.substr(i+1) == t.substr(i+1));
  16. }
  17. // if we get to here, no replacement was made and the strings are equal
  18. // so we return false
  19. return false;
  20. }
  21.  
  22. // Delete one character from bigger s
  23. else if(bigger - smaller == 1)
  24. {
  25. for(int i = 0; i < smaller; i++)
  26. {
  27. if(s[i] != t[i])
  28. return(s.substr(i+1) == t.substr(i));
  29. }
  30. // if we get here it means the last character in the bigger string is what remains
  31. return true;
  32. }
  33. return false;
  34. }

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:

  1. FUNCTION: maxSub(string S1 and S2, pointers M and N, memo matrix)
  2. if M or N are 0, return 0
  3. if memo[M][N] is valid, return it
  4.  
  5. int x = 1 if S1[M-1] is equal to S2[N-1]
  6. int SAME = maxSub(S1, S2, M-1, N-1, memo) + x
  7. int DEL_S1 = maxSub(S1, S2, M-1, N, memo)
  8. int DEL_S2 = maxSub(S1, S2, M, N-1, memo)
  9.  
  10. return the max of the 3
  11.  
  12. FUNCTION isValid(S1, S2)
  13. M = S1 length, N = S2 length
  14. Make a memo vector that is M+1 and N+1, init all to -1
  15. return ( M + N - 2* maxSub(S1, S2, M, N, memo)

Code:

  1. // make our own fancy 3 way max function
  2. int max(int x, int y , int z)
  3. {
  4. return ::max(::max(x,y),z);
  5. }
  6.  
  7. // return max equal sub string of s1 and s2
  8. int maxSub(string& s1, string& s2, int m, int n, vector<vector<int>> &memo)
  9. {
  10. if(m * n == 0) return 0;
  11.  
  12. // If it's in the memo, return it!
  13. if (memo[m][n] != -1) { return memo[m][n]; }
  14.  
  15. int x = (s1[m - 1] == s2[n - 1]) ? 1 : 0;
  16. int same = maxSub(s1, s2, m - 1, n - 1,memo) + x;
  17. int del_s1 = maxSub(s1, s2, m - 1, n,memo);
  18. int del_s2 = maxSub(s1, s2, m, n - 1,memo);
  19.  
  20. memo[m][n] = max(same, del_s1, del_s2);
  21. return memo[m][n];
  22. }
  23.  
  24. int minDistance(string word1, string word2) {
  25. int m = word1.length(), n = word2.length();
  26.  
  27. vector<vector<int>> memo(m+1, vector<int>(n+1, -1));
  28. int max_sub = maxSub(word1, word2, m, n, memo);
  29.  
  30. return(m + n - 2*max_sub);
  31. }

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:

  1. int findLength(vector<int>& A, vector<int>& B) {
  2. int m = A.size(), n = B.size();
  3.  
  4. vector<vector<int>> memo(m+1, vector<int>(n+1, 0));
  5.  
  6. int ans = 0;
  7. for(int i = 1; i <= m; i++)
  8. {
  9. for(int j = 1; j <= n; j++)
  10. {
  11. if(A[i-1] == B[j-1])
  12. {
  13. memo[i][j] = memo[i - 1][j - 1] + 1;
  14. ans = max(memo[i][j], ans);
  15. }
  16. }
  17. }
  18. return ans;
  19. }

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):

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

Algorithm O(N):

  1. create min set to INT_MAX and max set to INT_MIN
  2. create unordered set
  3. iterate n over input
  4. if n in set
  5. dupe = n
  6. insert n in set
  7. min = min ( min and n)
  8. max = max ( max and n)
  9.  
  10. iterate i from min to max
  11. 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:

  1. p = nums[0] and q = to num [0]
  2. DETECT CYCLE
  3. while true
  4. move p twice
  5. move q once
  6. if p == q, break ( we have a cycle )
  7.  
  8. FIGURE OUT WHERE CYCLE IS BASED ON FLOYD'S ALGO
  9. q = nums[0]
  10. while(p != q)
  11. move p once
  12. move q once
  13.  
  14. return q :)

Code:

  1. int findDuplicate(vector<int>& nums) {
  2.  
  3. int p = nums[0], q = nums[0];
  4.  
  5. while(true)
  6. {
  7. p = nums[p]; p = nums[p];
  8. q = nums[q];
  9. if( p == q)
  10. break;
  11. }
  12.  
  13. q = nums[0];
  14. while(p != q)
  15. {
  16. p = nums[p];
  17. q = nums[q];
  18. }
  19.  
  20. return p;
  21. }

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:

  1. vector <int> findMedian(vector <int> arr) {
  2. vector<int> out;
  3. priority_queue<int> max_heap;
  4. // just have to remember a default priority_queue in c++ is a max_heap
  5. priority_queue<int, vector<int>, greater<int>> min_heap;
  6.  
  7. for(auto& num : arr){
  8. // If both heaps empty
  9. if(max_heap.size() == 0 && min_heap.size() == 0){
  10. max_heap.push(num);
  11. }
  12. // we assume that max heap will not be empty
  13. else{
  14. if(num > max_heap.top()){
  15. min_heap.push(num);
  16. }else{
  17. max_heap.push(num);
  18. }
  19. }
  20.  
  21. // Balance the heaps CAREFUL WITH SIZE TYPES
  22. if((int)max_heap.size() - (int)min_heap.size() > 1){
  23. min_heap.push(max_heap.top());
  24. max_heap.pop();
  25. }
  26. else if((int)min_heap.size() - (int)max_heap.size() > 1){
  27. max_heap.push(min_heap.top());
  28. min_heap.pop();
  29. }
  30.  
  31. // Calculate median
  32. if(max_heap.size() == min_heap.size()){
  33. out.push_back( (max_heap.top() + min_heap.top() ) / 2 );
  34. }else if(max_heap.size() > min_heap.size()){
  35. out.push_back(max_heap.top());
  36. }else{
  37. out.push_back(min_heap.top());
  38. }
  39. }
  40. return out;
  41. }

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:

  1. class HeapElement
  2. HeapElemetn constructor
  3. value
  4. i, j
  5. // convert to min heap
  6. overload the < operator
  7. a.i > b.i
  8.  
  9. priority_queue<HeapElement> minHeap
  10.  
  11. FUNC constructure( lists )
  12. for i to lists size
  13. if list[i] not empty
  14. insert HeapElement(list[i][0], i, 0) into min heap
  15.  
  16. FUNC next()
  17. if hasNext() is false
  18. return -1
  19.  
  20. get a copy of top element of heap, call it prevTop
  21. pop off the top element
  22. int out = prevTop.val
  23. prevTop.j++
  24. if prevTop.j is bounds of its list
  25. set prevTop.val to value at prevTop i j
  26. insert heapElement into min_heap;
  27. return out;
  28.  
  29. FUNC hasNext()
  30. return size of heap > 0

Code:

  1. // this will contain the data in our heap
  2. class HeapElement {
  3. public:
  4. int val, i, j;
  5. HeapElement(int _val, int _i, int _j) : val(_val), i(_i), j(_j){}
  6. };
  7.  
  8. // Overload the less than operator
  9. bool operator<(const HeapElement &a, const HeapElement &b){
  10. return a.val > b.val;
  11. }
  12.  
  13. class SortedIterator {
  14. private:
  15. // we need a reference to our input list
  16. const vector<vector<int>> &lists;
  17. priority_queue<HeapElement> minHeap;
  18. public:
  19. // Constructor
  20. SortedIterator(const vector<vector<int>> &_lists) : lists(_lists){
  21. for(int i = 0; i < (int)lists.size(); i++){
  22. if(lists[i].size() > 0){
  23. minHeap.push(HeapElement(lists[i][0], i, 0));
  24. }
  25. }
  26. }
  27.  
  28. // our iterator next function
  29. int next(){
  30. if(hasNext() == false){
  31. return -1;
  32. }
  33. HeapElement prevTop = minHeap.top();
  34. minHeap.pop();
  35. int out = prevTop.val;
  36.  
  37. if(++prevTop.j < (int)lists[prevTop.i].size()){
  38. prevTop.val = lists[prevTop.i][prevTop.j];
  39. minHeap.push(prevTop);
  40. }
  41. return out;
  42. }
  43.  
  44. // check if we have a next value
  45. bool hasNext(){
  46. return minHeap.size() > 0;
  47. }
  48. };

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:

  1. create memo array
  2. set memo[0][:] to 1
  3. set memo[:][0] to 1
  4.  
  5. for i 1 to m
  6. for j 1 to m
  7. memo[i][j] = memo[i-1][j] + memo[i][j-1]
  8.  
  9. return memo[size - 1][memo[0]size-1]

Code:

  1. int uniquePaths(int m, int n) {
  2. // vector of all 1's
  3. vector<vector<int>> memo(m,vector<int>(n,1));
  4.  
  5. for(int i = 1; i < m; i++)
  6. for(int j = 1; j < n; j++)
  7. memo[i][j] = memo[i-1][j] + memo[i][j-1];
  8.  
  9. return memo[m-1][n-1];
  10. }

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:

  1. int calculate(string s) {
  2. stack<int> myStack;
  3. char sign = '+';
  4. int res = 0, tmp = 0;
  5. for (unsigned int i = 0; i < s.size(); i++) {
  6. if (isdigit(s[i]))
  7. tmp = 10*tmp + s[i]-'0';
  8. if (!isdigit(s[i]) && !isspace(s[i]) || i == s.size()-1) {
  9. if (sign == '-')
  10. myStack.push(-tmp);
  11. else if (sign == '+')
  12. myStack.push(tmp);
  13. else {
  14. int num;
  15. if (sign == '*' )
  16. num = myStack.top()*tmp;
  17. else
  18. num = myStack.top()/tmp;
  19. myStack.pop();
  20. myStack.push(num);
  21. }
  22. sign = s[i];
  23. tmp = 0;
  24. }
  25. }
  26. while (!myStack.empty()) {
  27. res += myStack.top();
  28. myStack.pop();
  29. }
  30. return res;
  31. }

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.

  1. ListNode* reverseBetween(ListNode* head, int m, int n) {
  2. ListNode dh;
  3. dh.next = head;
  4. ListNode *pre = &dh, *cur = head;
  5.  
  6. n = n - m;
  7.  
  8. // move pre and cur down till we hit m
  9. while(m > 1){
  10. pre = pre->next;
  11. cur = cur->next;
  12. m--;
  13. }
  14.  
  15. // handle our swaps
  16. while(n > 0){
  17. ListNode* next = cur->next;
  18. cur->next = next->next;
  19. next->next = pre->next;
  20. pre->next = next;
  21. n--;
  22. }
  23. return dh.next;
  24. }

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:

  1. Make pointer q and q both equal to head
  2.  
  3. while q and p, and p->next
  4. p advance twice
  5. q advance once
  6. if p == q, break
  7.  
  8. When we get here we either have a loop or an NULL end.
  9. if( !p OR !p->next) // the OR order is important, so we don't have runtime errors
  10. We have the end, so no loop! return NULL
  11.  
  12. We have loop, so we have to find where it starts
  13. q = head
  14. while p != q
  15. p advance once
  16. q advance once
  17.  
  18. return q // or q, it doesn't matter :)

Code:

  1. ListNode *detectCycle(ListNode *head) {
  2.  
  3. ListNode *q = head, *p = head;
  4.  
  5. while(q && p && p->next != NULL)
  6. {
  7. p = p->next; p = p->next;
  8. q = q->next;
  9. if(q == p)
  10. break;
  11. }
  12.  
  13. if(!p || p->next == NULL)
  14. return NULL;
  15.  
  16. q = head;
  17. while(p != q)
  18. {
  19. p = p->next;
  20. q = q->next;
  21. }
  22. return q;
  23. }

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.

  1. class Solution {
  2. public:
  3.  
  4. void insertAfter(Node* node, int i)
  5. {
  6. Node* temp = new Node(i);
  7. temp->next = node->next;
  8. node->next = temp;
  9. }
  10.  
  11. Node* insert(Node* head, int insert_val) {
  12.  
  13. // Lets take care of the NULL case
  14. if(head == NULL)
  15. {
  16. Node* temp = new Node(insert_val);
  17. temp->next = temp;
  18. return temp;
  19. }
  20.  
  21. // two pointers
  22. Node *p = head, *n = head->next;
  23.  
  24. while(n != head)
  25. {
  26. if(p->val <= insert_val && insert_val <= n->val)
  27. {
  28. insertAfter(p, insert_val);
  29. return head;
  30. }
  31. else if(p->val > n->val)
  32. {
  33. if(p->val <= insert_val || insert_val <= n->val)
  34. {
  35. insertAfter(p, insert_val);
  36. return head;
  37. }
  38. }
  39. p = n;
  40. n = n->next;
  41. }
  42.  
  43. insertAfter(p, insert_val);
  44.  
  45. return head;
  46. }
  47. };

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:

  1. FUNCTION split(head)
  2. if head is null return head
  3. slow pointer and faster pointer equal to head
  4. prev pointer
  5. while fast and fast next is not null
  6. prev = slow
  7. fast = fast next
  8. slow = slow next
  9. if slow != head
  10. prev next = null
  11. return slow
  12.  
  13. FUNCTION treenode sortedListToBST(head)
  14. if head is null return NULL
  15. listnode mid = split(head)
  16. TreeNode root = new treenode mid val
  17. if mid != head
  18. left = sortedListToBST(head);
  19. right = sortedList(mid->next)
  20. return root
  1. ListNode* split(ListNode *head){
  2. if(head == NULL){
  3. return NULL;
  4. }
  5. ListNode *slow = head, *fast = head, *prev = head;
  6. while(fast != NULL && fast->next != NULL){
  7. prev = slow;
  8. slow = slow->next;
  9. fast = fast->next->next;
  10. }
  11. if(slow != head){
  12. prev->next = NULL;
  13. }
  14. return slow;
  15. }
  16.  
  17. TreeNode* sortedListToBST(ListNode* head) {
  18. if(head == NULL){
  19. return NULL;
  20. }
  21. ListNode *mid = split(head);
  22. TreeNode *root = new TreeNode(mid->val);
  23.  
  24. // left list is going to be started with head
  25. // right list is started with mid->next
  26.  
  27. // if we have a real left list
  28. if(mid != head){
  29. root->left = sortedListToBST(head);
  30. }
  31. root->right = sortedListToBST(mid->next);
  32.  
  33. return root;
  34. }

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:

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

Code:

  1. // how much we have to add to a to get to b
  2. char dist(char a, char b)
  3. {
  4. int d = b - a;
  5. return (d < 0) ? d += ('z' - 'a' + 1) : d;
  6. }
  7.  
  8. vector<vector<string>> groupStrings(vector<string>& strings) {
  9.  
  10. vector<vector<string>> out;
  11. unordered_map<string, int> shift_map;
  12.  
  13. for(auto& s : strings)
  14. {
  15. // build our key for this string
  16. string key;
  17. for(int i = 1; i < s.length(); i++ )
  18. {
  19. key += dist(s[i-1], s[i]);
  20. }
  21.  
  22. if(shift_map.find(key) == shift_map.end())
  23. {
  24. // not in the map, create new entry
  25. out.push_back({s});
  26. shift_map[key] = out.size() - 1;
  27. }
  28. else
  29. {
  30. out[shift_map[key]].push_back(s);
  31. }
  32. }
  33. return out;
  34. }

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:

  1. FUNCTION Explore(Yearbook PATH, vertex V, set SEEN)
  2. if V in SEEN
  3. return
  4. insert V in SEEN
  5. explore(PATH[V-1])
  6.  
  7. FUNC signature(Yearbook PATH)
  8. out vector initalized to PATH size + 1 of -1's
  9. iterate i from 1 to PATH size inclusive
  10. if out[i] != -1
  11. explore(i)
  12. iterate E over elements in SEEN
  13. out[E] = SEEN size
  14. out.erase(out.begin)
  15. return out
  1. void explore(vector<int> &arr, unordered_set<int> &seen, int v)
  2. {
  3. if(seen.count(v) > 0){
  4. return;
  5. }
  6. seen.insert(v);
  7. explore(arr, seen, arr[v-1]);
  8. return;
  9. }
  10.  
  11. vector <int> findSignatureCounts(vector <int> arr) {
  12. int n = arr.size();
  13. vector<int> out(n, -1);
  14. for(int i = 1; i <= n; i++){
  15. // an unexplored yearbook
  16. if(out[i-1] == -1){
  17. unordered_set<int> seen;
  18. explore(arr, seen, i);
  19. for(auto& e : seen){
  20. out[e-1] = seen.size();
  21. }
  22. }
  23. }
  24. return out;
  25. }

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.

Cycle detection and optimization

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:

  1. OPTIMIZATION: Build unordered set of explored vertices called GOOD
  2. Build adjacency list Adj (unoredered map of vector<int>)
  3. Iterate over edges, adj[left vertex].push_back(right vertex)
  4.  
  5. Iterate v over Adj list
  6. OPT: If v is in good, CONTINUE, no need to check
  7. create seen set of ints
  8. If cycleDFS of v vertex returns TRUE, we have a cycle
  9. return false
  10.  
  11. // Return true if there is a cycle, false otherwise
  12. FUNCTION cycleDFS( take in Adj, seen, and vertex v)
  13. OPT: If v is in good, return false, no need to check
  14. check if v in seen
  15. If true, return true, there is a cycle
  16. iterate over n Neighbors of vertex v
  17. OPT: If n is in good, continue
  18. If cycleDFS of n is true
  19. return true
  20. // if we are here there are no cycles
  21. Remove v from seen, so we can backtrack without false positives
  22. return false

  1. class Solution {
  2. public:
  3. // This marks nodes that are already explored as good
  4. unordered_set<int> good;
  5.  
  6. bool cycleDFS(unordered_map<int, vector<int>>& adj, int v, unordered_set<int>& seen)
  7. {
  8. if(good.find(v) != good.end())
  9. return false;
  10.  
  11. // If we found this node before, we have a cycle
  12. if(seen.find(v) != seen.end())
  13. return true;
  14.  
  15. seen.insert(v);
  16.  
  17. // Iterate over neighbors
  18. for(auto& n : adj[v])
  19. {
  20. if(good.find(n) != good.end())
  21. continue;
  22. if( cycleDFS(adj, n, seen) )
  23. return true;
  24. }
  25. // we have come to the end of this exploration.
  26. seen.erase(v);
  27. good.insert(v);
  28. return false;
  29. }
  30.  
  31. bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
  32.  
  33. // Build the adjacency list
  34. unordered_map<int, vector<int>> adj;
  35. for(auto& e : prerequisites) {
  36. adj[e[0]].push_back(e[1]);
  37. }
  38.  
  39. // Iterate over the adjancey list, and run cycleDFS on each node
  40. for(auto& v : adj)
  41. {
  42. // This is our optimization. If we enouter a vertex we have already
  43. // marked as good, we don't a DFS on it
  44. if(good.find(v.first) != good.end())
  45. continue;
  46. // we start an empty seen set for every exploration
  47. // if we didn't we would encounter nodes from other explorations
  48. unordered_set<int> seen {};
  49. if(cycleDFS(adj, v.first, seen))
  50. {
  51. return false;
  52. }
  53. }
  54. return true;
  55. }
  56. };

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:

  1. class Solution {
  2. public:
  3. // we need to keep a set to allow O(1) lookups of elements present,
  4. // but we still need to keep an order which will be output
  5. vector<int> taken_list;
  6. unordered_set<int> taken;
  7.  
  8. bool DFS(unordered_map< int, vector<int> >& adj, unordered_set<int> &seen, int v)
  9. {
  10. if(taken.find(v) != taken.end())
  11. return true;
  12. if(seen.find(v) != seen.end())
  13. return false;
  14.  
  15. // only run neighbor check on vertices that have adj list
  16. if(adj.count(v) > 0)
  17. {
  18. // insert v into seen to mark that we saw it on this path
  19. seen.insert(v);
  20. // iterate over v's neighbors
  21. for(auto& n : adj[v])
  22. {
  23. // if we taken this class we don't need dfs
  24. if(taken.find(n) != taken.end())
  25. continue;
  26. if( DFS(adj, seen, n) == false)
  27. return false;
  28. }
  29. seen.erase(v);
  30. }
  31. // add the class to the taken list
  32. taken.insert(v);
  33. taken_list.push_back(v);
  34. return true;
  35. }
  36.  
  37. vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
  38. taken_list.reserve(numCourses);
  39. // build adj list
  40. unordered_map< int, vector<int> > adj;
  41. for(auto& e : prerequisites){
  42. adj[e[0]].push_back(e[1]);
  43. }
  44.  
  45. for(int v = 0; v < numCourses; v++)
  46. {
  47. // if we already took the class, then we don't have to explore it
  48. if(taken.find(v) != taken.end())
  49. continue;
  50. unordered_set <int> seen;
  51. if( DFS(adj, seen, v) == false)
  52. return {};
  53. }
  54. return taken_list;
  55. }
  56. };

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:

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

Code:

  1. int scheduleCourse(vector<vector<int>>& courses) {
  2. // set of durations of classes that we have taken
  3. multiset<int, greater<int>> taken;
  4.  
  5. // sort our courses by end date
  6. sort(courses.begin(), courses.end(),
  7. [](vector<int>&a, vector<int>&b){return a[1]<b[1];});
  8.  
  9. int last_end = 0;
  10. for(int i = 0; i < courses.size(); i++)
  11. {
  12. // can you this course? is the end time smaller equal to deadline
  13. if(courses[i][0] + last_end <= courses[i][1])
  14. {
  15. last_end += courses[i][0];
  16. taken.insert(courses[i][0]);
  17. }
  18. else
  19. {
  20. // lets try to swap this course the biggest possible taken one
  21. int old_len = *taken.begin();
  22. if(old_len >= courses[i][0])
  23. {
  24. // swap the courses
  25. taken.erase(taken.begin());
  26. taken.insert(courses[i][0]);
  27. // we also have to shift over our time savings!
  28. last_end -= old_len - courses[i][0];
  29. }
  30. }
  31. }
  32. return taken.size();
  33. }

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:

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

Code:

  1. int findMinArrowShots(vector<vector<int>>& points) {
  2. // Sort by end first
  3. sort(points.begin(), points.end(),[](vector<int>&a, vector<int>&b){return a[1]<b[1];});
  4.  
  5. // Initialize last end to smaller number than possible with int
  6. long last_end = LONG_MIN, ans = 0;
  7. for(int i = 0; i < points.size(); i++)
  8. {
  9. // If the current point ends after the previous, we need a new arrow
  10. if(points[i][0] > last_end)
  11. {
  12. ans++;
  13. // Update last end
  14. last_end = points[i][1];
  15. }
  16. }
  17. return ans;
  18. }

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:

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

Code:

  1. int greedyMeeting(vector<vector<int>> &m)
  2. {
  3. sort(m.begin(), m.end(),[](vector<int>&a, vector<int>&b){ return a[1]<b[1];});
  4. int last_end = -1, ans = 0;
  5. for(int i = 0; i < (int)m.size(); i++)
  6. {
  7. if(m[i][0] >= last_end)
  8. {
  9. // take the meeting
  10. last_end = m[i][1];
  11. ans++;
  12. cout << "Taking meeting number: " << ans << " - "
  13. << m[i][0] << ":" << m[i][1] << endl;
  14. }
  15. }
  16. return ans;
  17. }

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:

  1. bool compare(const vector<int>& a, const vector<int>&b)
  2. {
  3. // a will go before b if this is true:
  4. return ( a[0] < b[0] );
  5. }
  6.  
  7. 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.

  1. bool compare(const vector<int> &a, const vector<int> &b)
  2. {
  3. // element a[0] should come before b[0] if it is smaller
  4. return a[0] < b[0];
  5. }
  6.  
  7. class Solution{
  8. public:
  9.  
  10. void process(multiset<int> &rooms, vector<int>& interval)
  11. {
  12. // check to see if earliest ending meeting is <= to our start
  13. if(*rooms.begin() <= interval[0])
  14. {
  15. // erase our old meeting because we are gonna put in the new one :)
  16. rooms.erase(rooms.begin());
  17. }
  18. // put in the new end time
  19. rooms.insert(interval[1]);
  20. }
  21.  
  22. int minMeetingRooms(vector<vector<int>> &intervals)
  23. {
  24. if(intervals.size() == 0) return 0;
  25. // sort our intervals by start time, earliest first
  26. sort(intervals.begin(), intervals.end(), compare);
  27.  
  28. // make a multiset of rooms so we can store end times of the last meeting
  29. // there may be end times that end at the same time, so we need to allow for
  30. // dupes
  31. multiset<int> rooms = { intervals[0][1] };
  32.  
  33. for(int i = 1; i < intervals.size(); i++)
  34. {
  35. process(rooms, intervals[i]);
  36. }
  37.  
  38. return rooms.size();
  39. }
  40. };

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.

  1. FUNC: isPossible(array INPUT)
  2. MAX_REACH = 0, i = 0;
  3. Increment i from 0 to either INPUT size or MAX_REACH
  4. MAX_REACH = max ( MAX_REACH, INPUT[i]+i )
  5. 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:

  1. class Solution {
  2. public:
  3. double myPow(double x, int n) {
  4.  
  5. double ans = 1;
  6.  
  7. if(n == 0)
  8. return 1;
  9.  
  10. for(int i = 1; i <= abs(n); i++)
  11. {
  12. ans = x * ans;
  13. }
  14.  
  15. if(n < 0)
  16. ans = 1/ans;
  17.  
  18. return ans;
  19.  
  20. }
  21. };

  1. class Solution {
  2. public:
  3. double fastPow(double x, long long n)
  4. {
  5. if ( n == 0)
  6. return 1.0;
  7. double half = fastPow(x, n / 2);
  8. if( n % 2 == 0)
  9. {
  10. return half * half;
  11. }
  12. else
  13. {
  14. return half * half * x;
  15. }
  16. }
  17.  
  18. double myPow(double x, int n) {
  19. long long N = n;
  20. if(N < 0)
  21. {
  22. x = 1/x;
  23. N = -N;
  24. }
  25.  
  26. return fastPow(x, N);
  27. }
  28. };

Did a vector erase first but that wasn't ideal. I then learned how to do it with a two pointer approach. First pointer is a “last valid” location and second pointer sweeps through array. As it sweeps and find good ones, it swaps them with the valid. Valid then becomes my new array size.

Really interesting one cause theres dupes and rotations. Idea is to split the array and based on its bounds, you have 3 possible situations:

  • You have a normal sorted list cause left bound smaller than right bound. Do a normal bin search
  • Left bound is == to right bound, do a linear search
  • You have a pivot somewhere. You check to see if the left array is sorted right. If it is, check to see if your target is in it. If it is, search in it.
  • If it isn't in it, it's gotta be on the other side! Remove duplicates from a sorted list

Leetcode 86.

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions.

Make sure elements greater. Had a hard time with this one because I picked a bad approach from the start. I was moving elements to the back of the list if they met a certain condition. Problem was that I entered an infinite loop because I would get to the nodes I pushed back and keep pushing them back.

I then solved it by looking for groups of nodes that are bigger than x. I Then moved them with a node after them that was less than x.

Algorithm:

  1. ListNode dh(0, head);
  2. ListNode *prev = &dh, *cur = head;
  3.  
  4. while(cur != NULL){
  5. if(prev->next->val < x){
  6. prev = prev->next;
  7. }
  8. if(cur->val >= x){
  9. while(cur->next != NULL && cur->next->val >= x){
  10. cur = cur->next;
  11. }
  12.  
  13. if(cur->next == NULL){
  14. return dh.next;
  15. }
  16.  
  17. ListNode* next = cur->next;
  18. cur->next = next->next;
  19. next->next = prev->next;
  20. prev->next = next;
  21. }else{
  22. cur = cur->next;
  23. }
  24. }
  25. return dh.next;
  26. }

There is a MUCH EASIER way to do this! Build two lists, one less than and one greater than, and then connect them in the end!!!!!!! Watch this video.

Leetcode 198.

What a great problem! I first tried a greedy approach by picking the largest element first, setting it and its neighbors to 0, and then picking the next largest element, and repeat n/2 times. This fails for [2,3,2]] as it generates 3 instead of 4.

Dynamic programming with bottom up processing. If we are asked to solve a problem for the n'th thing, we solve for the i'th thing n times.

Code Recursive:

  1. int explore(vector<int>& nums, int i){
  2. int yes = 0, no = 0;
  3. // base case
  4. if(i >= nums.size()){
  5. return 0;
  6. }
  7.  
  8. // choose
  9. yes = nums[i] + explore(nums, i+2);
  10.  
  11. // unchoose
  12. no = explore(nums, i+1);
  13.  
  14. return max(yes, no);
  15. }
  16.  
  17. int rob(vector<int>& nums) {
  18. return explore(nums, 0);
  19. }

Code DP:

  1. int rob(vector<int>& nums) {
  2. // solve for the first 3 cases
  3. if(nums.size() == 0) { return 0; }
  4. if(nums.size() == 1) { return nums[0]; }
  5. if(nums.size() == 2) { return max(nums[0], nums[1]); }
  6.  
  7. // create the dp matrix
  8. vector<int> dp(nums.size(), 0);
  9.  
  10. // build the dp matrix and seed it with the first two cases
  11. dp[0] = nums[0];
  12. dp[1] = max(nums[0], nums[1]);
  13.  
  14. // iterate over the rest
  15. for(int i = 2; i < nums.size(); i++){
  16. dp[i] = max(dp[i-2] + nums[i], dp[i-1]);
  17. }
  18.  
  19. return dp.back();
  20. }

Code Simple DP (Kadane):

  1. int rob(vector<int>& nums) {
  2. int prev = 0, cur = 0;
  3. for(auto& num : nums){
  4. // temp keeps the max of one house ago
  5. int temp = cur;
  6. cur = max(prev + num, cur);
  7. prev = temp;
  8. }
  9. return cur;
  10. }

Maximum Subarray Greedy / Kadane's Algorithm

This problem can be solved amazingly easily in a one pass greedy approach. You keep track of a local maximum that can reset, and a global maximum.

  1. int maxSubArray(vector<int>& nums) {
  2. int cur_max = nums[0], max_out = nums[0];
  3.  
  4. for(int i = 1; i < nums.size(); i++)
  5. {
  6. cur_max = max(nums[i], cur_max + nums[i]);
  7. max_out = max(cur_max, max_out);
  8. }
  9. return max_out;
  10. }

This is a tricky algorithm to understand. It touches on dynamic programming. Here's a good write up on it.

Maximum Subarray Divide and Conquer

Good video here.

The maximum subarray problem can be solved using divide and conquer.

By breaking up the input array into two subarrays of $n/2$ length as follows:

  • A[low..mid]
  • A[mid+1..high]

The maximum subarray A[i..j] can only be located in one of 3 places; in the first one, crossing the middle, or the end. To solve this equation we must find the maximum subarray in each of those 3 places and simply pick the biggest one.

Theres lots of little details in the maxCross function. Especially with dealing with finding the maximum of the subarrays when you have negative numbers. Where you start on the mid line counts. You had to go mid to left and mid+1 to the right. If you go mid-1 to the left you're screwed.

Find-Max-Crossing-Subarray Algorithm

  1. int maxCross(vector<int>&nums, int& l, int &mid, int& r)
  2. {
  3. // We don't have to do bounds checks because we know l won't equal r,
  4. // because that's check for in the caller function.
  5. // With that knowledge we can set max_l and max_r both to INT_MIN's cause
  6. // I know there is going to be at least one element in each. You can also
  7. // set to nums[mid] and nums[mid+1]
  8. int max_l = INT_MIN, max_r = INT_MIN;
  9.  
  10. // find max left
  11. int sum = 0;
  12. for(int left = mid; left >= l; left-- )
  13. {
  14. sum += nums[left];
  15. max_l = max(sum, max_l);
  16. }
  17. // find max right
  18. sum = 0;
  19. for(int right = mid+1; right <= r; right++ )
  20. {
  21. sum += nums[right];
  22. max_r = max(sum, max_r);
  23. }
  24. // return the added sum.
  25. return max_l + max_r;
  26. }
  27.  
  28. int maxSub(vector<int>& nums, int l, int r)
  29. {
  30. if(l == r)
  31. return nums[l];
  32. int mid = (l+r) / 2;
  33. int max_left = maxSub(nums, l, mid);
  34. int max_right = maxSub(nums, mid + 1, r);
  35. int max_cross = maxCross(nums, l, mid, r);
  36. return max(max_left, max(max_right, max_cross) );
  37. }
  38.  
  39. int maxSubArray(vector<int>& nums) {
  40. if(nums.size() == 0) return NULL;
  41. return maxSub(nums, 0, nums.size()-1);
  42. }

This problem can also be solved very easily with a greedy version. Maximum Subarray Greedy

Leet Code Problem

There are variations to the Kadane's algorithm. Here is a buy and sell stock. The idea is to keep track of the minimum price, and then check the current minimum against the current price. You then check that potential profit against a running max_profit variable.

  1. int maxProfit(vector<int>& prices) {
  2.  
  3. int max_profit = 0, min_price = INT_MAX;
  4.  
  5. for(int i = 0; i < prices.size(); i++)
  6. {
  7. min_price = min(prices[i], min_price);
  8. max_profit = max(max_profit, prices[i] - min_price);
  9. }
  10. return max_profit;
  11. }

Leetcode 152.

Very interesting problem, that requires a clever extension of Kadane. The trick here is that negative numbers can flip a minimum to a maximum.

You keep track of a min_so_far, which is min of current number, current number times min so for, and current number times max so far.

And you keep track of a max_so_far which is the max of current number, current number times max_so_far and current number times min_so_far. Then you keep track of a result max, which you max against max_so_far.

Amazingly you get to test every possible subarray in one pass. Really awesome!

  1. int maxProduct(vector<int>& nums)
  2. {
  3. int min_so_far = nums[0], max_so_far = nums[0], result = nums[0];
  4.  
  5. for(int i = 1; i < nums.size(); i++)
  6. {
  7. int cur = nums[i];
  8. int temp_max = max(nums[i], max( nums[i] * min_so_far, nums[i] * max_so_far));
  9. min_so_far = min(nums[i], min( nums[i] * min_so_far, nums[i] * max_so_far));
  10. max_so_far = temp_max;
  11. result = max(max_so_far, result);
  12. }
  13. return result;
  14. }

Leetcode 238.

Very cool little problem that you solve by creating “product list” which is similar to a prefix sum. You do a pass from the left and create this product list, and then come in from the left one element at a time. You rely on the fact that out[i] = prod * a[i - 1]. prod is the running product from the left.

  1. vector<int> productExceptSelf(vector<int>& nums) {
  2.  
  3. vector<int> out(nums.size(), 0);
  4.  
  5. int left_prod = 1;
  6. for(int i = 0; i < nums.size() - 1; i++)
  7. {
  8. left_prod *= nums[i];
  9. out[i] = left_prod;
  10. }
  11.  
  12. int right_prod = 1;
  13. for(int i = nums.size() - 1; i > 0; i--)
  14. {
  15. out[i] = right_prod * out[i - 1];
  16. right_prod *= nums[i];
  17. }
  18. out[0] = right_prod;
  19.  
  20.  
  21. return out;
  22. }

Leetcode 209.

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

I solved this problem using a two pointer approach. The two pointers bound a subarray whose sum is updated as the pointers move. The trick is how to advanced the pointers. The right pointer moves up if the sum doesn't meet the condition. The left pointer moved up if the sum meets the condition.

I also worried about the case where the left pointer advanced over the right pointer but that is actually fine. The left pointer can only advanced over the right pointer once, at which case the sum will be 0 and invalidate the case.

Algorithm:

  1. Function: min subarray : take in nums array and number s
  2. left = 0, min_length = 0, sum = 0
  3.  
  4. iterate right from 0 to nums size
  5. sum += nums[i]
  6. while sum is greater than s
  7. min_length = min( min_length, i - left + 1 )
  8. remove nums[last] from sum
  9. move up left pointer
  10. return min_length

Leetcode 3.

Given a string, find the length of the longest substring without repeating characters.

Find the longest substring without repeating characters. Cute use of an unordered_set to keep track of seen characters while implement two pointers for a sliding window. The sliding window is your valid substring. You have a left and right pointer. Advance the right pointer and if the character is not in the set, great, ans = max(right - left, ans). If the character is found in the set, remove the character at the left pointer, advancing the left and try again. Point is you keep advancing the left pointer till you're good to advance the right. Worst case, the left pointer will go all the way to the right and you start with an empty set. Cool!

  1. int lengthOfLongestSubstring(string s) {
  2. unordered_set<char> seen;
  3.  
  4. int i = 0, j = 0, n = s.length(), ans = 0;
  5.  
  6. while(i < n && j < n)
  7. {
  8. if( seen.find(s[j]) == seen.end() )
  9. {
  10. seen.insert(s[j++]);
  11. ans = max(ans, j - i);
  12. }
  13. else
  14. {
  15. seen.erase(s[i++]);
  16. }
  17. }
  18. return ans;
  19. }

Leetcode 438.

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Nice and mellow problem! Make a key from the pattern of the characters and counts, keep a sliding window on the string with with characters and counts and compare to the key. If it's a match, add the index to the output.

I learned that you can just use the == operator on 2d vectors and unordered maps.

  1. Create key of characters and counts
  2. Create a window key of empty characters and counts, and output list
  3. Iterate i from 0 to end of input string s
  4. add character at i to window key
  5. if i - p.length() is >= to zero, remove character from window key
  6. compare window and key, if match add i - p length + 1 to output
  7. Return output

Vector based code;

  1. vector<int> findAnagrams(string s, string p) {
  2. vector<vector<int>> key = vector(26,vector<int>(1,0));
  3. vector<vector<int>> window = vector(26,vector<int>(1,0));
  4. // build our key
  5. for(auto& c : p)
  6. key[c-'a'][0]++;
  7.  
  8. vector<int> out;
  9. for(int i = 0; i < s.length(); i++)
  10. {
  11. window[s[i]-'a'][0]++;
  12. int last_valid = i - p.length();
  13. if(last_valid >= 0)
  14. window[s[last_valid]-'a'][0]--;
  15. if(check())
  16. out.push_back(last_valid + 1);
  17. }
  18. return out;
  19. }

Map based code:

  1. vector<int> findAnagrams(string s, string p) {
  2.  
  3. unordered_map<char, int> key, window;
  4.  
  5. // build our key
  6. for(auto& c : p)
  7. key[c]++;
  8.  
  9. vector<int> out;
  10. for(int i = 0; i < s.length(); i++)
  11. {
  12. window[s[i]]++;
  13. int last_valid = i - p.length();
  14. if(last_valid >= 0)
  15. {
  16. window[s[last_valid]]--;
  17. if(window[s[last_valid]] == 0)
  18. window.erase(s[last_valid]);
  19. }
  20. if(key == window)
  21. out.push_back(last_valid + 1);
  22. }
  23. return out;
  24. }

Leetcode 131.

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

The trickiest part of this problem is implementing a way of partitioning the string in a sliding window fashion. The easiest way to do this is to create new substrings A and B but this takes time and memory that unnecessary because our input string and two pointers, start and end is all we need to define any substring in S.

Algorithm:

  1. FUNCTION isPalindrome ( string s, left pointer, right pointer)
  2. while left pointer is less than right pointer
  3. if character under left pointer is not the same as right pointer character
  4. return false
  5. return true
  6.  
  7. FUNCTION explore(string S, int START,
  8. array of string CUR, array of array of strings OUT)
  9. if START is equal to string length
  10. push in CUR to OUT, and return
  11. Iterate from I = START to S.length()
  12. if the string from START to I is NOT a palindrome, continue
  13. create a substring that goes from START to I and push it into CUR
  14. explore S, i + 1, CUR, OUT
  15. pop the last element of CUR
  16.  
  17. Call explore with START of 0

Code:

  1. // return true if string is palindrome, false otherwise
  2. bool isPalin(string& in, int start, int end)
  3. {
  4. int l = start, r = end;
  5. while(l < r)
  6. {
  7. if(in[l++] != in[r--])
  8. return false;
  9. }
  10. return true;
  11. }
  12.  
  13. // partition string into all possible partitions
  14. void part(string& s, int start, vector<string> &cur, vector<vector<string>> &out)
  15. {
  16. if(s.length() == start)
  17. {
  18. out.push_back(cur);
  19. return;
  20. }
  21.  
  22. // partitioning
  23. for(int i = start; i < s.length() ; i++)
  24. {
  25. if(!isPalin(s, start, i)) continue;
  26.  
  27. cur.push_back(s.substr(start, i - start + 1));
  28. part(s,i + 1, cur, out);
  29. cur.pop_back();
  30. }
  31. return;
  32. }
  33.  
  34. vector<vector<string>> partition(string s) {
  35. vector<vector<string>> out;
  36. vector<string> cur;
  37. part(s,0, cur, out);
  38. return out;
  39. }

Tricky son-of-a-gun. Easiest way is to brute force, and check if every possible substring is a palindrome.

Next best thing is O(n²) solution by doing a two pass. First pass you check every character and go middle out, next pass find any double characters and then middle out them.

Leetcode Problem 336.

Easiest is to brute force. It would be n²*k where k is the length of the string.

You solve this by created a hashtable of the words in the array. Then you have these cases to deal with:

  1. Finding a word which is the exact reverse of the word you have
  2. Finding a shorter word that would be prepended to the word you have
  3. Finding a shorter word that would be appended to the word you have and make it a palindrome

The way to deal with prepend and append, is to take the word that you have, pop off a character and save that to a new word. If the new word is a palindrome, and you can find the reversed version of the original word without the popped off bits, you good bro.

Append Example:

  1. // Matching the following:
  2. word1 = petonot
  3. word2 = ep
  4. word3 = tonote
  5.  
  6. revered_word1 = tonotep
  7.  
  8. You keep pooping off and looking and if what you popped off by itself is a
  9. palindrome, and you foudn the reverse of whats left, you're good
  10.  
  11. | Reversed | Poppedoff | Popped off | Found Match? | Reversed | Reversed |
  12. | | | Palindrome? | Popped off? | Palindrome? | Match? |
  13. |----------+-----------+-------------+--------------+-------------+----------|
  14. | tonotep | | Yes | No | No | No |
  15. | onotep | t | Yes | No | No | No |
  16. | notep | to | No | No | No | No |
  17. | otep | ton | No | No | No | No |
  18. | tep | tono | No | No | No | No |
  19. | ep | tonot | Yes | Yes | No | Yes |
  20. | p | tonote | No | No | Yes | Yes |

The hashtable gives the 0(1) lookup speed, and avoids the linear search.

This is a backtracking algorithm where you either close or open a parenthesis.

Leetcode 621

Given a characters array tasks, return the least number of units of times that the CPU will take to finish all the given tasks.

This problem needs to be broken down into some basic parts:

  1. The result is the count of tasks plus whatever idle time we have
  2. The frequency of the tasks we need
  3. The problem is bounded by the task with the maximum frequency
  4. Edge case of having multiple tasks with a max frequency

There are some bits in the algorithm that look tricky, like the min's and max's but if you go back to the basic keys for solving this problem, it will make sense!

  1. Function: least Interval ( tasks, n cooldown)
  2. Create a vector of frequencies
  3. Sort the frequencies from high to low
  4.  
  5. idle_time = maximum ( frequency - 1 ) * n
  6.  
  7. iterate i from 1 to end
  8. Subtract from idle_time the min frequency of the task OR the max freq - 1
  9.  
  10. return tasks size + max(idle time or 0 incase it's negative
  1. int leastInterval(vector<char>& tasks, int n) {
  2. vector<int> freq(26, 0);
  3. for(auto& task : tasks){
  4. freq[task - 'A']++;
  5. }
  6.  
  7. sort(freq.begin(), freq.end(), greater<int>());
  8.  
  9. int idle_time = (freq[0] - 1) * n;
  10.  
  11. for(size_t i = 1; i < freq.size(); i++){
  12. idle_time -= min(freq[0] - 1, freq[i]);
  13. }
  14.  
  15. return tasks.size() + max(idle_time, 0);
  16. }

Leetcode 116

Took me a little bit of time to get my head around how to do it, but it was not bad at the end! You pass in a right node to each explore iteration. The left child gets passed in the right child and then right child gets passed in NULL or right child→child. Thats it!

Algorithm:

Code:

  1. void explore(Node* node, Node* pr)
  2. {
  3. if(node == NULL) return;
  4.  
  5. node->next = pr;
  6.  
  7. //if we have children:
  8. if(node->left && node->right)
  9. {
  10. // left child
  11. explore(node->left, node->right);
  12. // right child:
  13. if(pr == NULL)
  14. explore(node->right, NULL);
  15. else
  16. explore(node->right, pr->left);
  17. }
  18. return;
  19. }
  20.  
  21. Node* connect(Node* root) {
  22. explore(root, NULL);
  23. return root;
  24. }

Leetcode 114

This one was took a bit of time to wrap my head around it. I originally starting trying to check for a node with no grand-children. Remember, if you are checking for grandchildren in a recursive tree traversal, you are doing something wrong!

The trick here is that you need to break down the problem to a simple bottom base node, and work out the 4 different conditions:

  1. No children
  2. Left present, Right null
  3. Left null, Right present
  4. Left and Right present

The second important thing is to realise you need to return a tail, which will be the lowest right node of this newly shuffled subtree. When a node is null, it should return null, and when it has no children, it should return itself. Those are two base case returns.

We then have to deal with the return of the node that received either of those two returns from left and right children.

Algorithm:

Code:

  1. TreeNode* flatten_child(TreeNode* node)
  2. {
  3. if( node == NULL ) return NULL;
  4.  
  5. // no children to move, this is the right tail
  6. if( node->left == NULL && node->right == NULL )
  7. return node;
  8.  
  9. TreeNode* left_tail = flatten_child(node->left );
  10. TreeNode* right_tail = flatten_child(node->right);
  11.  
  12. if(node->left != NULL)
  13. {
  14. left_tail->right = node->right;
  15. node->right = node->left;
  16. node->left = NULL;
  17. }
  18.  
  19. // return the right most real tail
  20. if(right_tail == NULL)
  21. return left_tail;
  22.  
  23. return right_tail;
  24. }

Leetcode 426.

Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.

You have to realize that you need to flatten child nodes and then return both head and tail up to the caller. The caller than rearranges themselves in the right way.

Algorithm:

  1. FUNC flatten(node) return: Head and Tail of flattened list
  2. if node is null
  3. return null head and null tail
  4.  
  5. (Left Head, Left Tail) flatten(Left child)
  6. (Right Head, Right Tail) flatten(Right child)
  7.  
  8. If Left Tail not null, Connect Left Tail with node
  9. If Reft Head not null, Connect Right Head with node
  10.  
  11. HeadTail out;
  12.  
  13. //Set the proper Head
  14. out.head = (Left Head != NULL) ? Left Head : node;
  15.  
  16. //Set the proper Tail
  17. out.tail = (Right Tail != NULL) ? Right Tail : node;
  18.  
  19. FUNC caller(node) return: node
  20. if node is null return
  21. HeadTail = flatten(node)
  22. Head left = tail
  23. tail right = head
  24. return head
  25. return out

Code:

  1. // Our return object containing a head and tail
  2. class HeadTail{
  3. public:
  4. Node* head;
  5. Node* tail;
  6.  
  7. HeadTail(){}
  8.  
  9. HeadTail(Node* _head, Node* _tail) : head(_head), tail(_tail) {}
  10. };
  11.  
  12. class Solution {
  13. public:
  14. HeadTail flatten(Node* node){
  15. if(node == NULL){
  16. return HeadTail(NULL, NULL);
  17. }
  18.  
  19. HeadTail leftHT = flatten(node->left);
  20. HeadTail rightHT = flatten(node->right);
  21.  
  22. if(leftHT.tail != NULL){
  23. leftHT.tail->right = node;
  24. node->left = leftHT.tail;
  25. }
  26. if(rightHT.head != NULL){
  27. rightHT.head->left = node;
  28. node->right = rightHT.head;
  29. }
  30.  
  31. HeadTail out;
  32. out.head = (leftHT.head != NULL) ? leftHT.head : node;
  33. out.tail = (rightHT.tail != NULL) ? rightHT.tail : node;
  34. return out;
  35. }
  36.  
  37. Node* treeToDoublyList(Node* root) {
  38. if(root == NULL){
  39. return NULL;
  40. }
  41. HeadTail out = flatten(root);
  42. out.head->left = out.tail;
  43. out.tail->right = out.head;
  44. return out.head;
  45. }
  46. };

Leetcode 173.

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST.

Struggling hard with this one. First I tried a simple stack, that I would build on initializing that would go down to the current smallest element. This breaks down when having to explore right children of a parent node.

Then I thought about two stacks, but that's ridiculous and does not solve the problem.

Then I tried to think of some kind of process engine, that would change logic based on the step. This was not good.

Then I figured out a way with a stack that tracked a “seen” variable for each node! Which was unnecessary! I was hung up on what to do when encountering the parent node again.

  1. class BSTIterator {
  2. public:
  3.  
  4. enum Status{ UNSEEN, SEEN};
  5.  
  6. stack< pair<TreeNode*, Status> > stack;
  7.  
  8. // look for minimum.
  9. void buildMin(TreeNode* node)
  10. {
  11. if(node == NULL) return;
  12.  
  13. stack.push( make_pair(node, UNSEEN) );
  14.  
  15. if(node->left) { buildMin(node->left); }
  16. return;
  17. }
  18.  
  19. BSTIterator(TreeNode* root) {
  20. buildMin(root);
  21. }
  22.  
  23. /** @return the next smallest number */
  24. int next() {
  25.  
  26. // we have not seen this node
  27. if(stack.top().second == UNSEEN)
  28. {
  29. stack.top().second = SEEN;
  30. int out = stack.top().first->val;
  31. buildMin( stack.top().first->right );
  32. return out;
  33. }
  34. // node is seen
  35. stack.pop();
  36. return next();
  37. }
  38.  
  39. /** @return whether we have a next smallest number */
  40. bool hasNext() {
  41. while(stack.size() > 0 && stack.top().second == SEEN)
  42. {
  43. stack.pop();
  44. }
  45. return (stack.size() > 0) ? true: false;
  46. }
  47. };

Algorithm:

  1. FUNC: BUILD MIN ( Take in a node )
  2. if node NULL return
  3. Add node to stack
  4. if node has left child-> BUILDMIN(LEFT CHILD)
  5.  
  6. FUNC: NEXT()
  7. Node OUT = stack top
  8. pop stack top
  9. BUILD MIN( OUT->right child)
  10. return OUT's val
  11.  
  12. FUNC: HAS NEXT()
  13. return true if size of stack greater then 0, false otherwise

Code:

  1. class BSTIterator {
  2. public:
  3. stack<TreeNode*> stack;
  4.  
  5. // look for minimum.
  6. void buildMin(TreeNode* node)
  7. {
  8. if(node == NULL) return;
  9. stack.push(node);
  10. if(node->left) { buildMin(node->left); }
  11. }
  12.  
  13. BSTIterator(TreeNode* root) {
  14. buildMin(root);
  15. }
  16.  
  17. /** @return the next smallest number */
  18. int next() {
  19. TreeNode* out = stack.top(); stack.pop();
  20. buildMin(out->right);
  21. return out->val;
  22. }
  23.  
  24. /** @return whether we have a next smallest number */
  25. bool hasNext() {
  26. return (stack.size() > 0) ? true: false;
  27. }
  28. };

Leetcode 199.

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Do a level order traversal, and push the right most element in an output array

Algorithm:

  1. create a queue
  2. push first node into the the queue
  3. while queue isn't empty
  4. level size = queue size
  5. take the back of the queue and add it output
  6. for( i to level size)
  7. cur = pop front of queue
  8. if cur has children, put them in the back of the queue

Code:

  1. vector<int> rightSideView(TreeNode* root) {
  2. // output result
  3. vector<int> out;
  4.  
  5. if(root == NULL) return out;
  6.  
  7. // level queue
  8. queue<TreeNode*> levelq;
  9.  
  10. // push in first element, which is the root
  11. levelq.push(root);
  12.  
  13. while(!levelq.empty())
  14. {
  15. // add the right most element to the output;
  16. out.push_back( levelq.back()->val );
  17. // we need to count how many elements are in this level, so we can get the right
  18. // most element
  19. int level_size = levelq.size();
  20.  
  21. // pop off all the elements from this level
  22. while(level_size-- > 0)
  23. {
  24. // set cur to be the front of the queue and pop it
  25. TreeNode* cur = levelq.front(); levelq.pop();
  26. // if we have children, starting with the left, add them to the queue
  27. if(cur->left) levelq.push(cur->left);
  28. if(cur->right) levelq.push(cur->right);
  29. }
  30. }
  31. return out;
  32. }

DFS

We would explore the graph in a depth first way by keep track of levels. We could keep a map of results, so that if we end up at that level, we overwrite whatever is in that result map.

I used a map because I was worried that we would end up touching nodes we thought were at the right most and valid for that level. That's just not true, and silly on my part, because I had the firm assumption (and correct) that the left node was also the first most level at that level.

So all we have to do is start from the right and track levels!!! We can track levels in a really cutesy way too.

Algorithm:

  1. Explore function that takes in node, level, ref to output array
  2. if node is null return
  3. if level equal out size
  4. push in node val to out
  5. if right child
  6. explore right child, level + 1, output
  7. if left child
  8. explore left child, level + 1, output
  9. return

Code:

  1. void explore(TreeNode* node, int level, vector<int> &out)
  2. {
  3. if (node == NULL) return;
  4.  
  5. // Right most node we ever touch at this level!
  6. if (level == out.size())
  7. out.push_back(node->val);
  8.  
  9. // Check the children
  10. if(node->right)
  11. explore(node->right, level + 1, out);
  12. if(node->left)
  13. explore(node->left, level + 1, out);
  14.  
  15. return;
  16. }
  17.  
  18. vector<int> rightSideView(TreeNode* root) {
  19. vector<int> out;
  20. explore(root, 0, out);
  21. return out;
  22. }

Leetcode 236

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

This was a fun problem and I solved it in a cutesy way with two lists to keep a trace of the lineage to target node.

Algorithm:

  1. Create two traces lists one for p and for q
  2. explore p and build a left trace list
  3. explore q and build a right trace list
  4. while the two front elements of the traces equal each other
  5. set out to the front of one element
  6. pop the first element of both traces off
  7.  
  8. // FUNCTION
  9. Explore starting from a node with a target and reference of the trace list
  10. If node is null, return false
  11. Push out node on the trace list
  12. if node == target, that means we found it!
  13. return true
  14. Explore the left, and the right child. If either returns true
  15. return true
  16. We haven't found the target from this root, pop our element off the trace list
  17. return false

Code:

  1. bool explore(TreeNode* node, TreeNode* target, list<TreeNode*>& trace)
  2. {
  3. if(node == NULL)
  4. return false;
  5.  
  6. // push ourselves on the trace
  7. trace.push_back(node);
  8.  
  9. if(node == target)
  10. return true;
  11.  
  12. if( explore(node->left, target, trace) || explore(node->right, target, trace) )
  13. {
  14. return true;
  15. }
  16.  
  17. // not found in either child, get rid of our entry from the trace
  18. trace.pop_back();
  19. return false;
  20. }
  21.  
  22. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  23.  
  24. list<TreeNode*> p_trace, q_trace;
  25.  
  26. explore(root, p, p_trace);
  27. explore(root, q, q_trace);
  28.  
  29. // init out
  30. TreeNode* out;
  31.  
  32. while(p_trace.front() == q_trace.front())
  33. {
  34. out = p_trace.front();
  35. p_trace.pop_front();
  36. q_trace.pop_front();
  37. }
  38. return out;
  39. }

Leetcode 257

Given a binary tree, return all root-to-leaf paths.

I fell in a little pitfall with this problem! We have to travel all the way down to the leaf, building a string as we go down, and then triggering an append to an output array when a node has no children.

Algorithm:

  1. Explore with a node, a string and a reference to output array
  2. If the node is null, JUST RETURN. (we can be in a node with only one child!)
  3. if our string is NOT empty, add the "->"
  4. add the number of our node to the string
  5. If we don't have any children
  6. add the string to the output array and RETURN
  7. Explore the left child
  8. Explore the right child

Code:

  1. void explore(TreeNode* node, string path, vector<string> &out)
  2. {
  3. // A null node by itself is NOT a leaf!
  4. if(node == NULL) { return; }
  5.  
  6. // Add the arrow if the string isn't empty
  7. if(path != "")
  8. path += "->";
  9. // Add our number to the string
  10. path += to_string(node->val);
  11.  
  12. // If the node doesn't have children, we have a leaf!
  13. if(node->left == NULL && node->right == NULL)
  14. {
  15. out.push_back(path);
  16. return;
  17. }
  18. // Explore the left and the right
  19. explore(node->left, path, out);
  20. explore(node->right, path, out);
  21. return;
  22. }

Leetcode 543.

Had a little hiccup understanding the definition, cause I dove right in thinking the root node added up the path. READ THE QUESTION. UNDERSTAND IT.

Go down to the null, and return 0, then add 1 to that as you bubble up. At each node, check the max path on the left, max path on the right, Check if your max is bigger than the output.

Algorithm:

  1. Explore node with out ref
  2. if node is null, return 0
  3. left path is explore left node's max path
  4. right path is explore right node's max path
  5.  
  6. out is max of left path and right path
  7.  
  8. return max of left path + 1, right path + 1

Code:

  1. int explore(TreeNode* node, int& out)
  2. {
  3. if(node == NULL) return 0;
  4.  
  5. int lp = explore(node->left, out);
  6. int rp = explore(node->right, out);
  7.  
  8. out = max(out, lp + rp);
  9.  
  10. return max(lp + 1, rp + 1);
  11. }
  12.  
  13. int diameterOfBinaryTree(TreeNode* root) {
  14. int out = 0;
  15. explore(root, out);
  16. return out;
  17. }

Leetcode 437 - Path Sum III

You're given a binary tree and need to find the number of paths along the tree that add up to a number.

Dima helped me out with an algorithm that keeps an array of sums. At every node, you add the value of the node to every element in that array, and also push back the value of the node itself. At each node you also iterate through the array and check to see if any values add to up the sum that is requested.

  1. int helper(TreeNode* node, int target, vector<int> sums)
  2. {
  3. if(node == NULL)
  4. return 0;
  5.  
  6. int out = 0;
  7.  
  8. // add current node value to all elemnts of sums
  9. // and also check if they are valid solutions
  10. for(auto& entry : sums)
  11. {
  12. entry += node->val;
  13. if(entry == target)
  14. out++;
  15. }
  16. // append this elements value to sums
  17. sums.push_back(node->val);
  18.  
  19. // check if node itself is a possible solution on its own.
  20. if(node->val == target)
  21. out++;
  22.  
  23. // return out and children solutions
  24. return out + helper(node->left, target, sums) +
  25. helper(node->right, target, sums);
  26. }
  27.  
  28. int pathSum(TreeNode* root, int sum) {
  29. vector<int> sums;
  30. return helper(root, sum, sums);
  31. }

Prefix Sum

There is another way to solve this problem with a hashmap based prefix sum. I don't understand how this works. Here is the code:

Also funny, found some poor guy on the internt who also thinks this is magic.

  1. class Solution {
  2. public:
  3.  
  4. int count = 0;
  5. int k;
  6. unordered_map<int,int> h;
  7.  
  8. void helper(TreeNode* node, int cur_sum)
  9. {
  10. if(node == NULL)
  11. return;
  12.  
  13. cur_sum += node->val;
  14.  
  15. if(cur_sum == k)
  16. count++;
  17.  
  18. if(h.count(cur_sum - k) > 0)
  19. count += h[cur_sum - k];
  20.  
  21. h[cur_sum]++;
  22.  
  23. helper(node->left, cur_sum);
  24. helper(node->right, cur_sum);
  25.  
  26. h[cur_sum]--;
  27. }
  28.  
  29. int pathSum(TreeNode* root, int sum)
  30. {
  31. k = sum;
  32. helper(root, 0);
  33. return count;
  34. }
  35. };

Leetcode 525

Find the longest contiguous subarray that contains equal number of zero's and ones.

I first tried using divide and conquer but that doesn't work. Divide and conquer breaks down the problem into 3 possible solution locations, left, right and crossing the middle. This appraoch fails this problem because the solution cannot be split up because the sub-solutions are not independant. You can have 8 one's on the left, which is an invalid solution.

So this is another pre-fix with hashmap problem. Man i really don't get these problems and don't think they'll be asked.

Leetcode 101

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

This can be solved in two ways, recursively in a depth first manner, and iteratively in a breath first manner.

Recursive DFS

Take in two nodes, which should be reflections of each other. Initially these will be first children left and right.

If they are null and equal, return true, great. We don't recurse past this node because there are no children.

If only one is NULL, then return false. Tree is not symmetric.

Then check the following:

  1. Values of both first and second node are equal
  2. Recurse with the outer children of the two nodes
  3. Recurse with the inner children of the two nodes

Return all three cases && together.

  1. class Solution{
  2. public:
  3.  
  4. bool isMirror(TreeNode* t1, TreeNode* t2)
  5. {
  6. if(t1 == NULL && t2 == NULL) return true;
  7. if(t1 == NULL || t2 == NULL) return false;
  8.  
  9. // now we have to check if the two nodes are mirrors
  10. // if their inner children are mirrors, or if theyre
  11. // outer children are mirrors
  12. return t1->val == t2->val &&
  13. isMirror(t1->right, t2->left) &&
  14. isMirror(t1->left, t2->right);
  15. }
  16.  
  17. bool isSymmetric(TreeNode* root)
  18. {
  19. if(root == NULL) return true;
  20. return isMirror(root->left, root->right);
  21. }
  22. };

Iterative BFS

Use a queue, push in the first two children.

Pop out 2 nodes at a time, and compare them. Push in the children nodes in symmetric pairs.

  1. class Solution {
  2. public:
  3. bool isSymmetric(TreeNode* root) {
  4.  
  5. if(root == NULL) return true;
  6.  
  7. queue<TreeNode*> q;
  8. q.push(root->left);
  9. q.push(root->right);
  10. while(q.size() > 0)
  11. {
  12. TreeNode* t2 = q.front(); q.pop();
  13. TreeNode* t1 = q.front(); q.pop();
  14.  
  15. if(t1 == NULL && t2 == NULL) continue;
  16. if(t1 == NULL || t2 == NULL) return false;
  17. if(t1->val != t2->val) return false;
  18.  
  19. // outer pair
  20. q.push(t1->left); q.push(t2->right);
  21. // inner pair
  22. q.push(t1->right); q.push(t2->left);
  23. }
  24. return true;
  25. }
  26. };

Leetcode 56.

Given a collection of intervals, merge all overlapping intervals.

Example 1:

  1. Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
  2. Output: [[1,6],[8,10],[15,18]]
  3. Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Algorithm:

  1. If input is less than 2 elements return
  2. Sort by starting interval
  3. Put first interval in out array
  4. Iterate i from 1 to input end
  5. min end = min(end of last interval in out, end of input[i]
  6. if start of last interval in out is LESS OR EQUAL to min end
  7. Overlap, set end of last interval to the max end of the two
  8. Else
  9. No overlap, push in input[i] to out
  10. Return out

Code:

  1. vector<vector<int>> merge(vector<vector<int>>& in) {
  2. // Take care of edge case
  3. if(in.size() < 2) return in;
  4. // Sort the intervals by start
  5. sort(in.begin(), in.end(), [] (vector<int> &a, vector<int> &b) {return a[0] < b[0];});
  6. // Build the output array
  7. vector<vector<int>> out;
  8. // Add first interval to our output
  9. out.push_back(in[0]);
  10. // Iterate from second element to finish
  11. for(int i = 1; i < in.size(); i++)
  12. {
  13. // The max start will always be the new interval, cause we sorted it
  14. int max_start = in[i][0];
  15. // Meat of the problem
  16. int min_end = min(out.back()[1], in[i][1]);
  17. if(max_start <= min_end)
  18. out.back()[1] = max(out.back()[1], in[i][1]);
  19. else
  20. out.push_back(in[i]);
  21. }
  22. return out;
  23. }

Leetcode 88.

You need to do a merge sort in place. One array is big enough to hold both of them. You work with 3 pointers.

One pointer at the end of the long array that will be the output, another pointer at the end of the valid data, and another pointer at the end of the other array.

You take the biggest element and put it in the end of the array and shift the pointers left.

At the end you might still have some shit left in the second array. If you do, just put em in the array.

Leetcode 215.

This was a nice and easy one. Idea is to keep a heap of the size that we require. In C++ we would just use a multiset to allow for duplicates. We iterate through the input array and insert elements into the set. If the set is bigger than k, we remove the smallest element from the set. We then return the smallest element of the set which will be the k'th largest element.

There are 2 different ways of solving this problem:

DFT recursively, BFT.

DFT Recursively

Depth First Traversal recursively with an unordered map of seen nodes and copies.

Algorithm:

  1. If node is NULL return NULL
  2. Add node and copy to map
  3. Explore Node with Map
  4. iterate over neighbors A
  5. if not in Map
  6. add copy of A to map.
  7. Explore A with Map
  8. Push back copy of A to copy of Node neighbors

Code:

  1. void explore(Node* node, unordered_map<Node*, Node*> &copy_map)
  2. {
  3. // iterate over neighbors of node
  4. for(auto& A : node->neighbors)
  5. {
  6. if(copy_map.find(A) == copy_map.end())
  7. {
  8. // if we have NOT seen this node yet
  9. copy_map[A] = new Node(A->val);
  10. explore(A, copy_map);
  11. }
  12. copy_map[node]->neighbors.push_back(copy_map[A]);
  13. }
  14. }
  15.  
  16. Node* cloneGraph(Node* node) {
  17. if(node == NULL) return NULL;
  18.  
  19. unordered_map<Node*, Node*> copy_map;
  20. copy_map[node] = new Node(node->val);
  21.  
  22. explore(node, copy_map);
  23.  
  24. return copy_map[node];
  25. }

BFT Iteratively

Breath First Traversal iteratively with a queue and an ordered map of seen nodes and copies.

Algorithm:

  1. If node is NULL return NULL
  2. Insert node, and a copy of that node (with just the value for now) in a map
  3. Push node in a queue
  4. While queue is not empty
  5. deque the front of the queue and call it N
  6. iterate over the neighbors of N, call each one A.
  7. if A is not in the map
  8. Insert A, and a copy into the map
  9. add the copy of A to the neighbor list of the copy of N.
  10. Return the copy of node.

Code:

  1. Node* cloneGraph(Node* node) {
  2. if(node == NULL) return NULL;
  3.  
  4. unordered_map<Node*, Node*> copy_map;
  5. queue<Node*> q;
  6.  
  7. // create entry in copy_map of node, copy of node
  8. copy_map[node] = new Node(node->val);
  9. q.push(node);
  10.  
  11. while(!q.empty())
  12. {
  13. Node* n = q.front(); q.pop();
  14. // iterate over adjacent nodes
  15. for(auto& a : n->neighbors)
  16. {
  17. // if we have not visted this node yet
  18. if(copy_map.find(a) == copy_map.end())
  19. {
  20. // make a copy and add it to our map
  21. copy_map[a] = new Node(a->val);
  22. // add node to our queue
  23. q.push(a);
  24. }
  25. // we add this newly copied neighbor to the copy of the node we are examining
  26. copy_map[n]->neighbors.push_back(copy_map[a]);
  27. }
  28. }
  29. return copy_map[node];
  30. }

Leetcode 200

Graph problem, we explore connected land parts and then mark them as seen. Then we go through the graph and check if we encounter any new unseen land areas. If we do, increment result counter and explore and mark seen :).

I spent a great deal of effort coding a system that will look at all neighboring elements along with diagonals. The question didn't ask this!!! Remember to read the question!!

I also had a lot of effort in trying to create an ordered map/set of pairs. You can't do that easily in C++, so I just modified the input the input grid.

Algorithm:

  1. Iterate over every element of the graph
  2. If the element is unseen land
  3. Increment result counter
  4. Explore unseen land
  5. Mark land as seen
  6. Explore all unseen connected land

Code:

  1. vector< vector<int> > landN(vector<vector<char>>& grid, int& i, int& j)
  2. {
  3. int max_i = grid.size() - 1;
  4. int max_j = grid[0].size() - 1;
  5.  
  6. vector<vector<int>> out;
  7. // top
  8. if(i - 1 >= 0 && grid[i-1][j] == '1')
  9. out.push_back({i-1, j});
  10. //left
  11. if(j - 1 >= 0 && grid[i][j-1] == '1')
  12. out.push_back({i, j-1 });
  13. //down
  14. if(j + 1 <= max_j && grid[i][j+1] == '1')
  15. out.push_back({i,j + 1});
  16. //right
  17. if(i + 1 <= max_i && grid[i+1][j] == '1')
  18. out.push_back({i+1, j});
  19.  
  20. return out;
  21. }
  22.  
  23. void explore(vector<vector<char>>& grid, int& i, int& j )
  24. {
  25. // assume we are on a land element
  26. grid[i][j] = 'X';
  27.  
  28. // get a list of neighbors that are land
  29. vector< vector<int> > neighbors = landN(grid, i, j);
  30. for(auto n : neighbors)
  31. {
  32. explore(grid, n[0], n[1]);
  33. }
  34. return;
  35. }
  36.  
  37. int numIslands(vector<vector<char>>& grid) {
  38.  
  39. int islands = 0;
  40. for(int i = 0; i < grid.size(); i++)
  41. {
  42. for(int j = 0; j < grid[0].size(); j++)
  43. {
  44. if( grid[i][j] == '1')
  45. {
  46. islands++;
  47. explore(grid, i, j);
  48. }
  49. }
  50. }
  51. return islands;
  52. }

Leetcode 785

I don't know you tell me bro.

I did a deep dive in this problem. To solve it, we have to start at a node, color it, and then check to see if any of its neighbors have the same color. Then iterate over the neighbor nodes, if they are uncolored, then color them a different color than their current node.

Algorithm:

  1. Create color map, key will be vertex index and value will be color or unseen
  2. color: -1 = unseen, 0 one color, 1 another color
  3. Iterate i from 0 to end of graph. Do this to take care of disconnected sub graphs
  4. if the vertex at i is unseen (-1)
  5. create a stack of ints
  6. push i in the stack
  7. color the vertex i 0
  8. while stack is not empty
  9. vertex cur will equal top element popped from stack
  10. // we are now in a colored node. we need to check its neighbors
  11. iterate n over neighbors of vertex cur
  12. if color of n == -1 meaning not colored/seen yet
  13. set color of n the opposite of color of cur
  14. suspend cur by pushig it to the stack
  15. push n to the stack
  16. break out of the iteration
  17. if color of n == color of cur
  18. return false cause this is not BIPARTE

Code:

  1. bool isBipartite(vector<vector<int>>& graph) {
  2.  
  3. unordered_map<int, int> color;
  4. // initialize color map to all -1
  5. for(int i = 0; i < graph.size(); i++)
  6. color[i] = -1;
  7.  
  8. // this for loop is to take in account disconnected vertices
  9. for(int start = 0; start < graph.size(); start++)
  10. {
  11. // if a vertex has not been colored. If it has, we've already done a
  12. // full search of its connected vertices. We do this for every
  13. // disconnected graph
  14.  
  15. if(color[start] == -1)
  16. {
  17. stack<int> s;
  18. s.push(start);
  19. // color the first vertex. We assume every vertex in the while loop is
  20. // colored
  21. color[start] = 0;
  22.  
  23. while(!s.empty())
  24. {
  25. // grab the top of the stack
  26. int cur = s.top(); s.pop();
  27.  
  28. // iterate over its children. We are looking for one un colored
  29. // vertex to dive deeper into.
  30. for(auto n : graph[cur])
  31. {
  32. if(color[n] == -1)
  33. {
  34. // we have to suspend our current vertex, we'll get back
  35. // to it later.
  36. s.push(cur);
  37. // lets push in our new node to search
  38. s.push(n);
  39. // this sets the color to the opposite of our vertex n
  40. // using the bitwise XOR operator
  41. color[n] = color[cur] ^ 1;
  42. // break out of this vertex's exploration. we want to
  43. // pursue this new deeper vertex.
  44. break;
  45. }
  46. else if(color[n] == color[cur])
  47. return false;
  48. }
  49. }
  50. }
  51. }
  52. return true;
  53. }

Leetcode 721

This is a really interesting graph problem, and theres a couple of parts to to it. The trick to understand is that bulk of the problems lies with accounts tying other accounts together. For example:

  1. Account 1: A B
  2. Account 2: C D
  3. Account 3: A C

A trick early in this problem was simplify the email strings, and the whole name crap, and boil it down to the root problem. Strings that if found in other accounts, need to be merged into one.

First is building the graph itself, in the form of an adjacency list. Next is to create a map of seen emails, with the key being the first node they were seen in. Then iterate over the accounts, and for each account, iterate over the emails. If the email address has been found already, add an adjacency entry connecting that node to the node the email address was found.

After this we'll have a nifty adjacency list that defines our graph, which is all we need to build our output list of accounts.

What we do is do Depth First Traversal on each node we find. Throughout that traversal, we keep adding all the emails we see into a set for that node, and also mark each node as seen as we explore it. That's it!

Algorithm:

  1. Build an array of sets of ints to serve as adjancency list
  2. Initialize the array to have empty set for every index in accounts
  3. Create a map called EMAP of key: email string and value: index of account first seen with it
  4. Iterate A over accounts
  5. iterate E for all emails of A
  6. if E is in EMAP
  7. create adjacency connections:
  8. A to EMAP[E] and EMAP[E] to A
  9. else add EMAP[E] = A
  10.  
  11. Build our output: create a vector of vectors of strings called OUT
  12. Create a SEEN set of ints
  13. iterate A over Accounts
  14. if A isn't in SEEN:
  15. create a vector of strings, and add in the name as the first element
  16. Pass this vector and node A into Explore! Explore will fill in the emails
  17. Return OUT!
  18.  
  19. SUBROUTINE:
  20. Explore DFS with params:
  21. accounts ref,
  22. adjacency list,
  23. seen set
  24. output string set ref
  25. node index
  26.  
  27. if the node is in the seen set, RETURN
  28. add the nodes emails to the emails output string set
  29. iterate over the neighbors
  30. explore them!

Code:

  1. // Depth first traversal of our graph, that builds a set of emails for that connected group
  2. void dfs(vector<vector<string>>& accounts, vector< set<int> > &adj,
  3. unordered_set<int> &seen, int node, set<string> &emails)
  4. {
  5. if(seen.find(node) != seen.end())
  6. return;
  7.  
  8. // node not seen, add its email to the emails set,
  9. bool first = true;
  10. for(auto& e : accounts[node]){
  11. if(first){ first = false; continue;}
  12. emails.insert(e);
  13. }
  14.  
  15. //mark it seen
  16. seen.insert(node);
  17.  
  18. //explore its neighbors
  19. for(auto& n : adj[node])
  20. dfs(accounts,adj,seen, n, emails);
  21.  
  22. return;
  23. }
  24.  
  25. vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
  26. // initialize empty adj list, set to avoid duplicate adjacencies
  27. vector< set<int> > adj(accounts.size(), set<int>());
  28.  
  29. unordered_map< string, int > emap;
  30.  
  31. // Build the adj list and emails map
  32. for(int id = 0; id < accounts.size(); id++)
  33. {
  34. // iterate over emails see if any are found
  35. for(int j = 1; j < accounts[id].size(); j++){
  36. if(emap.find(accounts[id][j]) != emap.end())
  37. {
  38. adj[emap[accounts[id][j]]].insert(id);
  39. adj[id].insert(emap[ accounts[id][j] ]);
  40. }
  41. else
  42. emap[accounts[id][j]] = id;
  43. }
  44. }
  45.  
  46. // build output
  47. vector<vector<string>> out;
  48. unordered_set<int> seen;
  49. for(int i = 0; i < accounts.size(); i++)
  50. {
  51. if(seen.find(i) != seen.end()){ continue; }
  52. // we haven't found this yet, so build it, starting with name
  53. out.push_back( {accounts[i][0]} );
  54. set<string> emails;
  55. dfs(accounts, adj, seen, i, emails);
  56. // iterate over emails set and add them to out
  57. for(auto& e : emails)
  58. {
  59. out.back().push_back(e);
  60. }
  61. }
  62. return out;
  63. }

To give you some perspective, this was my first crack at this algo:

Did a vector erase first but that wasn't ideal. I then learned how to do it with a two pointer approach. First pointer is a “last valid” location and second pointer sweeps through array. As it sweeps and find good ones, it swaps them with the valid. Valid then becomes my new array size.

Really interesting one cause theres dupes and rotations. Idea is to split the array and based on its bounds, you have 3 possible situations:

  • You have a normal sorted list cause left bound smaller than right bound. Do a normal bin search
  • Left bound is == to right bound, do a linear search
  • You have a pivot somewhere. You check to see if the left array is sorted right. if it is, check to see if your target is in it. If it is, search in it. If it isn't in it, it's gotta be on the other side! Remove duplicates from a sorted list

Leetcode 23

Very nice little problem. Many ways to solve but here's the nice optimized way. We have list of nodes and we need to keep track of the minimum one. We make use of an ordered container to do this. This container needs to keep our list of nodes ordered by the value of the container and also store a handle to that node.

Algorithm:

  1. Create a dummyhead and a pointer last that points to it
  2. Create a multimap with key (value of node) and value (pointer to node)
  3. Iterate over input lists and insert every ListNode and value into the map
  4. only add non null elements
  5. While multimap has at least 2 elements
  6. pop off the smallest node from the mulitmap = cur
  7. set last->next = to cur
  8. set last = last next
  9. if cur next isn't null
  10. add it to the multimap
  11. if multimap is only one element
  12. make last next point to it
  13. break
  14. return dummyhead next

Code:

  1. ListNode* mergeKLists(vector<ListNode*>& lists) {
  2.  
  3. if(lists.size() == 0 ) return NULL;
  4.  
  5. ListNode dh, *last;
  6. last = &dh;
  7.  
  8. // create the map of first elements
  9. multimap<int, ListNode*> mmap;
  10. for(auto& ln : lists)
  11. {
  12. if(ln != NULL)
  13. mmap.insert(make_pair(ln->val,ln));
  14. }
  15.  
  16. while(mmap.size() > 1)
  17. {
  18. // set a current node to the minimum node and remove it
  19. ListNode* cur = mmap.begin()->second;
  20. mmap.erase(mmap.begin());
  21.  
  22. // set our last pointer to point to this min element
  23. last->next = cur;
  24. last = last->next;
  25.  
  26. // if there are still nodes in this list, put the next one in the map
  27. if(cur->next != NULL)
  28. {
  29. mmap.insert(make_pair(cur->next->val, cur->next));
  30. }
  31. }
  32. //mmap is going to have one element left
  33. if(mmap.size() == 1)
  34. last->next = mmap.begin()->second;
  35.  
  36. return dh.next;
  37. }

The all time favorite :)

We make use of the splice function in its single element version to move an element by its iterator to the top of the list.

void splice (iterator position, list& x, iterator i)

Code:

  1. class LRUCache {
  2. public:
  3. list< pair<int, int> > lru;
  4. unordered_map< int, list< pair<int,int> >::iterator > table;
  5. int cap;
  6.  
  7. LRUCache(int capacity) {
  8. cap = capacity;
  9. }
  10.  
  11. int get(int key) {
  12. // we search the table for the element
  13. auto search = table.find(key);
  14. // if not found, return -1
  15. if(search == table.end()) { return -1; }
  16. // if found, move up the lru node
  17. lru.splice(lru.begin(), lru, search->second);
  18. return search->second->second;
  19. }
  20.  
  21. void put(int key, int value) {
  22. // we search the table for the element
  23. auto search = table.find(key);
  24.  
  25. // if found, move lru and update value
  26. if(search != table.end()) {
  27. lru.splice(lru.begin(), lru, search->second);
  28. lru.front().second = value;
  29. return;
  30. }
  31.  
  32. // if we don't find it, need a newone
  33. lru.push_front(make_pair(key, value));
  34. table[key] = lru.begin();
  35. // check size
  36. if(lru.size() > cap)
  37. {
  38. table.erase(lru.back().first);
  39. lru.pop_back();
  40. }
  41. return;
  42. }
  43. };
  • algorithm_problems.txt
  • Last modified: 2020/09/14 19:45
  • (external edit)