
# Coding Interview Tips

## Ofast

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();
```

## Overflow

See the [reverse integer](/blog/leetcode/reverse-integer/) problem for some basic overflow avoidance logic. And the [sqrt(x)](/blog/leetcode/sqrtx/) problem for more advanced overflow when you need to take into account the division and the denominator can be zero so that has to be treated separately.

## Underflow

`a.size() - b.size()` can underflow because they're both `size_t`, so you must do `(int)(a.size() - b.size())`.

## Freeing up Nodes

It's often forgotted, but when you remove a node from a linked list, you must free up its memory.
Use `delete`.

## Two's Complement

To calculate two's complement of a negative number in C++, do `(uint)num` -- it's as simple as that.


Summary of an awesome collection of interview gotchas.

Coding Interview Tips


# Add Binary Problem & Solution

Given two binary strings `a` and `b`, return their sum as a binary string.

See the [add binary problem on LeetCode](https://leetcode.com/problems/add-binary/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  string addBinary(string a, string b) {
    int longest = max(a.size(), b.size());
    string sum(longest, '0');

    int i = a.size() - 1;
    int j = b.size() - 1;
    int k = longest - 1;
    int carryover = 0;
    while (i >= 0 && j >= 0) {
      int ci = a[i--] == '1' ? 1 : 0;
      int cj = b[j--] == '1' ? 1 : 0;
      sum[k--] = (ci + cj + carryover) % 2 + '0';
      carryover = (ci + cj + carryover) / 2;
    }

    while (i >= 0) {
      int ci = a[i--] == '1' ? 1 : 0;
      sum[k--] = (ci + carryover) % 2 + '0';
      carryover = (ci + carryover) / 2;
    }

    while (j >= 0) {
      int cj = b[j--] == '1' ? 1 : 0;
      sum[k--] = (cj + carryover) % 2 + '0';
      carryover = (cj + carryover) / 2;
    }

    if (carryover > 0) {
      sum.insert(0, "1");
    }

    return sum;
  }
};
```


Solution for the add binary problem from LeetCode.

Add Binary

LeetCode Add Binary Solution


# Add Digits Problem & Solution

Given an integer `num`, repeatedly add all its digits until the result has only one digit, and return it.

See the [add digits problem on LeetCode](https://leetcode.com/problems/add-digits/).

## C++ Solution

The runtime complexity of this algorithm is $O(1)$.

```cpp
#pragma GCC optimize("Ofast")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int addDigits(int num) {
    if (num == 0) {
      return 0;
    }

    // https://en.wikipedia.org/wiki/Digital_root
    return 1 + (num - 1) % 9;
  }
};
```


Solution for the add digits problem from LeetCode.

Add Digits

LeetCode Add Digits Solution


# Array Partition I Problem & Solution

Given an integer array `nums` of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized.
Return the maximized sum.

See the [array partition i problem on LeetCode](https://leetcode.com/problems/array-partition-i/).

## C++ Solution

The runtime complexity of this algorithm is $O(n\log{}n)$.

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int arrayPairSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    
    int sum = 0;
    for (int i = 0; i < nums.size(); i += 2) {
      sum += min(nums[i], nums[i + 1]);
    }
    
    return sum;
  }
};
```


Solution for the array partition i problem from LeetCode.

Array Partition I

LeetCode Array Partition I Solution


# Balanced Binary Tree Problem & Solution

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as: a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

See the [balanced binary tree problem on LeetCode](https://leetcode.com/problems/balanced-binary-tree/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  bool isBalanced(TreeNode* root) {
    bool ok = true;

    isBalanced(root, ok);

    return ok;
  }

private:
  int isBalanced(TreeNode* root, bool& ok) {
    if (root == nullptr) {
      return 0;
    }

    int left = isBalanced(root->left, ok);
    int right = isBalanced(root->right, ok);

    if (abs(left - right) > 1) {
      ok = false;
    }

    return max(left, right) + 1;
  }
};
```


Solution for the balanced binary tree problem from LeetCode.

Balanced Binary Tree

LeetCode Balanced Binary Tree Solution


# Best Time to Buy and Sell Stock Problem & Solution

You are given an array `prices` where `prices[i]` is the price of a given stock on the `i`th day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction.
If you cannot achieve any profit, return 0.

See the [best time to buy and sell stock problem on LeetCode](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int maxProfit(vector<int>& prices) {
    int min_value = INT_MAX;
    int result = 0;

    for (int i = 0; i < prices.size(); ++i) {
      if (min_value > prices[i]) {
        min_value = prices[i];
      } else if (prices[i] - min_value > result) {
        result = prices[i] - min_value;
      }
    }

    return result;
  }
};
```


Solution for the best time to buy and sell stock problem from LeetCode.

Best Time to Buy and Sell Stock

LeetCode Best Time to Buy and Sell Stock Solution


# Binary Tree Inorder Traversal Problem & Solution

Given the `root` of a binary tree, return the inorder traversal of its nodes' values.

See the [binary tree inorder traversal problem on LeetCode](https://leetcode.com/problems/binary-tree-inorder-traversal/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  vector<int> inorderTraversal(TreeNode* root) {
    vector<int> path;

    inorderTraversal(root, path);

    return path;
  }

private:
  void inorderTraversal(TreeNode* node, vector<int>& path) {
    if (node == nullptr) {
      return;
    }

    inorderTraversal(node->left, path);
    path.push_back(node->val);
    inorderTraversal(node->right, path);
  }
};
```


