Level Order Traversal

Problem

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its level order traversal as:

1
2
3
4
5
[
  [3],
  [9,20],
  [15,7]
]

Accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    vector<vector<int>> nodes;
    void preorder(TreeNode* root, int level) {
        if (root == nullptr) return;
        if (level >= nodes.size()) {
            // create new level
            vector<int> v = {root->val};
            nodes.push_back(v);
        } else {
            nodes[level].push_back(root->val);
        }
        preorder(root->left, level+1);
        preorder(root->right, level+1);

    }
public:

    vector<vector<int>> levelOrder(TreeNode* root) {
        preorder(root, 0);
        return nodes;
    }
};

Sum Closest To Given Number 🚧

Given a 3 x 3 matrix, find if there exists a sum of numbers from each row that adds up to a given number such as 0.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
[
  [1, 0 , 3],
  [0, 5, 0],
  [1, 1, 0]
]
True because 0 + 0 + 0

[
  [1, -3 , 3],
  [3, 8, 0],
  [1, 1, 0]
]
True because -3 + 3 + 0


[
  [1, -33 , 3],
  [31, 8, 0],
  [1, 1, 0]
]
False

Analysis

  • brute force approach would mean that we have cubic time complexity, so that is not so good
  • there is no restriction on sorting, so we could sort the arrays, say in descending order
    • this gives us the largest numbers towards left and smallest towards right

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
[
  [1, 0 , 3],
  [0, 5, 0],
  [1, 1, 0]
]

After sorting we get
[
  [3, 1 , 0],
  [5, 0, 0],
  [1, 1, 0]
]


Let's say we have three indices i, j and k

i,j,k starts at 0

matrix[0][i] => 3
matrix[0][j] => 5
matrix[0][k] => 1

The approach I thought of and was recomended was to try and find a O(n^2) alternative, since this is one of those problems that is not possoible to do in better time. The way we can do this is to recognize that we are looking for a sum of three numbers (one from each row) and that can be either 0 or less than 0 or more than 0. If we simply pick each element in derial order that degenerates into cubic complexity. But what if we sorted each row. Let’s take an example:

1
2
3
4
5
[
  [-3, 1 , 0],
  [5, 0, 0],
  [1, 1, 0]
]

Similar

Leetcode seems to have a similar problem here

Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
      vector<vector<int>> res;
      if (nums.size() < 3) return res;
      sort(nums.begin(), nums.end(), [](int a, int b) { return a < b;});
      for (int i = 0; i < nums.size() - 2; i++) {
        int j = i + 1;
        int k = nums.size() - 1;
        while (j < k) {
          int sum = nums[i]+nums[j]+nums[k];
          if (sum == 0) {
            res.push_back({nums[i], nums[j], nums[k]});
          }
          if (nums[i]+nums[j+1]+nums[k] > sum) {
            k = k - 1;
          } else {
            j = j + 1;
          }
        }
        //if (nums[i+1] == nums[i])
      }
      return res;
    }
};

This fails the test case because we are allowing duplicates when we shouldn’t.

1
2
3
4

Input: [0,0,0,0]
Output: [[0,0,0],[0,0,0],[0,0,0]]
Expected: [[0,0,0]]

Second ATtempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
      vector<vector<int>> res;
      if (nums.size() < 3) return res;
      sort(nums.begin(), nums.end(), [](int a, int b) { return a < b;});
      for (int i = 0; i < nums.size() - 2; i++) {
        // skip duplicates of nums[i]
        if (i > 0 && nums[i] == nums[i-1]) { continue; }
        int j = i + 1;
        int k = nums.size() - 1;
        while (j < k) {
          int sum = nums[i]+nums[j]+nums[k];
          if (sum == 0) {
            res.push_back({nums[i], nums[j], nums[k]});
            // skip all duplicates for nums[j] and nums[k]
            while (j < k && nums[k-1] == nums[k]) k--;
            while (j < k && nums[j+1] == nums[j]) j++;

            j++;
            k--;
          }
          if (nums[i]+nums[j+1]+nums[k] > sum) {

            k = k - 1;

          } else {
            j = j + 1;
          }
        }
      }
      return res;
    }
};

This has a side effect and fails the following test case

1
2
3
Input: [-1,0,1,2,-1,-4]
Output: [[-1,-1,2]]
Expected: [[-1,-1,2],[-1,0,1]]

