
# Coding Interview Tips

## Ask Questions

First things first, ask questions before you jump into coding.

## Draw Diagrams

If required, and only if required, draw diagrams.

```dot An example diagram.
digraph {
  Hello -> World
}
```

## 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


# Focus on problems, not products

When you are working for a corporation or a startup, we believe focusing on problems and not products will yield the best results in your career progression.


An opinionated writeup as to why you should focus on problems and not products when you are working for someone else.

Focus on problems, not products


# 1-bit and 2-bit Characters Problem & Solution

We have two special characters:

*   The first character can be represented by one bit 0.
*   The second character can be represented by two bits (10 or 11).

Given a binary array `bits` that ends with 0, return true if the last character must be a one-bit character.

See the [1-bit and 2-bit characters problem on LeetCode](https://leetcode.com/problems/1-bit-and-2-bit-characters/).

## 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 isOneBitCharacter(vector<int>& bits) {
    for (int i = 0; i < bits.size(); ++i) {
      
      // Skips two positions if `bits[i]` is 1 because the next position can't be a one-bit character.
      if (bits[i] == 1) {
        i += 1;
      } else if (i == bits.size() - 1 && bits[i] == 0) {
        return true;
      }
    }

    return false;
  }
};
```


Solution for we have two special characters: The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11). Given a binary array bits that ends with 0, return true if the last character must be a one-bit character.

1-bit and 2-bit Characters

LeetCode 1-bit and 2-bit Characters Solution


# 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


# Assign Cookies Problem & Solution

Assume you are an awesome parent and want to give your children some cookies.
But, you should give each child at most one cookie.

Each child `i` has a greed factor `g[i]`, which is the minimum size of a cookie that the child will be content with; and each cookie `j` has a size `s[j]`.
If `s[j] >= g[i]`, we can assign the cookie `j` to the child `i`, and the child `i` will be content.
Your goal is to maximize the number of your content children and output the maximum number.

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

## 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 findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    
    int i = 0;
    int j = 0;
    while (i < g.size()) {
      while (j < s.size() && s[j] < g[i]) {
        ++j;
      }

      if (j == s.size()) {
        break;
      }
      
      ++i;
      ++j;
    }

    return i;
  }
};
```


Solution for the assign cookies problem from LeetCode.

Assign Cookies

LeetCode Assign Cookies 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


# Base 7 Problem & Solution

Given an integer `num`, return a string of its base 7 representation.

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

## 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 convertToBase7(int num) {
    int positive = abs(num);

    string result;
    while (positive > 0) {
      result += positive % 7 + '0';
      positive /= 7;
    }
    
    if (num < 0) {
      result += '-';
    } else if (num == 0) {
      result = "0";
    }

    reverse(result.begin(), result.end());
    
    return result;
  }
};
```


Solution for given an integer num, return a string of its base 7 representation.

Base 7

LeetCode Base 7 Solution


# Best Time to Buy and Sell Stock II Problem & Solution

You are given an array prices where `prices[i]` is the price of a given stock on the `i`th day.

Find the maximum profit you can achieve.
You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

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

## 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 maxProfit(vector<int>& prices) {
    int profit = 0;
    for (int i = 1; i < prices.size(); ++i) {
      if (prices[i - 1] < prices[i]) {
        profit += prices[i] - prices[i - 1];
      }
    }
    
    return profit;
  }
};
```


Solution for you are given an array prices where prices[i] is the price of a given stock on the ith day. Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times). Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Best Time to Buy and Sell Stock II

LeetCode Best Time to Buy and Sell Stock II 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 Number with Alternating Bits Problem & Solution

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

See the [binary number with alternating bits problem on LeetCode](https://leetcode.com/problems/binary-number-with-alternating-bits/).

## 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 hasAlternatingBits(int n) {
    int prev = n % 2;
    n /= 2;

    while (n > 0) {
      int mod = n % 2;
      n /= 2;
      
      if (mod == prev) {
        return false;
      }
      
      prev = mod;
    }
    
    return true;
  }
};
```


Solution for given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

Binary Number with Alternating Bits

LeetCode Binary Number with Alternating Bits Solution


# Binary Search Problem & Solution

Given an array of integers `nums` which is sorted in ascending order, and an integer `target`, write a function to search `target` in `nums`.
If `target` exists, then return its index.
Otherwise, return -1.

You must write an algorithm with $O(\log{}n)$ runtime complexity.

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

## 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 search(vector<int>& nums, int target) {
    int low = 0;
    int high = nums.size() - 1;
    while (low < high) {

      // Uses this way of calculating the midpoint vs. `(low + high) / 2` to avoid overflow.
      int mid = low + (high - low) / 2;
      if (target > nums[mid]) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    
    return target == nums[low] ? low : -1;
  }
};
```