Solution for the binary tree inorder traversal problem from LeetCode.

Binary Tree Inorder Traversal

LeetCode Binary Tree Inorder Traversal Solution


# Binary Tree Paths Problem & Solution

Given the `root` of a binary tree, return all root-to-leaf paths in any order.
A leaf is a node with no children.

See the [binary tree paths problem on LeetCode](https://leetcode.com/problems/binary-tree-paths/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> results;

    binaryTreePaths(root, "", results);

    return results;
  }

private:
  void binaryTreePaths(TreeNode* root, string result, vector<string>& results) {
    if (root == nullptr) {
      return;
    }

    if (root->left == nullptr && root->right == nullptr) {
      result += to_string(root->val);
      results.push_back(result);
    }

    string tmp = result + to_string(root->val) + "->";

    binaryTreePaths(root->left, tmp, results);
    binaryTreePaths(root->right, tmp, results);
  }
};
```


Solution for the binary tree paths problem from LeetCode.

Binary Tree Paths

LeetCode Binary Tree Paths Solution


# Binary Tree Postorder Traversal Problem & Solution

Given the `root` of a binary tree, return the postorder traversal of its nodes' values.

See the [binary tree postorder traversal problem on LeetCode](https://leetcode.com/problems/binary-tree-postorder-traversal/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  vector<int> postorderTraversal(TreeNode* root) {
    vector<int> traversal;
    
    postorderTraversal(root, traversal);
    
    return traversal;
  }

private:
  void postorderTraversal(TreeNode* node, vector<int>& traversal) {
    if (node == nullptr) {
      return;
    }

    postorderTraversal(node->left, traversal);
    postorderTraversal(node->right, traversal);
    traversal.push_back(node->val);
  }
};
```


Solution for the binary tree postorder traversal problem from LeetCode.

Binary Tree Postorder Traversal

LeetCode Binary Tree Postorder Traversal Solution


# Binary Tree Preorder Traversal Problem & Solution

Given the `root` of a binary tree, return the preorder traversal of its nodes' values.

See the [binary tree preorder traversal problem on LeetCode](https://leetcode.com/problems/binary-tree-preorder-traversal/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  vector<int> preorderTraversal(TreeNode* root) {
    vector<int> traversal;
    
    preorderTraversal(root, traversal);
    
    return traversal;
  }

private:
  void preorderTraversal(TreeNode* node, vector<int>& traversal) {
    if (node == nullptr) {
      return;
    }
    
    traversal.push_back(node->val);
    preorderTraversal(node->left, traversal);
    preorderTraversal(node->right, traversal);
  }
};
```


Solution for the binary tree preorder traversal problem from LeetCode.

Binary Tree Preorder Traversal

LeetCode Binary Tree Preorder Traversal Solution


# Climbing Stairs Problem & Solution

You are climbing a staircase.
It takes `n` steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

See the [climbing stairs problem on LeetCode](https://leetcode.com/problems/climbing-stairs/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int climbStairs(int n) {
    if (n <= 2) {
      return n;
    }

    int result = 0;
    int first = 1;
    int second = 2;

    for (int i = 3; i <= n; ++i) {
      int tmp = result;

      result = first + second;
      first = second;
      second = result;
    }

    return result;
  }
};
```


Solution for the climbing stairs problem from LeetCode.

Climbing Stairs

LeetCode Climbing Stairs Solution


# Combine Two Tables Problem & Solution

Write a SQL query for a report that provides the following information for each person in the `Person` table, regardless if there is an address for each of those people: `FirstName`, `LastName`, `City`, `State`.