Third Attempt

The condition (nums[i]+nums[j+1]+nums[k] > sum should be in an else if

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
      vector<vector<int>> res;
      if (nums.size() < 3) return res;
      sort(nums.begin(), nums.end(), [](int a, int b) { return a < b;});
      for (int i = 0; i < nums.size() - 2; i++) {
        // skip duplicates of nums[i]
        if (i > 0 && nums[i] == nums[i-1]) { continue; }
        int j = i + 1;
        int k = nums.size() - 1;
        while (j < k) {
          int sum = nums[i]+nums[j]+nums[k];
          if (sum == 0) {
            res.push_back({nums[i], nums[j], nums[k]});
            // skip all duplicates for nums[j] and nums[k]
            while (j < k && nums[k-1] == nums[k]) k--;
            while (j < k && nums[j+1] == nums[j]) j++;
            j++;
            k--;
          } else if (nums[i]+nums[j+1]+nums[k] > sum) {
            k--;
          } else {
            j++;
          }
        }
      }
      return res;
    }
};

However, this fails the testcase

1
2
3
Input: [1,-1,-1,0]
Output: []
Expected: [[-1,0,1]]

Fourth

The issue is that since we are sorting in ascending order and we have the check to skip duplicates of nums[i], we end up skipping all the -1’s!
We need to modify that check a bit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
      vector<vector<int>> res;
      if (nums.size() < 3) return res;
      sort(nums.begin(), nums.end(), [](int a, int b) { return a < b;});
      for (int i = 0; i < nums.size() - 2; i++) {
        // skip duplicates of nums[i]
        if (i+1 < nums.size() && nums[i] == nums[i+1]) { continue; }
        int j = i + 1;
        int k = nums.size() - 1;
        while (j < k) {
          int sum = nums[i]+nums[j]+nums[k];
          if (sum == 0) {
            res.push_back({nums[i], nums[j], nums[k]});
            // skip all duplicates for nums[j] and nums[k]
            while (j < k && nums[k-1] == nums[k]) k--;
            while (j < k && nums[j+1] == nums[j]) j++;
            j++;
            k--;
          } else if (nums[i]+nums[j+1]+nums[k] > sum) {
            k--;
          } else {
            j++;
          }
        }
      }
      return res;
    }
};

But this fails

1
2
3
4

Input: [-1,0,1,2,-1,-4]
Output: [[-1,0,1]]
Expected: [[-1,-1,2],[-1,0,1]]

Ah this brings us back to the previous failure.

I think I misunderstood. The only duplicates we should skips for nums[i] are 0’s?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
      vector<vector<int>> res;
      if (nums.size() < 3) return res;
      sort(nums.begin(), nums.end(), [](int a, int b) { return a < b;});
      for (int i = 0; i < nums.size() - 2; i++) {
        // skip duplicates of nums[i] if 0
        if (i+1 < nums.size() && nums[i] == 0 && nums[i+1] == 0) { continue; }
        int j = i + 1;
        int k = nums.size() - 1;
        while (j < k) {
          int sum = nums[i]+nums[j]+nums[k];
          if (sum == 0) {
            res.push_back({nums[i], nums[j], nums[k]});
            // skip all duplicates for nums[j] and nums[k]
            while (j < k && nums[k-1] == nums[k]) k--;
            while (j < k && nums[j+1] == nums[j]) j++;
            j++;
            k--;
          } else if (nums[i]+nums[j+1]+nums[k] > sum) {
            k--;
          } else {
            j++;
          }
        }
      }
      return res;
    }
};

Revising core logic

The main comparison logic is somewhat flawed. We need to check if sum is equal to 0, greater than 0 or less than 0. The reason fos this is that

Accepted Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
      vector<vector<int>> res;
      if (nums.size() < 3) return res;
      sort(nums.begin(), nums.end());
      for (int i = 0; i < nums.size() - 2; i++) {
        // skip duplicates of nums[i]
        if (i > 0  && nums[i-1] == nums[i]) { continue; }
        int j = i + 1;
        int k = nums.size() - 1;
        while (j < k) {
          int sum = nums[i]+nums[j]+nums[k];
          if (sum == 0) {
            res.push_back({nums[i], nums[j], nums[k]});
            // skip all duplicates for nums[j] and nums[k]
            while (j < k && nums[k-1] == nums[k]) k--;
            while (j < k && nums[j+1] == nums[j]) j++;
            j++;
            k--;
          } else if (sum > 0) {
            k--;
          } else {
            j++;
          }
        }
      }
      return res;
    }
};