Solution for given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity.

Binary Search

LeetCode Binary Search 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


# Binary Tree Tilt Problem & Solution

Given the `root` of a binary tree, return the sum of every tree node's tilt.

The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values.
If a node does not have a left child, then the sum of the left subtree node values is treated as 0.
The rule is similar if there the node does not have a right child.

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

## C++ Solution

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

static const int _=[](){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 findTilt(TreeNode* root) {
    int result = 0;
    findTilt(root, result);
    
    return result;
  }

private:
  int findTilt(TreeNode* root, int& sum) {
    if (root == nullptr) {
      return 0;
    }
    
    if (root->left == nullptr && root->right == nullptr) {
      return root->val;
    }
    
    int left = findTilt(root->left, sum);
    int right = findTilt(root->right, sum);
    
    sum += abs(left - right);
    
    return left + right + root->val;
  }
};
```


Solution for given the root of a binary tree, return the sum of every tree node's tilt. The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values. If a node does not have a left child, then the sum of the left subtree node values is treated as 0. The rule is similar if there the node does not have a right child.

Binary Tree Tilt

LeetCode Binary Tree Tilt Solution


# Can Place Flowers Problem & Solution

You have a long flowerbed in which some of the plots are planted, and some are not.
However, flowers cannot be planted in adjacent plots.

Given an integer array `flowerbed` containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer `n`, return if `n` new flowers can be planted in the `flowerbed` without violating the no-adjacent-flowers rule.

See the [can place flowers problem on LeetCode](https://leetcode.com/problems/can-place-flowers/).

## 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 canPlaceFlowers(vector<int>& flowerbed, int n) {
    int j = 0;
    for (int i = 0; i < flowerbed.size(); ++i) {
      if (flowerbed[i] == 1) {
        continue;
      }

      bool left = i == 0 || (i > 0 && flowerbed[i - 1] == 0);
      bool right = i == flowerbed.size() - 1 || (i < flowerbed.size() - 1 && flowerbed[i + 1] == 0);

      if (left && right) {
        flowerbed[i] = 1;
        ++j;
      }
    }
    
    return j >= n;
  }
};
```


Solution for you have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots. Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

Can Place Flowers

LeetCode Can Place Flowers 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


# Construct the Rectangle Problem & Solution

A web developer needs to know how to design a web page's size.
So, given a specific rectangular web page's area, your job by now is to design a rectangular web page, whose length `L` and width `W` satisfy the following requirements:

*   The area of the rectangular web page you designed must equal to the given target area.
*   The width `W` should not be larger than the length `L`, which means `L >= W`.
*   The difference between length `L` and width `W` should be as small as possible.

Return an array `[L, W]` where `L` and `W` are the length and width of the web page you designed in sequence.

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

## 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<int> constructRectangle(int area) {

    // Starts with the square root and keeps decrementing to find an exact match.
    for (int i = sqrt(area); i > 0; --i) {
      if (area % i == 0) {
        
        // The denominator keeps getting smaller, so `area / i` will be larger.
        return {area / i, i};
      }
    }
    
    // If the area is a prime number, return itself because it's the only way to decompose.
    return {area, 1};
  }
};
```


Solution for a web developer needs to know how to design a web page's size. So, given a specific rectangular web page's area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements: The area of the rectangular web page you designed must equal to the given target area. The width W should not be larger than the length L, which means L >= W. The difference between length L and width W should be as small as possible. Return an array [L, W] where L and W are the length and width of the web page you designed in sequence.

Construct the Rectangle

LeetCode Construct the Rectangle Solution


# Contains Duplicate II Problem & Solution

Given an integer array `nums` and an integer `k`, return true if there are two distinct indices `i` and `j` in the array such that `nums[i] == nums[j]` and `abs(i - j) <= k`.

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

## 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 containsNearbyDuplicate(vector<int>& nums, int k) {

    // Represents the most recent position we saw for each number.
    unordered_map<int, int> js;
    for (int i = 0; i < nums.size(); ++i) {
      if (js.find(nums[i]) != js.end() &&
          abs(i - js[nums[i]]) <= k) {
        return true;
      }
      
      // Keeps track of the last position we saw for `nums[i]`.
      js[nums[i]] = i;
    }
    
    return false;
  }
};
```