See the [combine two tables problem on LeetCode](https://leetcode.com/problems/combine-two-tables/).

## SQL Solution

```sql
SELECT FirstName, LastName, City, State
FROM Person
LEFT JOIN Address ON Person.PersonId = Address.PersonId;
```


Solution for the combine two tables problem from LeetCode.

Combine Two Tables

LeetCode Combine Two Tables Solution


# Contains Duplicate Problem & Solution

Given an integer array `nums`, return true if any value appears at least twice in the array, and return false if every element is distinct.

See the [contains duplicate problem on LeetCode](https://leetcode.com/problems/contains-duplicate/).

## C++ Solution

The runtime complexity of the algorithm is $O(n\log{}n)$.

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  bool containsDuplicate(vector<int>& nums) {
    sort(nums.begin(), nums.end());

    for (int i = 0; i < nums.size() - 1; ++i) {
      if (nums[i] == nums[i + 1]) {
        return true;
      }
    }

    return false;
  }
};
```


Solution for the contains duplicate problem from LeetCode.

Contains Duplicate

LeetCode Contains Duplicate Solution


# Convert a Number to Hexadecimal Problem & Solution

Given an integer `num`, return a string representing its hexadecimal representation.
For negative integers, two’s complement method is used.

All the letters in the answer string should be lowercase characters, and there should not be any leading zeros in the answer except for the zero itself.

Note: You are not allowed to use any built-in library method to directly solve this problem.

See the [convert a number to hexadecimal problem on LeetCode](https://leetcode.com/problems/convert-a-number-to-hexadecimal/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  string toHex(int num) {
    if (num == 0) {
      return "0";
    }

    string result = "";
    
    // Converts to two's complement.
    uint unum = (uint)num;

    while (unum > 0) {
      int r = unum % 16;
      result += r < 10 ? r + '0' : r - 10 + 'a';
      unum /= 16;
    }
    
    reverse(result.begin(), result.end());

    return result;
  }
};
```


Solution for the convert a number to hexadecimal problem from LeetCode.

Convert a Number to Hexadecimal

LeetCode Convert a Number to Hexadecimal Solution


# Count Primes Problem & Solution

Count the number of prime numbers less than a non-negative number, `n`.

See the [count primes problem on LeetCode](https://leetcode.com/problems/count-primes/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int countPrimes(int n) {
    if (n < 2) {
      return 0;
    }

    vector<bool> sieve(n, true);
    sieve[0] = false;
    sieve[1] = false;

    for (int i = 2; i < n; ++i) {
      if (sieve[i]) {
        for (int j = i * 2; j < n; j += i) {
          sieve[j] = false;
        }
      }
    }

    int result = 0;
    for (int i = 2; i < n; ++i) {
      if (sieve[i]) {
        result += 1;
      }
    }

    return result;
  }
};
```


Solution for the count primes problem from LeetCode.

Count Primes

LeetCode Count Primes Solution


# Counting Bits Problem & Solution

Given an integer `n`, return an array `ans` of length `n + 1` such that for each `i (0 <= i <= n)`, `ans[i]` is the number of 1's in the binary representation of `i`.

See the [counting bits problem on LeetCode](https://leetcode.com/problems/counting-bits/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  vector<int> countBits(int n) {
    vector<int> results(n + 1, 0);
    
    for (int i = 1; i < results.size(); i++) {
      results[i] = __builtin_popcount(i);
    }
    
    return results;
  }
};
```


Solution for the counting bits problem from LeetCode.

Counting Bits

LeetCode Counting Bits Solution


# Delete Node in a Linked List Problem & Solution

Write a function to delete a node in a singly-linked list.
You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly.
It is guaranteed that the node to be deleted is not a tail node in the list.

See the [delete node in a linked list problem on LeetCode](https://leetcode.com/problems/delete-node-in-a-linked-list/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  void deleteNode(ListNode* node) {
    ListNode* cursor = node->next;

    *node = *cursor;

    delete cursor;
  }
};
```


Solution for the delete node in a linked list problem from LeetCode.

Delete Node in a Linked List

LeetCode Delete Node in a Linked List Solution


# Distribute Candies Problem & Solution

Alice has `n` candies, where the ith candy is of type `candyType[i]`.
Alice noticed that she started to gain weight, so she visited a doctor.

The doctor advised Alice to only eat `n / 2` of the candies she has (`n` is always even).
Alice likes her candies very much, and she wants to eat the maximum number of different types of candies while still following the doctor's advice.

Given the integer array `candyType` of length `n`, return the maximum number of different types of candies she can eat if she only eats `n / 2` of them.

See the [distribute candies problem on LeetCode](https://leetcode.com/problems/distribute-candies/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int distributeCandies(vector<int>& candyType) {
    unordered_set<int> uniques;

    for (int i = 0; i < candyType.size(); ++i) {
      uniques.insert(candyType[i]);
    }

    return min(uniques.size(), candyType.size() / 2);
  }
};
```


Solution for the distribute candies problem from LeetCode.

Distribute Candies

LeetCode Distribute Candies Solution


# Duplicate Emails Problem & Solution

Write a SQL query to find all duplicate emails in a table named `Person`.