Leetcode similar problem

C++ refresher

Inheritance

Strings

  • substr()

Regex

Exceptions

1
throw std::invalid_argument("can't resolve ifindex for main intf");

C++11 features

Lambda functions

https://stackoverflow.com/questions/7627098/what-is-a-lambda-expression-in-c11

C++14 features

auto&& vs auto&

emplace_back() vs push_back

emplace_back:
I am being constructed.

push_back:
I am being constructed.
I am being moved.

Library

Priority queue

std::distance()

Computes distance between iterators

1
std::distance(words_begin, words_end)

unordered_set vs set

is_sorted_until()

Returns an iterator to the first element in the range [first,last) which does not follow an ascending order.

is_sorted()

Returns true if the range [first,last) is sorted into ascending order.

vector vs. bitset

Concurrency

Resources

Super Washing Machines 🚧

Problem

You have n super washing machines on a line. Initially, each washing machine has some dresses or is empty.

For each move, you could choose any m (1 ≤ m ≤ n) washing machines, and pass one dress of each washing machine to one of its adjacent washing machines at the same time .

Given an integer array representing the number of dresses in each washing machine from left to right on the line, you should find the minimum number of moves to make all the washing machines have the same number of dresses. If it is not possible to do it, return -1.

Example1

Input: [1,0,5]

Output: 3

Explanation:

1
2
3
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3
3rd move:    2     1 <-- 3    =>    2     2     2

Example2

Input: [0,3,0]

Output: 2

Explanation:

1
2
1st move:    0 <-- 3     0    =>    1     2     0
2nd move:    1     2 --> 0    =>    1     1     1

Example3

Input: [0,2,0]

Output: -1

Explanation:
It’s impossible to make all the three washing machines have the same number of dresses.

Note:

The range of n is [1, 10000].
The range of dresses number in a super washing machine is [0, 1e5].

IPO 🚧

Problem

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given several projects. For each project i, it has a pure profit Pi and a minimum capital of Ci is needed to start the corresponding project. Initially, you have W capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

To sum up, pick a list of at most k distinct projects from given projects to maximize your final capital, and output your final maximized capital.

Example 1:

Input: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].

Output: 4

Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

Note:

You may assume all numbers in the input are non-negative integers.
The length of Profits array and Capital array will not exceed 50,000.
The answer is guaranteed to fit in a 32-bit signed integer.

Analysis

We would like to maximize the profit of each investment at each step to get the best overall profit. This suggests a greedy approach.

First Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
      int len = Profits.size();
      unordered_set<int> selected;
      for (int i = 0; i < k; i++) {
        // pair of project index and corresponding profit
        pair<int, int> best = make_pair(0,0);
        for (int j = 0; j < len; j++) {
          // if available capital is enough to pick project and project not picked already
          if (W >= Capital[j]) {
            if (selected.find(j) == selected.end()) {
              if (best.second < Profits[j]) {
                best = make_pair(j, Profits[j]);
              }
            }
          }
        }
        selected.insert(best.first);
        W += Profits[best.first];
      }
      return W;
    }
};

We need to ensure we check if best,first

Second Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
      int len = Profits.size();
      unordered_set<int> selected;
      for (int i = 0; i < k; i++) {
        // pair of project index and corresponding profit
        pair<int, int> best = make_pair(-1,-1);
        for (int j = 0; j < len; j++) {
          // if available capital is enough to pick project and project not picked already
          if (W >= Capital[j]) {
            if (selected.find(j) == selected.end()) {
              if (best.second < Profits[j]) {
                best = make_pair(j, Profits[j]);
              }
            }
          }
        }
        if (best.first >= 0) {
          selected.insert(best.first);
          W += Profits[best.first];
        }
      }
      return W;
    }
};

Time limited exceeded on this solution. ⏲

How can we optimize this?

##

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
  struct elem_t {
    int p; //profit
    int c; //capital
  };