Solution for given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Contains Duplicate II

LeetCode Contains Duplicate II 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


# Convert Sorted Array to Binary Search Tree Problem & Solution

Given an integer array `nums` where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

See the [convert sorted array to binary search tree problem on LeetCode](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/).

## C++ Solution

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

static const int _=[](){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* sortedArrayToBST(vector<int>& nums) {
    TreeNode* root = nullptr;
    sortedArrayToBST(nums, 0, nums.size() - 1, &root);

    return root;
  }
  
private:
  void sortedArrayToBST(vector<int>& nums, int low, int high, TreeNode** node) {
    if (low > high) {
      return;
    }
    
    int mid = low + (high - low) / 2;
    *node = new TreeNode(nums[mid]);
    sortedArrayToBST(nums, low, mid - 1, &(*node)->left);
    sortedArrayToBST(nums, mid + 1, high, &(*node)->right);
  }
};
```


Solution for given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Convert Sorted Array to Binary Search Tree

LeetCode Convert Sorted Array to Binary Search Tree 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


# Degree of an Array Problem & Solution

Given a non-empty array of non-negative integers `nums`, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of `nums`, that has the same degree as `nums`.

See the [degree of an array problem on LeetCode](https://leetcode.com/problems/degree-of-an-array/).

## 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 findShortestSubArray(vector<int>& nums) {
    int degree = 0;
    unordered_map<int, help> freq;
    for (int i = 0; i < nums.size(); ++i) {
      if (freq.find(nums[i]) == freq.end()) {
        freq[nums[i]] = {1, i, i};
      } else {
        ++freq[nums[i]].count;
        freq[nums[i]].high = i;
      }
      
      degree = max(degree, freq[nums[i]].count);
    }
    
    int argdegree = numeric_limits<int>::max();
    for (auto it = freq.begin(); it != freq.end(); ++it) {
      if (it->second.count == degree) {
        argdegree = min(argdegree, it->second.high - it->second.low + 1);
      }
    }

    return argdegree;
  }
  
private:
  struct help {
    int count;
    int low;
    int high;
  };
};
```


Solution for given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements. Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Degree of an Array

LeetCode Degree of an Array 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;

    // Saves the next node onto the node to be deleted; so, the node to be deleted is actually the next node now.
    *node = *cursor;

    // Frees up memory occupied by the next node; otherwise, the next node lives in memory twice.
    // This deletes the initial location of the next node.
    delete cursor;
  }
};
```


Solution for 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.

Delete Node in a Linked List

LeetCode Delete Node in a Linked List Solution


# Detect Capital Problem & Solution

We define the usage of capitals in a word to be right when one of the following cases holds:

*   All letters in this word are capitals, like "USA".
*   All letters in this word are not capitals, like "leetcode".
*   Only the first letter in this word is capital, like "Google".

Given a string `word`, return true if the usage of capitals in it is right.

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

## 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 detectCapitalUse(string word) {
    bool uppercase = true;
    bool lowercase = true;
    bool sentencecase = true;
    for (int i = 0; i < word.size(); ++i) {
      uppercase &= word[i] >= 'A' && word[i] <= 'Z';
      lowercase &= word[i] >= 'a' && word[i] <= 'z';
      sentencecase &= i == 0
        ? word[i] >= 'A' && word[i] <= 'Z'
        : word[i] >= 'a' && word[i] <= 'z';
    }
    
    return uppercase || lowercase || sentencecase;
  }
};
```


Solution for we define the usage of capitals in a word to be right when one of the following cases holds: All letters in this word are capitals, like USA. All letters in this word are not capitals, like leetcode. Only the first letter in this word is capital, like Google. Given a string word, return true if the usage of capitals in it is right.

Detect Capital

LeetCode Detect Capital Solution


# DI String Match Problem & Solution

A permutation `perm` of `n + 1` integers of all the integers in the range `[0, n]` can be represented as a string `s` of length `n` where:

*   `s[i] == 'I'` if `perm[i] < perm[i + 1]`, and
*   `s[i] == 'D'` if `perm[i] > perm[i + 1]`.

Given a string `s`, reconstruct the permutation `perm` and return it.
If there are multiple valid permutations `perm`, return any of them.