See the [duplicate emails problem on LeetCode](https://leetcode.com/problems/duplicate-emails/).

## SQL Solution

```sql
SELECT Email
FROM Person
GROUP BY Email
HAVING COUNT(Email) > 1;
```


Solution for the duplicate emails problem from LeetCode.

Duplicate Emails

LeetCode Duplicate Emails Solution


# Excel Sheet Column Number Problem & Solution

Given a string `columnTitle` that represents the column title as appear in an Excel sheet, return its corresponding column number.

See the [Excel sheet column number problem on LeetCode](https://leetcode.com/problems/excel-sheet-column-number/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int titleToNumber(string columnTitle) {
    int result = 0;

    for (int i = 0; i < columnTitle.size(); ++i) {

      // The parentheses to calculate the digits are used to avoid overflow.
      result = result * 26 + (columnTitle[i] - 'A' + 1);
    }

    return result;
  }
};
```


Solution for the Excel sheet column number problem from LeetCode.

Excel Sheet Column Number

LeetCode Excel Sheet Column Number Solution


# Excel Sheet Column Title Problem & Solution

Given an integer `columnNumber`, return its corresponding column title as it appears in an Excel sheet.

See the [Excel sheet column title problem on LeetCode](https://leetcode.com/problems/excel-sheet-column-title/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  string convertToTitle(int columnNumber) {
    string result;

    while (columnNumber > 0) {

      // Must take into account the offset of the column number.
      --columnNumber;

      result += columnNumber % 26 + 'A';
      columnNumber /= 26;
    }

    reverse(result.begin(), result.end());

    return result;
  }
};
```


Solution for the Excel sheet column title problem from LeetCode.

Excel Sheet Column Title

LeetCode Excel Sheet Column Title Solution


# Factorial Trailing Zeroes Problem & Solution

Given an integer `n`, return the number of trailing zeroes in `n!`.

See the [factorial trailing zeroes problem on LeetCode](https://leetcode.com/problems/factorial-trailing-zeroes/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int trailingZeroes(int n) {
    int result = 0;
    
    // Sums up the powers of 5 at each step, skipping other factors than 5.
    while (n > 0) {
      result += n / 5;
      n /= 5;
    }
    
    return result;
  }
};
```


Solution for the factorial trailing zeroes problem from LeetCode.

Factorial Trailing Zeroes

LeetCode Factorial Trailing Zeroes Solution


# Find the Difference Problem & Solution

You are given two strings `s` and `t`.
String `t` is generated by random shuffling string `s` and then add one more letter at a random position.
Return the letter that was added to `t`.

See the [find the difference problem on LeetCode](https://leetcode.com/problems/find-the-difference/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  char findTheDifference(string s, string t) {
    unordered_map<char, int> histogram;
    
    for (int i = 0; i < s.size(); ++i) {
      if (histogram.find(s[i]) == histogram.end()) {
        histogram[s[i]] = 1;
      } else {
        ++histogram[s[i]];
      }
    }
    
    for (int i = 0; i < t.size(); ++i) {
      if (histogram.find(t[i]) == histogram.end()) {
        return t[i];
      } else if (histogram[t[i]]-- == 0) {
        return t[i];
      }
    }
    
    return 0;
  }
};
```


Solution for the find the difference problem from LeetCode.

Find the Difference

LeetCode Find the Difference Solution


# First Bad Version Problem & Solution

You are a product manager and currently leading a team to develop a new product.
Unfortunately, the latest version of your product fails the quality check.
Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have `n` versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API `bool isBadVersion(version)` which returns whether version is bad.
Implement a function to find the first bad version.
You should minimize the number of calls to the API.

See the [first bad version problem on LeetCode](https://leetcode.com/problems/first-bad-version/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
  int firstBadVersion(int n) {
    int low = 0;
    int high = n;
    while (low < high) {
      int mid = low + (high - low) / 2;

      if (!isBadVersion(mid)) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }

    return low;
  }
};
```


Solution for the first bad version problem from LeetCode.

First Bad Version

LeetCode First Bad Version Solution


# First Unique Character in a String Problem & Solution

Given a string `s`, find the first non-repeating character in it and return its index.
If it does not exist, return -1.

See the [first unique character in a string problem on LeetCode](https://leetcode.com/problems/first-unique-character-in-a-string/).

## C++ Solution

The runtime complexity of this algorithm is $O(n)$.

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int firstUniqChar(string s) {
    vector<int> positions('z' - 'a' + 1, -1);
    vector<bool> repeats('z' - 'a' + 1, false);

    for (int i = 0; i < s.size(); ++i) {
      int offset = s[i] - 'a';

      if (positions[offset] >= 0) {
        repeats[offset] = true;
      }

      if (!repeats[offset]) {
        positions[offset] = i;
      }
    }

    int minarg = INT_MAX;
    for (int i = 0; i < repeats.size(); ++i) {
      if (!repeats[i] && positions[i] >= 0) {
        minarg = min(minarg, positions[i]);
      }
    }
    
    return minarg == INT_MAX ? -1 : minarg;
  }
};
```


Solution for the first unique character in a string problem from LeetCode.

First Unique Character in a String

LeetCode First Unique Character in a String Solution


# Fizz Buzz Problem & Solution

Given an integer `n`, return a string array answer (1-indexed) where:

*   `answer[i] == "FizzBuzz"` if `i` is divisible by 3 and 5.
*   `answer[i] == "Fizz"` if `i` is divisible by 3.
*   `answer[i] == "Buzz"` if `i` is divisible by 5.
*   `answer[i] == i` if non of the above conditions are true.