public:
    int findMaximizedCapital(int k, int W, vector<int>& Profits,
      vector<int>& Capital) {
      int len = Profits.size();
      vector<elem_t> v(len);

      for (int i = 0; i < len; i++) {
        v[i] = {Profits[i], Capital[i]};
      }
      sort(v.begin(), v.end(),
      [](const elem_t& a, const elem_t& b) {
        return a.p > b.p;
      });
      for (int i = 0; i < k; i++) {
        auto it = v.begin();
        auto selected = it;
        for (; it != v.end(); it++) {
          if ((*it).c <= W) {
            selected = it;
            break;
          }
        }
        W += (*selected).p;
        v.erase(selected);
      }
      return W;
    }
};

Accepted non-optimal solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>

class Solution {
  struct elem_t {
    int p; //profit
    int c; //capital
  };
public:
    int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
      int len = Profits.size();
      vector<elem_t> v(len);

      for (int i = 0; i < len; i++) {
        v[i] = {Profits[i], Capital[i]};
      }
      sort(v.begin(), v.end(),
      [](const elem_t& a, const elem_t& b) {
        return a.p > b.p;
      });
      //cout << "Hello\n";
      for (int i = 0; i < k; i++) {
        vector<elem_t>::iterator it = v.begin();
        vector<elem_t>::iterator selected = v.end();
        for (; it != v.end(); it++) {
          if ((*it).c <= W) {
            //cout << "Got cost " << (*it).c << endl;
            selected = it;
            break;
          }
        }

        if (selected != v.end()) {
          //cout << "got " << (*selected).p << endl;
          W += (*selected).p;
          v.erase(selected);
        }
      }
      return W;
    }
};

The inefficiency is a result of us using erase() as seen here

“Because vectors use an array as their underlying storage, erasing elements in positions other
than the vector end causes the container to relocate all the elements after the segment
erased to their new positions. This is generally an inefficient operation compared to the one
performed for the same operation by other kinds of sequence containers (such as list or
forward_list).”

I was afraid of that! Guess checking documentation is a good idea. 😖

Let’s try to use a set to track what projects we have already selected. We can track via addresses of array elements.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


class Solution {
  struct elem_t {
    int id;
    int p; //profit
    int c; //capital
    //bool operator < (const elem_t &other) const { return p < other.p; }
  };
public:
    int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
      int len = Profits.size();
      vector<elem_t> v(len);
      unordered_set<int> picked;
      for (int i = 0; i < len; i++) {
        v[i] = {i, Profits[i], Capital[i]};
      }
      sort(v.begin(), v.end(),
      [](const elem_t& a, const elem_t& b) {
        return a.p > b.p;
      });
      for (int i = 0; i < k; i++) {
        bool selected = false;
        int j = 0;
        for (; j < v.size(); j++) {
          if ((v[j].c <= W) && (picked.find(j) == picked.end())) {
            selected = true;
            break;
          }
        }

        if (selected) {
          cout << "got " << v[j].p << endl;
          W += v[j].p;
          picked.insert(j);
        }
      }
      return W;
    }
};

Um….this one times out! 😰
So, using the set is not as helpful as I thought.

System Design Notes

How to Approach

  1. Understanding the user requirements
  2. Coming up with a high level design
  3. Scaling the design

Notes from harvard scalability lecture

  • Vertical scaling means adding more RAM/CPU etc.
    • this will have physical limits and might blow your budget
  • Horizontal scaling means we can use cheaper less capable hardware, but more of them

Components

Load balancer

Spread out requests across several servers, each of which maintains a replica of our application server.

DNS round robin

Each DNS request can be used to send a different IP address. So each new request will go the next available sever. Can use something like BIND(Berkely Internet Name Daemon). Google uses something like this?

Limitations
  • Does not take into account load of each server
  • DNS responses will likely be cached on client, so a high traffic client will likely keep hitting the same server with every request, so in that case this technique will not help us
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
                     ________________
                    |                |
                    |     CLIENT     |
                    |  WEB BROWSER   |
                    |________________|
                            ||
                            ||
                     _______\/_______
                    |                |
                    |   DNS SERVER   |
                    |________________|
                            ||
                            ||
                    _______/  \_______
                   /                  \
                  /                    \
 ____________________                ____________________
