---
title: 'Bloomberg'
tags: LeetCode
---
## Array
### 41. First Missing Positive
```cpp
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
const int n = nums.size();
// Correct slot:
// nums[i] = i + 1
// nums[i] - 1 = i
// nums[nums[i] - 1] = nums[i]
for (int i = 0; i < n; ++i)
while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1])
swap(nums[i], nums[nums[i] - 1]);
for (int i = 0; i < n; ++i)
if (nums[i] != i + 1)
return i + 1;
return n + 1;
}
};
```
## Stack
### 394. Decode String
```cpp
class Solution {
public:
string decodeString(string s) {
stack<pair<string, int>> stack;
string currStr;
int currNum = 0;
for (const char c : s) {
if (isdigit(c)) {
currNum = currNum * 10 + (c - '0');
} else {
if (c == '[') {
stack.emplace(currStr, currNum);
currStr = "";
currNum = 0;
} else if (c == ']') {
const auto [prevStr, n] = stack.top();
stack.pop();
currStr = prevStr + getRepeatedStr(currStr, n);
} else {
currStr += c;
}
}
}
return currStr;
}
private:
string getRepeatedStr(const string& str, int n) {
string s;
while (n--) {
s += str;
}
return s;
}
};
```
### 445. Add Two Numbers II
```cpp
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int carry = 0;
stack<ListNode*> stack1;
stack<ListNode*> stack2;
while (l1) {
stack1.push(l1);
l1 = l1->next;
}
// [7, 2, 4, 3]
while (l2) {
stack2.push(l2);
l2 = l2->next;
}
// [5, 6, 4]
ListNode* head = nullptr;
while (carry || !stack1.empty() || !stack2.empty()) {
if (!stack1.empty()) {
carry += stack1.top()->val;
stack1.pop();
}
if (!stack2.empty()) {
carry += stack2.top()->val;
stack2.pop();
}
ListNode* node = new ListNode(carry % 10);
node->next = head;
head = node;
carry /= 10;
}
return head;
}
};
```
### 1249. Minimum Remove to Make Valid Parentheses
```cpp
class Solution {
public:
string minRemoveToMakeValid(string s) {
stack<int> stack; // unpaired '(' indicies
for (int i = 0; i < s.length(); ++i)
if (s[i] == '(') {
stack.push(i); // record unpaired '(' index
} else if (s[i] == ')') {
if (stack.empty())
s[i] = '*'; // mark unpaired ')' as '*'
else
stack.pop(); // find a pair!
}
// mark unpaired '(' as '*'
while (!stack.empty())
s[stack.top()] = '*', stack.pop();
s.erase(remove(begin(s), end(s), '*'), end(s));
return s;
}
};
```
### 1209. Remove All Adjacent Duplicates in String II
```cpp
class Solution {
public:
string removeDuplicates(string s, int k) {
string ans;
vector<pair<char, int>> stack;
for (const char c : s) {
if (stack.empty() || stack.back().first != c) {
stack.emplace_back(c, 1);
} else if (++stack.back().second == k) {
stack.pop_back();
}
}
for (const auto& [c, count] : stack)
ans.append(count, c);
return ans;
}
};
```
## Linked List
### 1244. Design A Leaderboard
```cpp
class Leaderboard {
public:
void addScore(int playerId, int score) {
idToScore[playerId] += score;
}
int top(int K) {
int ans = 0;
priority_queue<int, vector<int>, greater<>> pq;
for (const auto& [id, score] : idToScore) {
pq.push(score);
if (pq.size() > K)
pq.pop();
}
while (!pq.empty())
ans += pq.top(), pq.pop();
return ans;
}
void reset(int playerId) {
idToScore.erase(playerId);
}
private:
unordered_map<int, int> idToScore;
};
```
### 1472. Design Browser History
#### Approach 1: Array
```cpp
class BrowserHistory {
public:
BrowserHistory(string homepage) {
visit(homepage);
}
void visit(string url) {
if (++index < urls.size()) {
urls[index] = url;
} else {
urls.push_back(url);
}
lastIndex = index;
}
string back(int steps) {
index = max(0, index - steps);
return urls[index];
}
string forward(int steps) {
index = min(lastIndex, index + steps);
return urls[index];
}
private:
vector<string> urls;
int index = -1;
int lastIndex = -1;
};
```
#### Approach 2: Stack
```cpp
class BrowserHistory {
public:
BrowserHistory(string homepage) {
visit(homepage);
}
void visit(string url) {
history.push(url);
future = stack<string>();
}
string back(int steps) {
while (steps-- > 0 && history.size() > 1)
future.push(history.top()), history.pop();
return history.top();
}
string forward(int steps) {
while (steps-- > 0 && !future.empty())
history.push(future.top()), future.pop();
return history.top();
}
private:
stack<string> history;
stack<string> future;
};
```
#### Approach 3: Doubly-Linked List
```cpp
struct Node {
Node(const string& url) : url(url) {}
Node* prev = nullptr;
Node* next = nullptr;
const string url;
};
class BrowserHistory {
public:
BrowserHistory(string homepage) {
curr = new Node(homepage);
}
void visit(string url) {
curr->next = new Node(url);
curr->next->prev = curr;
curr = curr->next;
}
string back(int steps) {
while (curr->prev && steps-- > 0)
curr = curr->prev;
return curr->url;
}
string forward(int steps) {
while (curr->next && steps-- > 0)
curr = curr->next;
return curr->url;
}
private:
Node* curr = nullptr;
};
```
## OOP
### 1396. Design Underground System
```cpp
struct CheckIn {
string stationName;
int time;
};
struct CheckOut {
int numTrips;
int totalTime;
};
class UndergroundSystem {
public:
void checkIn(int id, string stationName, int t) {
checkIns[id] = {stationName, t};
}
void checkOut(int id, string stationName, int t) {
const auto [startStation, startTime] = checkIns[id];
checkIns.erase(id);
const string& route = startStation + "->" + stationName;
++checkOuts[route].numTrips;
checkOuts[route].totalTime += t - startTime;
}
double getAverageTime(string startStation, string endStation) {
const auto& [numTrips, totalTime] =
checkOuts[startStation + "->" + endStation];
return totalTime / (double)numTrips;
}
private:
unordered_map<int, CheckIn> checkIns; // {id: (stationName, time)}
unordered_map<string, CheckOut> checkOuts; // {route: (numTrips, totalTime)}
};
```
## Tree
### 103. Binary Tree Zigzag Level Order Traversal
#### Approach 1: Deque
```cpp
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if (!root)
return {};
vector<vector<int>> ans;
deque<TreeNode*> q{{root}};
bool isLeftToRight = true;
while (!q.empty()) {
vector<int> currLevel;
for (int size = q.size(); size > 0; --size)
if (isLeftToRight) {
TreeNode* node = q.front();
q.pop_front();
currLevel.push_back(node->val);
if (node->left)
q.push_back(node->left);
if (node->right)
q.push_back(node->right);
} else {
TreeNode* node = q.back();
q.pop_back();
currLevel.push_back(node->val);
if (node->right)
q.push_front(node->right);
if (node->left)
q.push_front(node->left);
}
ans.push_back(currLevel);
isLeftToRight = !isLeftToRight;
}
return ans;
}
};
```
#### Approach 2: Queue
```cpp
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if (!root)
return {};
vector<vector<int>> ans;
queue<TreeNode*> q{{root}};
bool isLeftToRight = true;
while (!q.empty()) {
const int size = q.size();
vector<int> currLevel(size);
for (int i = 0; i < size; ++i) {
TreeNode* node = q.front();
q.pop();
const int index = isLeftToRight ? i : size - i - 1;
currLevel[index] = node->val;
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
ans.push_back(node);
isLeftToRight = !isLeftToRight;
}
return ans;
}
};
```
#### Approach 3: DFS
### 501. Find Mode in Binary Search Tree
```cpp
class Solution {
public:
vector<int> findMode(TreeNode* root) {
vector<int> ans;
int count = 0;
int maxCount = 0;
inorder(root, count, maxCount, ans);
return ans;
}
private:
TreeNode* pred = nullptr;
void inorder(TreeNode* root, int& count, int& maxCount, vector<int>& ans) {
if (!root)
return;
inorder(root->left, count, maxCount, ans);
updateCount(root, count, maxCount, ans);
inorder(root->right, count, maxCount, ans);
}
void updateCount(TreeNode* root, int& count, int& maxCount,
vector<int>& ans) {
if (pred && pred->val == root->val)
++count;
else
count = 1;
if (count > maxCount) {
maxCount = count;
ans = {root->val};
} else if (count == maxCount) {
ans.push_back(root->val);
}
pred = root;
}
};
```
### 98. Validate Binary Search Tree
#### Approach 1: Iterative
```cpp
class Solution {
public:
bool isValidBST(TreeNode* root) {
return isValidBST(root, nullptr, nullptr);
}
private:
bool isValidBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
if (!root)
return true;
if (minNode && root->val <= minNode->val)
return false;
if (maxNode && root->val >= maxNode->val)
return false;
return isValidBST(root->left, minNode, root) &&
isValidBST(root->right, root, maxNode);
}
};
```
#### Approach 2: Recursive (stack)
```cpp
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> stack;
TreeNode* pred = nullptr;
while (root || !stack.empty()) {
while (root) {
stack.push(root);
root = root->left;
}
root = stack.top(), stack.pop();
if (pred && pred->val >= root->val)
return false;
pred = root;
root = root->right;
}
return true;
}
};
```
### 104. Maximum Depth of Binary Tree
```cpp
class Solution {
public:
int maxDepth(TreeNode* root) {
if (!root)
return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
};
```
### 236. Lowest Common Ancestor of a Binary Tree
```cpp
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q)
return root;
TreeNode* l = lowestCommonAncestor(root->left, p, q);
TreeNode* r = lowestCommonAncestor(root->right, p, q);
if (l && r)
return root;
return l ? l : r;
}
};
```
### 987. Vertical Order Traversal of a Binary Tree
```cpp
class Solution {
public:
vector<vector<int>> verticalTraversal(TreeNode* root) {
vector<vector<int>> ans;
map<int, multiset<pair<int, int>>> xToSortedPairs; // {x: {(-y, val)}}
dfs(root, 0, 0, xToSortedPairs);
for (const auto& [_, pairs] : xToSortedPairs) {
vector<int> vals;
for (const auto& pair : pairs)
vals.push_back(pair.second);
ans.push_back(vals);
}
return ans;
}
private:
void dfs(TreeNode* root, int x, int y,
map<int, multiset<pair<int, int>>>& xToSortedPairs) {
if (!root)
return;
xToSortedPairs[x].emplace(y, root->val);
dfs(root->left, x - 1, y + 1, xToSortedPairs);
dfs(root->right, x + 1, y + 1, xToSortedPairs);
}
};
```
## Two Pointers
### 42. Trapping Rain Water
#### $O(n)$ space
```cpp
class Solution {
public:
int trap(vector<int>& height) {
const int n = height.size();
int ans = 0;
vector<int> l(n); // l[i] := max(height[0..i])
vector<int> r(n); // r[i] := max(height[i..n))
for (int i = 0; i < n; ++i)
l[i] = i == 0 ? height[i] : max(height[i], l[i - 1]);
for (int i = n - 1; i >= 0; --i)
r[i] = i == n - 1 ? height[i] : max(height[i], r[i + 1]);
for (int i = 0; i < n; ++i)
ans += min(l[i], r[i]) - height[i];
return ans;
}
};
```
#### $O(1)$ space
```cpp
class Solution {
public:
int trap(vector<int>& height) {
if (height.empty())
return 0;
int ans = 0;
int l = 0;
int r = height.size() - 1;
int maxL = height[l];
int maxR = height[r];
while (l < r)
if (maxL < maxR) {
ans += maxL - height[l];
maxL = max(maxL, height[++l]);
} else {
ans += maxR - height[r];
maxR = max(maxR, height[--r]);
}
return ans;
}
};
```
## DFS
### 797. All Paths From Source to Target
```cpp
class Solution {
public:
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<vector<int>> ans;
vector<int> path{0};
dfs(graph, 0, path, ans);
return ans;
}
private:
void dfs(const vector<vector<int>>& graph, int node, vector<int>& path,
vector<vector<int>>& ans) {
if (node == graph.size() - 1) {
ans.push_back(path);
return;
}
for (const int child : graph[node]) {
path.push_back(child);
dfs(graph, child, path, ans);
path.pop_back();
}
}
};
```
### 430. Flatten a Multilevel Doubly Linked List
#### Appraoch 1: Recursive
```cpp
class Solution {
public:
Node* flatten(Node* head, Node* rest = nullptr) {
if (!head)
return rest;
head->next = flatten(head->child, flatten(head->next, rest));
if (head->next)
head->next->prev = head;
head->child = nullptr;
return head;
}
};
```
#### Approach 2: Iterative
```cpp
class Solution {
public:
Node* flatten(Node* head) {
for (Node* curr = head; curr; curr = curr->next)
if (curr->child) {
Node* cachedNext = curr->next;
curr->next = curr->child;
curr->child->prev = curr;
curr->child = nullptr;
Node* tail = curr->next;
while (tail->next)
tail = tail->next;
tail->next = cachedNext;
if (cachedNext)
cachedNext->prev = tail;
}
return head;
}
};
```
### 1274. Number of Ships in a Rectangle
```cpp
/**
* // This is Sea's API interface.
* // You should not implement it, or speculate about its implementation
* class Sea {
* public:
* bool hasShips(vector<int> topRight, vector<int> bottomLeft);
* };
*/
class Solution {
public:
int countShips(Sea sea, vector<int> topRight, vector<int> bottomLeft) {
if (topRight[0] < bottomLeft[0] || topRight[1] < bottomLeft[1])
return 0;
if (!sea.hasShips(topRight, bottomLeft))
return 0;
// sea.hashShips(topRight, bottomLeft) == true
if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1])
return 1;
const int mx = (topRight[0] + bottomLeft[0]) / 2;
const int my = (topRight[1] + bottomLeft[1]) / 2;
int ans = 0;
// top right
ans += countShips(sea, topRight, {mx + 1, my + 1});
// bottom right
ans += countShips(sea, {topRight[0], my}, {mx + 1, bottomLeft[1]});
// top left
ans += countShips(sea, {mx, topRight[1]}, {bottomLeft[0], my + 1});
// bottom left
ans += countShips(sea, {mx, my}, bottomLeft);
return ans;
}
};
```
### 242. Valid Anagram
```cpp
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.length() != t.length())
return false;
vector<int> count(128);
for (const char c : s)
++count[c];
for (const char c : t)
if (--count[c] < 0)
return false;
return true;
}
};
```
## Map
### 1583. Count Unhappy Friends
## Heap
### 407. Trapping Rain Water II
```cpp
struct T {
T(int i, int j, int h) : i(i), j(j), h(h) {}
int i;
int j;
int h; // heightMap[i][j] or the height after filling water
};
class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
const int m = heightMap.size();
const int n = heightMap[0].size();
const vector<int> dirs{0, 1, 0, -1, 0};
int ans = 0;
auto compare = [](const T& a, const T& b) { return a.h > b.h; };
priority_queue<T, vector<T>, decltype(compare)> pq(compare);
vector<vector<bool>> seen(m, vector<bool>(n));
for (int i = 0; i < m; ++i) {
pq.emplace(i, 0, heightMap[i][0]);
pq.emplace(i, n - 1, heightMap[i][n - 1]);
seen[i][0] = true;
seen[i][n - 1] = true;
}
for (int j = 1; j < n - 1; ++j) {
pq.emplace(0, j, heightMap[0][j]);
pq.emplace(m - 1, j, heightMap[m - 1][j]);
seen[0][j] = true;
seen[m - 1][j] = true;
}
while (!pq.empty()) {
const auto [i, j, h] = pq.top();
pq.pop();
for (int k = 0; k < 4; ++k) {
const int x = i + dirs[k];
const int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (seen[x][y])
continue;
if (heightMap[x][y] < h) {
ans += h - heightMap[x][y];
pq.emplace(x, y, h); // fill the water on grid[x][y]
} else {
pq.emplace(x, y, heightMap[x][y]);
}
seen[x][y] = true;
}
}
return ans;
}
};
```
### 692. Top K Frequent Words
```cpp
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
const int n = words.size();
vector<string> ans;
vector<vector<string>> bucket(n + 1);
unordered_map<string, int> count;
for (const string& word : words)
++count[word];
for (const auto& [word, freq] : count)
bucket[freq].push_back(word);
for (int freq = n; freq > 0; --freq) {
sort(begin(bucket[freq]), end(bucket[freq]));
for (const string& word : bucket[freq]) {
ans.push_back(word);
if (ans.size() == k)
return ans;
}
}
throw;
}
};
```
### 1029. Two City Scheduling
How much money can we save if we fly a person to A vs. B? To minimize the total cost, we should fly the person with the maximum saving to A, and with the minimum - to B.
Example: [30, 100], [40, 90], [50, 50], [70, 50].
Savings: 70, 50, 0, -20.
Obviously, first person should fly to A, and the last - to B.
```cpp
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs) {
const int n = costs.size() / 2;
int ans = 0;
// How much money can we save if we fly a person to A instead of B?
// To save money, we should
// 1) fly the person with the max saving to A
// 2) fly the person with the min saving to B
sort(begin(costs), end(costs), [](const auto& a, const auto& b) {
// sort in descending order by the money saved
// if we fly a person to A instead of B
return a[1] - a[0] > b[1] - b[0];
});
for (int i = 0; i < n; ++i)
ans += costs[i][0] + costs[i + n][1];
return ans;
}
};
```
## DP
### 403. Frog Jump
```cpp
class Solution {
public:
bool canCross(vector<int>& stones) {
const int n = stones.size();
// dp[i][j] := true if a frog can jumps to stones[i] with j units
vector<vector<bool>> dp(n, vector<bool>(n + 1));
dp[0][1] = true;
for (int i = 1; i < n; ++i)
for (int j = 0; j < i; ++j) {
const int k = stones[i] - stones[j];
if (k <= n && dp[j][k]) {
dp[i][k - 1] = true;
dp[i][k] = true;
dp[i][k + 1] = true;
}
}
return any_of(begin(dp.back()), end(dp.back()),
[](bool val) { return val; });
}
};
```
### 45. Jump Game II
```cpp
class Solution {
public:
int jump(vector<int>& nums) {
int ans = 0;
int end = 0;
int farthest = 0;
for (int i = 0; i < nums.size() - 1; ++i) {
farthest = max(farthest, i + nums[i]);
if (farthest >= nums.size() - 1) {
++ans;
break;
}
if (i == end) {
++ans;
end = farthest;
}
}
return ans;
}
};
```
### 140. Word Break II
```cpp
class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet{begin(wordDict), end(wordDict)};
unordered_map<string, vector<string>> memo;
return wordBreak(s, wordSet, memo);
}
private:
vector<string> wordBreak(const string& s,
const unordered_set<string>& wordSet,
unordered_map<string, vector<string>>& memo) {
if (memo.count(s))
return memo[s];
vector<string> ans;
// 1 <= prefix.length() < s.length()
for (int i = 1; i < s.length(); ++i) {
const string& prefix = s.substr(0, i);
const string& suffix = s.substr(i);
if (wordSet.count(prefix))
for (const string& word : wordBreak(suffix, wordSet, memo))
ans.push_back(prefix + " " + word);
}
// contains whole string, so don't add any space
if (wordSet.count(s))
ans.push_back(s);
return memo[s] = ans;
}
};
```
### 322. Coin Change
```cpp
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
// dp[i] := fewest # of coins to make up i
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (const int coin : coins)
for (int i = coin; i <= amount; ++i)
dp[i] = min(dp[i], dp[i - coin] + 1);
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
};
```
### 964. Least Operators to Express Number
```cpp
class Solution {
public:
int leastOpsExpressTarget(int x, int target) {
return dfs(x, target);
}
private:
unordered_map<int, int> memo;
int dfs(int x, int target) {
if (memo.count(target))
return memo[target];
if (x > target)
return min(2 * target - 1, 2 * (x - target));
if (x == target)
return 0;
long prod = x;
int n = 0;
while (prod < target) {
prod *= x;
++n;
}
if (prod == target)
return memo[target] = n;
int ans = dfs(x, target - prod / x) + n;
if (prod < 2 * target)
ans = min(ans, dfs(x, prod - target) + n + 1);
return memo[target] = ans;
}
};
```
## Greedy
### 56. Merge Intervals
```cpp
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> ans;
sort(begin(intervals), end(intervals));
for (const auto& interval : intervals)
if (ans.empty() || ans.back()[1] < interval[0])
ans.push_back(interval);
else
ans.back()[1] = max(ans.back()[1], interval[1]);
return ans;
}
};
```
### 253. Meeting Rooms II
```cpp
class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
if (intervals.empty())
return 0;
// store end times of each room
priority_queue<int, vector<int>, greater<>> pq;
sort(begin(intervals), end(intervals));
for (const auto& interval : intervals) {
if (!pq.empty() && interval[0] >= pq.top())
pq.pop(); // no overlap, we can reuse the same room
pq.push(interval[1]);
}
return pq.size();
}
};
```
### 1583. Count Unhappy Friends
```cpp
class Solution {
public:
int unhappyFriends(int n, vector<vector<int>>& preferences,
vector<vector<int>>& pairs) {
int ans = 0;
vector<int> matches(n);
vector<unordered_map<int, int>> prefer(n);
for (const auto& pair : pairs) {
const int x = pair[0];
const int y = pair[1];
matches[x] = y;
matches[y] = x;
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < n - 1; ++j)
prefer[i][preferences[i][j]] = j;
for (int x = 0; x < n; ++x)
for (const auto& [u, _] : prefer[x]) {
const int y = matches[x];
const int v = matches[u];
if (prefer[x][u] < prefer[x][y] && prefer[u][x] < prefer[u][v]) {
++ans;
break;
}
}
return ans;
}
};
```
Sign in with Wallet
Connect another wallet