See the [fizz buzz problem on LeetCode](https://leetcode.com/problems/fizz-buzz/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  vector<string> fizzBuzz(int n) {
    vector<string> result(n, "");
    
    for (int i = 0; i < result.size(); ++i) {
      if ((i + 1) % 3 == 0 && (i + 1) % 5 == 0) {
        result[i] = "FizzBuzz";
      } else if ((i + 1) % 3 == 0) {
        result[i] = "Fizz";
      } else if ((i + 1) % 5 == 0) {
        result[i] = "Buzz";
      } else {
        result[i] = to_string(i + 1);
      }
    }
    
    return result;
  }
};
```


Solution for the fizz buzz problem from LeetCode.

Fizz Buzz

LeetCode Fizz Buzz Solution


# Guess Number Higher or Lower Problem & Solution

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to `n`.
You have to guess which number I picked.
Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.
You call a pre-defined API `int guess(int num)`, which returns 3 possible results:

*   -1: The number I picked is lower than your guess (i.e. `pick < num`).
*   1: The number I picked is higher than your guess (i.e. `pick > num`).
*   0: The number I picked is equal to your guess (i.e. `pick == num`).

Return the number that I picked.

See the [guess number higher or lower problem on LeetCode](https://leetcode.com/problems/guess-number-higher-or-lower/).

## C++ Solution

The runtime complexity of the algorithm is $O(\log{}n)$.

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			         1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */
class Solution {
public:
  int guessNumber(int n) {
    int low = 1;
    int high = n;
    while (low < high) {
      int mid = low + (high - low) / 2;
      int result = guess(mid);

      if (result == 0) {
        return mid;
      } else if (result > 0) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    
    return low;
  }
};
```


Solution for the guess number higher or lower problem from LeetCode.

Guess Number Higher or Lower

LeetCode Guess Number Higher or Lower Solution


# Hamming Distance Problem & Solution

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers `x` and `y`, return the Hamming distance between them.

See the [Hamming distance problem on LeetCode](https://leetcode.com/problems/hamming-distance/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int hammingDistance(int x, int y) {
    return __builtin_popcount(x ^ y);
  }
};
```


Solution for the Hamming distance problem from LeetCode.

Hamming Distance

LeetCode Hamming Distance Solution


# Happy Number Problem & Solution

Write an algorithm to determine if a number `n` is happy.

A happy number is a number defined by the following process:

*   Starting with any positive integer, replace the number by the sum of the squares of its digits.
*   Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
*   Those numbers for which this process ends in 1 are happy.

Return true if `n` is a happy number, and false if not.

See the [happy number problem on LeetCode](https://leetcode.com/problems/happy-number/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  bool isHappy(int n) {
    int slow = happy(n);
    int fast = happy(slow);

    while (slow != fast) {
      slow = happy(slow);
      fast = happy(happy(fast));
    }

    return slow == 1;
  }

private:
  int happy(int n) {
    int sum = 0;

    while (n > 0) {
      sum += pow(n % 10, 2);
      n /= 10;
    }

    return sum;
  }
};
```


Solution for the happy number problem from LeetCode.

Happy Number

LeetCode Happy Number Solution


# Implement strstr Problem & Solution

Implement `strstr()`. Return the index of the first occurrence of `needle` in `haystack`, or -1 if `needle` is not part of `haystack`.

See the [implement strstr problem on LeetCode](https://leetcode.com/problems/implement-strstr/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int strStr(string haystack, string needle) {
    if (needle.empty()) {
      return 0;
    }

    for (int i = 0; i <= (int)(haystack.size() - needle.size()); ++i) {
      bool ok = true;
      for (int j = 0; j < needle.size(); ++j) {
        ok &= haystack[i + j] == needle[j];
        if (!ok) {
          break;
        }
      }

      if (ok) {
        return i;
      }
    }

    return -1;
  }
};
```


Solution for the implement strstr problem from LeetCode.

Implement strstr

LeetCode Implement strstr Solution


# Intersection of Two Arrays II Problem & Solution

Given two integer arrays `nums1` and `nums2`, return an array of their intersection.
Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

See the [intersection of two arrays ii problem on LeetCode](https://leetcode.com/problems/intersection-of-two-arrays-ii/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    vector<int> usage1(1001, 0);
    vector<int> usage2(1001, 0);
    
    for (int i = 0; i < nums1.size(); ++i) {
      ++usage1[nums1[i]];
    }
    
    for (int i = 0; i < nums2.size(); ++i) {
      ++usage2[nums2[i]];
    }
    
    vector<int> result;
    
    for (int i = 0; i < 1001; ++i) {
      if (usage1[i] > 0 && usage2[i] > 0) {
        for (int j = 0; j < min(usage1[i], usage2[i]); ++j) {
          result.push_back(i);
        }
      }
    }
    
    return result;
  }
};
```


Solution for the intersection of two arrays ii problem from LeetCode.

Intersection of Two Arrays II

LeetCode Intersection of Two Arrays II Solution


# Intersection of Two Arrays Problem & Solution