|                    |              |                    |
|   SAN FRANCISCO    |              |   SAN FRANCISCO    |
|____________________|              |____________________|
|   ______________   |              |   ______________   |
|  |              |  |              |  |              |  |
|  |  WEB SERVER  |  |              |  |  WEB SERVER  |  |
|  | LOAD BALANCE |  |              |  | LOAD BALANCE |  |
|  |     PROXY    |  |              |  |     PROXY    |  |
|  |_____    _____|  |              |  |_____    _____|  |
|________|  |________|              |________|  |________|
          ||      __                  __      ||
          ||<=====||==================||=====>||
          \/      \/                  \/      \/
 ____________________                ____________________
|                    |              |                    |
|    SAN FRANCISCO   |              |      NEW YORK      |
|____________________|              |____________________|
|   ______________   |              |   ______________   |
|  |              |  |              |  |              |  |
|  |  APP SERVER  |  |              |  |  APP SERVER  |  |
|  |______  ______|  |              |  |______  ______|  |
|   ______||______   |              |   ______||______   |
|  |              |  |              |  |              |  |
|  |   DATABASE   |<==================>|   DATABASE   |  |
|  |______________|  |              |  |______________|  |
|____________________|              |____________________|

Reference

  1. HTTP(S) load balancing

Reference
More about HTTP Headers
Load balancing concepts

Reverse proxy

Reference

Message Brokers

Reverse Proxies

Example: Design Pinterest

Users

Constraints

High level design

Real life examples

Aman many more good ones at QCON!

References

  1. System design primer
  2. Hired in Tech
  3. Reddit discussion
  4. Clean Architecture Book (requires subscription)
  5. System Design Interview for IT
  6. Building Software Systems At Google and Lessons Learned
  7. Building a garbage collector
  8. Software Design patterns
  9. The Guardian’s move to Postgres

Third Maximum Number

Problem

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2:

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int thirdMax(vector<int>& nums) {
      int m1 = INT_MIN, m2 = INT_MIN, m3 = INT_MIN;
      for (int e : nums) {
        if (e > m1) {
          int tmp = m1;
          m1 = e;
          int tmp2 = m2;
          m2 = tmp;
          m3 = tmp2;
        } else if (e > m2) {
          int tmp = m2;
          m2 = e;
          m3 = tmp;
        } else if (e > m3) {
          m3 = e;
        }
      }

      // we should only return m3 if m3 was updated
      if (m3 > INT_MIN) {
        return m3;
      } else if (m2 > INT_MIN) {
        return m2;
      }

      return m1;
    }
};

Oops! Read the question carefully.

If it does not exist, return the maximum number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int thirdMax(vector<int>& nums) {
      int m1 = INT_MIN, m2 = INT_MIN, m3 = INT_MIN;
      for (int e : nums) {
        if (e > m1) {
          int tmp = m1;
          m1 = e;
          int tmp2 = m2;
          m2 = tmp;
          m3 = tmp2;
        } else if ((e > m2) && (e != m1)) {
          int tmp = m2;
          m2 = e;
          m3 = tmp;
        } else if ((e > m3) && (e != m2)) {
          m3 = e;
        }
      }

      // we should only return m3 if m3 was updated
      if (m3 > INT_MIN) {
        return m3;
      }
      return m1;
    }
};

There still a problem with this!

For [3,2,3]we see m1 = 3, m2 = 3,m3 = 2! 😱

We should have seen m1 = 3, m2 = 2,m3 = INT_MIN!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int thirdMax(vector<int>& nums) {
      int m1 = INT_MIN, m2 = INT_MIN, m3 = INT_MIN;
      for (int e : nums) {
        if (e > m1) {
          int tmp = m1;
          m1 = e;
          int tmp2 = m2;
          m2 = tmp;
          m3 = tmp2;
        } else if ((e > m2) && (e != m1)) {
          int tmp = m2;
          m2 = e;
          m3 = tmp;
        } else if ((e > m3) && (e != m2)) {
          m3 = e;
        }
      }

      //printf("%d %d %d\n", m1,m2,m3);
      // we should only return m3 if m3 was updated
      if (m3 > INT_MIN) {
        return m3;
      }
      return m1;
    }
};

Well this fails the testcase below.

1
2
3
Input: [1,2,2,5,3,5]
Output: 5
Expected: 2

