---
# System prepended metadata

title: Bloomberg
tags: [LeetCode]

---

---
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;
  }
};
```