Given two integer arrays `nums1` and `nums2`, return an array of their intersection.
Each element in the result must be unique and you may return the result in any order.

See the [intersection of two arrays problem on LeetCode](https://leetcode.com/problems/intersection-of-two-arrays/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    vector<bool> usage(1001, false);
    
    for (int i = 0; i < nums1.size(); ++i) {
      usage[nums1[i]] = true;
    }
    
    unordered_set<int> result;

    for (int i = 0; i < nums2.size(); ++i) {
      if (usage[nums2[i]]) {
        result.insert(nums2[i]);
      }
    }
    
    return vector<int>{result.begin(), result.end()};
  }
};
```


Solution for the intersection of two arrays problem from LeetCode.

Intersection of Two Arrays

LeetCode Intersection of Two Arrays Solution


# Intersection of Two Linked Lists Problem & Solution

Given the heads of two singly linked-lists `headA` and `headB`, return the node at which the two lists intersect.
If the two linked lists have no intersection at all, return null.

See the [intersection of two linked lists problem on LeetCode](https://leetcode.com/problems/intersection-of-two-linked-lists/).

## C++ Solution

The runtime complexity of the algorithm is $O(n + m)$.

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int lenA = 0;
    ListNode* cursorA = headA;
    while (cursorA != nullptr) {
      cursorA = cursorA->next;
      ++lenA;
    }

    int lenB = 0;
    ListNode* cursorB = headB;
    while (cursorB != nullptr) {
      cursorB = cursorB->next;
      ++lenB;
    }

    while (lenA > lenB) {
      headA = headA->next;
      --lenA;
    }

    while (lenB > lenA) {
      headB = headB->next;
      --lenB;
    }

    // At this step, `lenA == lenB`.
    while (lenA > 0) {
      if (headA == headB) {
        return headA;
      }

      headA = headA->next;
      headB = headB->next;
      --lenA;
    }

    return nullptr;
  }
};
```


Solution for the intersection of two linked lists problem from LeetCode.

Intersection of Two Linked Lists

LeetCode Intersection of Two Linked Lists Solution


# Invert Binary Tree Problem & Solution

Given the `root` of a binary tree, invert the tree, and return its `root`.

See the [invert binary tree problem on LeetCode](https://leetcode.com/problems/invert-binary-tree/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) {
      return nullptr;
    }
    
    swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    
    return root;
  }
};
```


Solution for the invert binary tree problem from LeetCode.

Invert Binary Tree

LeetCode Invert Binary Tree Solution


# Is Subsequence Problem & Solution

Given two strings `s` and `t`, return true if `s` is a subsequence of `t`, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

See the [is subsequence problem on LeetCode](https://leetcode.com/problems/is-subsequence/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  bool isSubsequence(string s, string t) {
    int j = 0;
    for (int i = 0; i < s.size(); ++i) {
      while (j < t.size() && s[i] != t[j]) {
        ++j;
      }

      if (j == t.size()) {
        return false;
      }
      
      ++j;
    }
    
    return true;
  }
};
```


Solution for the is subsequence problem from LeetCode.

Is Subsequence

LeetCode Is Subsequence Solution


# Isomorphic Strings Problem & Solution

Given two strings `s` and `t`, determine if they are isomorphic.
Two strings `s` and `t` are isomorphic if the characters in `s` can be replaced to get `t`.
All occurrences of a character must be replaced with another character while preserving the order of characters.
No two characters may map to the same character, but a character may map to itself.

See the [isomorphic strings problem on LeetCode](https://leetcode.com/problems/isomorphic-strings/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  bool isIsomorphic(string s, string t) {
    unordered_map<char, char> map;
    set<char> used;

    for (int i = 0; i < s.size(); ++i) {
      if (map.find(s[i]) == map.end() &&
          used.find(t[i]) == used.end()) {
        map[s[i]] = t[i];
        used.insert(t[i]);
      }

      if (map[s[i]] != t[i]) {
        return false;
      }
    }

    return true;
  }
};
```


Solution for the isomorphic strings problem from LeetCode.

Isomorphic Strings

LeetCode Isomorphic Strings Solution


# Length of Last Word Problem & Solution

Given a string `s`, which consists of some words separated by spaces, return the length of the last word in the string. If the last word does not exist, return 0.

See the [length of last word problem on LeetCode](https://leetcode.com/problems/length-of-last-word/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int lengthOfLastWord(string s) {
    int i = s.size() - 1;
    while (i >= 0 && s[i] == ' ') {
      --i;
    }

    int j = i;
    while (j >= 0 && s[j] != ' ') {
      --j;
    }

    return i - j;
  }
};
```


Solution for the length of last word problem from LeetCode.

Length of Last Word

LeetCode Length of Last Word Solution


# Linked List Cycle Problem & Solution

Given `head`, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.
Internally, pos is used to denote the index of the node that tail's next pointer is connected to.
Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.