The reason is because we need to ensure we check both m1 and m2!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int thirdMax(vector<int>& nums) {
      int m1 = INT_MIN, m2 = INT_MIN, m3 = INT_MIN;
      for (int e : nums) {
        if (e > m1) {
          int tmp = m1;
          m1 = e;
          int tmp2 = m2;
          m2 = tmp;
          m3 = tmp2;
        } else if ((e > m2) && (e != m1)) {
          int tmp = m2;
          m2 = e;
          m3 = tmp;
        } else if ((e > m3) && (e != m2) && (e != m1)) {
          m3 = e;
        }
      }

      // we should only return m3 if m3 was updated
      if (m3 > INT_MIN) {
        return m3;
      }
      return m1;
    }
};

Oh great. Now it fails here… 🤕
Ah you got me there!

1
2
3
4

Input: [1,2,-2147483648]
Output: 2
Expected: -2147483648

Well we have no way of knowing right now that the m3 was set to INT_MIN or was never updated.
If we has used a data structure like a set this might have been simpler and cleaner.

Well we can possibly use a flag to denote when all variables have been touched and when they have not. Then we also need to test >= as opposed to >.

Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int thirdMax(vector<int>& nums) {
      int m1 = INT_MIN, m2 = INT_MIN, m3 = INT_MIN;
      bool m3updated = false;
      for (int e : nums) {
        if (e >= m1) {
          int tmp = m1;
          m1 = e;
          int tmp2 = m2;
          m2 = tmp;
          m3 = tmp2;
        } else if ((e >= m2) && (e != m1)) {
          int tmp = m2;
          m2 = e;
          m3 = tmp;
        } else if ((e >= m3) && (e != m2) && (e != m1)) {
          m3 = e;
          m3updated = true;
        }
      }

      // we should only return m3 if m3 was updated
      if (m3 > INT_MIN) {
        return m3;
      }
      return m1;
    }
};

This is not a good approach.

Let’s go back and think about the requirement a bit more. Well the numbers are ints. So we cannot initialize to INT_MIN. 🤔

OK so what can we initialize this to?

How about LONG_MIN 💡!

Accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int thirdMax(vector<int>& nums) {
      long m1 = LONG_MIN, m2 = LONG_MIN, m3 = LONG_MIN;

      for (int e : nums) {
        if ((long)e > m1) {
          long tmp = m1;
          m1 = (long) e;
          long tmp2 = m2;
          m2 = tmp;
          m3 = tmp2;

        } else if (((long)e > m2) && ((long)e != m1)) {
          long tmp = m2;
          m2 = (long)e;
          m3 = tmp;

        } else if (((long)e > m3) && ((long)e != m2) && ((long)e != m1)) {
          m3 = e;

        }
      }

      // we should only return m3 if m3 was updated
      if (m3 > LONG_MIN) {
        return m3;
      }
      return m1;
    }
};

Nice 👍

But this has an obvious shortfall. What if the inputs are long? Well we can use long long?

But you see the limitations.

A set would be cleaner.

Remove sorted list duplicates II

Problem

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

Input: 1->1->1->2->3
Output: 2->3

Accepted on First Attempt 🍺

We try and use a pointer to a pointer. This allows handling special cases like updating head more generically although the approach may be off-putting to some.

Trying it on paper with a picture paid off. There wasn’t even a compilation error 🕺

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
  ListNode *skipDups(ListNode *p, int v) {
    while (p && p->val == v) { p = p->next;}
    return p;
  }
public:

  ListNode* deleteDuplicates(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode **p = &head;

    while ((*p) && ((*p)->next)) {
      if ((*p)->val == (*p)->next->val) {
        ListNode *n = skipDups(*p, (*p)->val);
        *p = n;
      } else {
        p = &((*p)->next);
      }
    }
    return head;
  }
};

There is a flaw in this solution though. Can you see it?

Where’s my memory? 🕵

That skipDups() function only skips but doesn’t release any memory!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  ListNode *skipDups(ListNode *p, int v) {
    while (p && p->val == v) {
      ListNode *tmp = p;
      p = p->next;
      free(tmp);
    }
    return p;
  }
public:

  ListNode* deleteDuplicates(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode **p = &head;

    while ((*p) && ((*p)->next)) {
      if ((*p)->val == (*p)->next->val) {
        ListNode *n = skipDups(*p, (*p)->val);
        *p = n;
      } else {
        p = &((*p)->next);
      }
    }
    return head;
  }
};