See the [DI string match problem on LeetCode](https://leetcode.com/problems/di-string-match/).

## 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<int> diStringMatch(string s) {
    int low = 0;
    int high = s.size();
    
    vector<int> result(s.size() + 1, 0);
    for (int i = 0; i < s.size(); ++i) {
      if (s[i] == 'I') {
        result[i] = low++;
      } else {
        result[i] = high--;
      }
    }
    
    result[s.size()] = low;
    
    return result;
  }
};
```


Solution for a permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where: s[i] == 'I' if perm[i] < perm[i + 1], and s[i] == 'D' if perm[i] > perm[i + 1]. Given a string s, reconstruct the permutation perm and return it. If there are multiple valid permutations perm, return any of them.

DI String Match

LeetCode DI String Match Solution


# Diameter of Binary Tree Problem & Solution

Given the `root` of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree.
This path may or may not pass through the `root`.

The length of a path between two nodes is represented by the number of edges between them.

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

## C++ Solution

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

static const int _=[](){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 diameterOfBinaryTree(TreeNode* root) {
    int result = 0;
    diameterOfBinaryTree(root, result);
    
    return result;
  }
  
private:
  int diameterOfBinaryTree(TreeNode* root, int& diameter) {
    if (root == nullptr) {
      return -1;
    }

    int left = 1 + diameterOfBinaryTree(root->left, diameter);
    int right = 1 + diameterOfBinaryTree(root->right, diameter);
    diameter = max(diameter, left + right);

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


Solution for given the root of a binary tree, return the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The length of a path between two nodes is represented by the number of edges between them.

Diameter of Binary Tree

LeetCode Diameter of Binary Tree 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 appears 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 given a string columnTitle that represents the column title as appears in an Excel sheet, return its corresponding column number.

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


# Fibonacci Number Problem & Solution

The Fibonacci numbers, commonly denoted `F(n)` form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.
That is,

```
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
```

Given `n`, calculate `F(n)`.

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

## 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 fib(int n) {
    if (n == 0) {
      return 0;
    } else if (n == 1) {
      return 1;
    } else {
      int first = 0;
      int second = 1;
      
      for (int i = 2; i <= n; ++i) {
        int tmp = first + second;

        first = second;
        second = tmp;
      }
      
      return second;
    }
  }
};
```


Solution for the Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.

Fibonacci Number

LeetCode Fibonacci Number Solution


# Find All Numbers Disappeared in an Array Problem & Solution

Given an array `nums` of `n` integers where `nums[i]` is in the range `[1, n]`, return an array of all the integers in the range `[1, n]` that do not appear in `nums`.

See the [find all numbers disappeared in an array problem on LeetCode](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/).

## 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<int> findDisappearedNumbers(vector<int>& nums) {
    vector<int> results;

    for (int i = 0; i < nums.size(); ++i) {
      int j = abs(nums[i]);
      if (nums[j - 1] > 0) {
        
        // Flips the sign for the positions of the numbers we iterated on.
        nums[j - 1] *= -1;
      }
    }
    
    for (int i = 0; i < nums.size(); ++i) {
      
      // The missing numbers will be the positions which are still positive integers.
      if (nums[i] > 0) {
        results.push_back(i + 1);
      }
    }
    
    return results;
  }
};
```


Solution for given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Find All Numbers Disappeared in an Array

LeetCode Find All Numbers Disappeared in an Array Solution


# Find Pivot Index Problem & Solution

Given an array of integers `nums`, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

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

## 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 pivotIndex(vector<int>& nums) {

    // Memoizes the sums from left to right.
    vector<int> leftSum(nums.size(), 0);
    for (int i = 1; i < nums.size(); ++i) {
      leftSum[i] = leftSum[i - 1] + nums[i - 1];
    }

    // Memoizes the sums from right to left.
    vector<int> rightSum(nums.size(), 0);
    for (int i = nums.size() - 2; i >= 0; --i) {
      rightSum[i] = rightSum[i + 1] + nums[i + 1];
    }
    
    for (int i = 0; i < nums.size(); ++i) {
      if (leftSum[i] == rightSum[i]) {
        return i;
      }
    }

    return -1;
  }
};
```


Solution for given an array of integers nums, calculate the pivot index of this array. The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right. If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array. Return the leftmost pivot index. If no such index exists, return -1.

Find Pivot Index

LeetCode Find Pivot Index Solution


# Find Smallest Letter Greater Than Target Problem & Solution

Given a characters array `letters` that is sorted in non-decreasing order and a character `target`, return the smallest character in the array that is larger than `target`.

Note that the letters wrap around.

For example, if `target == 'z'` and `letters == ['a', 'b']`, the answer is `'a'`.