See the [linked list cycle problem on LeetCode](https://leetcode.com/problems/linked-list-cycle/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  bool hasCycle(ListNode *head) {
    if (head == nullptr || head->next == nullptr) {
      return false;      
    }

    ListNode* slow = head;
    ListNode* fast = head->next;

    while (slow != nullptr &&
           fast != nullptr && fast->next != nullptr &&
           slow != fast) {
      slow = slow->next;
      fast = fast->next->next;
    }
    
    return slow == fast;
  }
};
```


Solution for the linked list cycle problem from LeetCode.

Linked List Cycle

LeetCode Linked List Cycle Solution


# Longest Common Prefix Problem & Solution

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "".

See the [longest common prefix problem on LeetCode](https://leetcode.com/problems/longest-common-prefix/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  string longestCommonPrefix(vector<string>& strs) {
    if (strs.size() == 1) {
      return strs[0];
    }

    int max = 0;
    while (true) {
      bool ok = true;
      for (int i = 1; i < strs.size(); ++i) {
        if (max >= strs[i].size() ||
            strs[i][max] != strs[0][max]) {
          ok = false;
          break;
        }
      }

      if (ok) {
        ++max;
      } else {
        break;
      }
    }

    return strs[0].substr(0, max);
  }
};
```


Solution for the longest common prefix problem from LeetCode.

Longest Common Prefix

LeetCode Longest Common Prefix Solution


# Longest Palindrome Problem & Solution

Given a string `s` which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome here.

See the [longest palindrome problem on LeetCode](https://leetcode.com/problems/longest-palindrome/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int longestPalindrome(string s) {
    unordered_map<char, int> map;
    
    for (int i = 0; i < s.size(); ++i) {
      ++map[s[i]];
    }
    
    int even = 0;
    int odd = 0;
    for (auto& it: map) {
      if (it.second % 2 == 0) {
        even += it.second;
      } else {
        even += it.second - 1;
        odd = 1;
      }
    }
    
    return even + odd;
  }
};
```


Solution for the longest palindrome problem from LeetCode.

Longest Palindrome

LeetCode Longest Palindrome Solution


# Lowest Common Ancestor of a Binary Search Tree Problem & Solution

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: "The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself)."

See the [lowest common ancestor of a binary search tree problem on LeetCode](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (p->val < root->val && q->val < root->val) {
      return lowestCommonAncestor(root->left, p, q);
    } else if (p->val > root->val && q->val > root->val) {
      return lowestCommonAncestor(root->right, p, q);
    } else {
      return root;
    }
  }
};
```


Solution for the lowest common ancestor of a binary search tree problem from LeetCode.

Lowest Common Ancestor of a Binary Search Tree

LeetCode Lowest Common Ancestor of a Binary Search Tree Solution


# Majority Element Problem & Solution

Given an array `nums` of size `n`, return the majority element.

The majority element is the element that appears more than `⌊n / 2⌋` times.
You may assume that the majority element always exists in the array.

See the [majority element problem on LeetCode](https://leetcode.com/problems/majority-element/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int majorityElement(vector<int>& nums) {
    int candidate = 0;
    int count = 0;
    
    for (int i = 0; i < nums.size(); ++i) {
      if (count == 0) {
        candidate = nums[i];
      }
      
      count += nums[i] == candidate ? 1 : -1;
    }
    
    return candidate;
  }
};
```


Solution for the majority element problem from LeetCode.

Majority Element

LeetCode Majority Element Solution


# Maximum Depth of Binary Tree Problem & Solution

Given the `root` of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

See the [maximum depth of binary tree problem on LeetCode](https://leetcode.com/problems/maximum-depth-of-binary-tree/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  int maxDepth(TreeNode* root) {
    if (root == nullptr) {
      return 0;
    }

    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
  }
};
```


Solution for the maximum depth of binary tree problem from LeetCode.

Maximum Depth of Binary Tree

LeetCode Maximum Depth of Binary Tree Solution


# Maximum Subarray Problem & Solution

Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

See the [maximum subarray problem on LeetCode](https://leetcode.com/problems/maximum-subarray/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int maxSubArray(vector<int>& nums) {
    int largest = INT_MIN;
    int sum = 0;

    for (int i = 0; i < nums.size(); ++i) {

      // Breaks the streak of contiguous subarray if the current number is
      // greater than the running sum; but, only if the sum is negative.
      if (nums[i] >= sum && sum < 0) {
        sum = nums[i];
      } else {
        sum += nums[i];
      }

      largest = max(largest, sum);
    }

    return largest;
  }
};
```


Solution for the maximum subarray problem from LeetCode.

Maximum Subarray

LeetCode Maximum Subarray Solution


# Merge Sorted Array Problem & Solution

You are given two integer arrays `nums1` and `nums2`, sorted in non-decreasing order, and two integers `m` and `n`, representing the number of elements in `nums1` and `nums2` respectively.
Merge `nums1` and `nums2` into a single array sorted in non-decreasing order.

See the [merge sorted array problem on LeetCode](https://leetcode.com/problems/merge-sorted-array/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int k = m + n - 1;
    int i = m - 1;
    int j = n - 1;

    while (i >= 0 && j >= 0) {
      if (nums1[i] > nums2[j]) {
        nums1[k--] = nums1[i--];
      } else {
        nums1[k--] = nums2[j--];
      }
    }

    while (j >= 0) {
      nums1[k--] = nums2[j--];
    }
  }
};
```