See the [find smallest letter greater than target problem on LeetCode](https://leetcode.com/problems/find-smallest-letter-greater-than-target/).

## 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 nextGreatestLetter(vector<char>& letters, char target) {
    int low = 0;
    int high = letters.size() - 1;
    while (low < high) {
      int mid = low + (high - low) / 2;
      if (letters[mid] < target) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    
    if (letters[low] == target) {
      while (low < letters.size() && letters[low] == target) {
        ++low;
      }

      return letters[low < letters.size() ? low : 0];
    } else if (letters[low] > target) {
      return letters[low];
    } else {
      return letters[0];
    }
  }
};
```


Solution for given a characters array letters that is sorted in non-decreasing order and a character target, return the smallest character in the array that is larger than target. Note that the letters wrap around. For example, if target == 'z' and letters == ['a', 'b'], the answer is 'a'.

Find Smallest Letter Greater Than Target

LeetCode Find Smallest Letter Greater Than Target 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


# Flood Fill Problem & Solution

An image is represented by an `m` x `n` integer grid image where `image[i][j]` represents the pixel value of the image.

You are also given three integers `sr`, `sc`, and `newColor`.
You should perform a flood fill on the image starting from the pixel `image[sr][sc]`.

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on.
Replace the color of all of the aforementioned pixels with `newColor`.

Return the modified image after performing the flood fill.

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

## C++ Solution

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

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

class Solution {
public:
  vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
    
    // Must check if the color to be replaced is different than `newColor`; otherwise,
    // the algorithm goes into an infinite loop as we don't keep track of visited cells.
    int oldColor = image[sr][sc];
    if (oldColor != newColor) {
      floodFill(image, sr, sc, oldColor, newColor);
    }
    
    return image;
  }
  
private:
  void floodFill(vector<vector<int>>& image, int i, int j, int oldColor, int newColor) {
    image[i][j] = newColor;

    vector<int> x{0, 0, -1, +1};
    vector<int> y{-1, +1, 0, 0};

    assert(x.size() == y.size());
    for (int k = 0; k < x.size(); ++k) {
      int ix = i + x[k];
      int jy = j + y[k];

      if (ix >= 0 && ix < image.size() &&
          jy >= 0 && jy < image[ix].size() &&
          image[ix][jy] == oldColor) {
        floodFill(image, ix, jy, oldColor, newColor);
      }
    }
  }
};
```


Solution for an image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and newColor. You should perform a flood fill on the image starting from the pixel image[sr][sc]. To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with newColor. Return the modified image after performing the flood fill.

Flood Fill

LeetCode Flood Fill 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


# Image Smoother Problem & Solution

An image smoother is a filter of the size `3 x 3` that can be applied to each cell of an image by rounding down the average of the cell and the eight surrounding cells (i.e., the average of the nine cells in the blue smoother).
If one or more of the surrounding cells of a cell is not present, we do not consider it in the average (i.e., the average of the four cells in the red smoother).

Given an `m x n` integer matrix `img` representing the grayscale of an image, return the image after applying the smoother on each cell of it.

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

## 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<vector<int>> imageSmoother(vector<vector<int>>& img) {
    vector<int> x{0, -1, 1,  0, 0, -1, 1, -1,  1};
    vector<int> y{0,  0, 0, -1, 1, -1, 1,  1, -1};
    
    assert(x.size() == y.size());

    vector<vector<int>> result(img.size(), vector<int>(img[0].size(), 0));
    for (int i = 0; i < img.size(); ++i) {
      for (int j = 0; j < img[0].size(); ++j) {
        int sum = 0;
        int count = 0;

        for (int k = 0; k < x.size(); ++k) {
          int ii = i + x[k];
          int jj = j + y[k];
          if (ii >= 0 && ii < img.size() &&
              jj >= 0 && jj < img[0].size()) {
            sum += img[ii][jj];
            ++count;
          }
        }

        result[i][j] = sum / count;
      }
    }
    
    return result;
  }
};
```


Solution for an image smoother is a filter of the size 3 x 3 that can be applied to each cell of an image by rounding down the average of the cell and the eight surrounding cells (i.e., the average of the nine cells in the blue smoother). If one or more of the surrounding cells of a cell is not present, we do not consider it in the average (i.e., the average of the four cells in the red smoother). Given an m x n integer matrix img representing the grayscale of an image, return the image after applying the smoother on each cell of it.

Blog

LeetCode Problems and Solutions

Project Euler Problems and Solutions