Solution for you are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge Sorted Array

LeetCode Merge Sorted Array Solution


# Merge Two Sorted Lists Problem & Solution

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

See the [merge two sorted lists problem on LeetCode](https://leetcode.com/problems/merge-two-sorted-lists/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode() : val(0), next(nullptr) {}
 *   ListNode(int x) : val(x), next(nullptr) {}
 *   ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == nullptr) {
      return l2;
    }

    if (l2 == nullptr) {
      return l1;
    }

    ListNode* root = new ListNode();
    ListNode* cursor = root;

    while (l1 != nullptr && l2 != nullptr) {
      if (l1->val > l2->val) {
        cursor->next = l2;
        l2 = l2->next;
        cursor = cursor->next;
      } else {
        cursor->next = l1;
        l1 = l1->next;
        cursor = cursor->next;
      }
    }

    if (l1 != nullptr) {
      cursor->next = l1;
    }

    if (l2 != nullptr) {
      cursor->next = l2;
    }

    cursor = root->next;
    delete root;

    return cursor;
  }
};
```


Solution for the merge two sorted lists problem from LeetCode.

Merge Two Sorted Lists

LeetCode Merge Two Sorted Lists Solution


# Minimum Depth of Binary Tree Problem & Solution

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
A leaf is a node with no children.

See the [minimum depth of binary tree problem on LeetCode](https://leetcode.com/problems/minimum-depth-of-binary-tree/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("max-inline-insns-recursive-auto")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

/**
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  int minDepth(TreeNode* root) {
    if (root == nullptr) {
      return 0;
    }

    int result = INT_MAX;

    minDepth(root, 0, result);

    return result;
  }

private:
  void minDepth(TreeNode* root, int depth, int& result) {
    if (root == nullptr) {
      return;
    }

    if (root->left == nullptr && root->right == nullptr) {
      result = min(result, depth + 1);
    }

    minDepth(root->left, depth + 1, result);
    minDepth(root->right, depth + 1, result);
  }
};
```


Solution for the minimum depth of binary tree problem from LeetCode.

Minimum Depth of Binary Tree

LeetCode Minimum Depth of Binary Tree Solution


# Missing Number Problem & Solution

Given an array nums containing `n` distinct numbers in the range `[0, n]`, return the only number in the range that is missing from the array.

See the [missing number problem on LeetCode](https://leetcode.com/problems/missing-number/).

## C++ Solution

The runtime complexity of this algorithm is $O(n)$.

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int missingNumber(vector<int>& nums) {
    int sum = nums.size();
    for (int i = 0; i < nums.size(); ++i) {
      sum += i;
      sum -= nums[i];
    }

    return sum;
  }
};
```


Solution for the missing number problem from LeetCode.

Missing Number

LeetCode Missing Number Solution


# Move Zeroes Problem & Solution

Given an integer array `nums`, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.

See the [move zeroes problem on LeetCode](https://leetcode.com/problems/move-zeroes/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  void moveZeroes(vector<int>& nums) {
    for (int i = 0; i < nums.size(); ++i) {
      if (nums[i] == 0) {
        int j = i + 1;
        
        // Skips consecutive zeroes.
        while (j < nums.size() && nums[j] == 0) {
          ++j;
        }

        rotate(nums.begin() + i, nums.begin() + j, nums.end());
      }
    }
  }
};
```


Solution for the move zeroes problem from LeetCode.

Move Zeroes

LeetCode Move Zeroes Solution


# Nim Game Problem & Solution

You are playing the following Nim Game with your friend:

*   Initially, there is a heap of stones on the table.
*   You and your friend will alternate taking turns, and you go first.
*   On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
*   The one who removes the last stone is the winner.

Given `n`, the number of stones in the heap, return true if you can win the game assuming both you and your friend play optimally, otherwise return false.

See the [nim game problem on LeetCode](https://leetcode.com/problems/nim-game/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  bool canWinNim(int n) {

    // You can always reduce a game of `n` to a game of 4.
    // If there are one to three pieces left, you can win.
    return n % 4 != 0;
  }
};
```


Solution for the nim game problem from LeetCode.

Nim Game

LeetCode Nim Game Solution


# Number of 1 Bits Problem & Solution

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

See the [number of 1 bits problem on LeetCode](https://leetcode.com/problems/number-of-1-bits/).

## C++ Solution

```cpp
#pragma GCC optimize("Ofast")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  int hammingWeight(uint32_t n) {
    return  __builtin_popcount(n);
  }
};
```


Solution for the number of 1 bits problem from LeetCode.

Blog

LeetCode Problems and Solutions

Project Euler Problems and Solutions