teleren/devto huggingface dataset:
2242. Leetcode Solution in CPP
Tags: cpp
Published: 2022-07-06 11:49:28

```
class Solution {
 public:
  int maximumScore(vector<int>& scores, vector<vector<int>>& edges) {
    int ans = -1;
    vector<set<pair<int, int>>> graph(scores.size());  // {(score, node)}

    for (const auto& e : edges) {
      const int u = e[0];
      const int v = e[1];
      graph[u].emplace(scores[v], v);
      graph[v].emplace(scores[u], u);
      if (graph[u].size() > 3)
        graph[u].erase(begin(graph[u]));
      if (graph[v].size() > 3)
        graph[v].erase(begin(graph[v]));
    }

    // target sequence: a - u - v - b
    // enumerate each edge (u, v), and find a (u's child) and b (v's child)
    // that's why we find the 3 children that have the highest scores because
    // one of the 3 children is guaranteed to be valid
    for (const auto& e : edges) {
      const int u = e[0];
      const int v = e[1];
      for (const auto& [scoreA, a] : graph[u])
        for (const auto& [scoreB, b] : graph[v])
          if (a != b && a != v && b != u)
            ans = max(ans, scoreA + scores[u] + scores[v] + scoreB);
    }

    return ans;
  }
};

```
#leetcode
#challenge
here is the link for the problem:
https://leetcode.com/problems/maximum-score-of-a-node-sequence/submissions/
Golang — Time utility functions you will always need
Tags: go, programming, time, functions
Published: 2022-07-06 11:48:35


**How to use timestamp and other utility functions?**

In this blog, we will discuss some of the utilities like adding days or finding differences between timestamps, etc. Which we many times come around but are not available at the library level. May this article will save some of your minutes!

- Add days to or subtract days from a given time
- Get day start time
- Get Day end time
- Check whether the given two days are the same or not
- Find a number of days between given timestamps
- Find a number of weekdays(Mon, Tue,…) between two dates
- Check if a given year is a leap year

For implementation details, visit [canopas blog](https://blog.canopas.com/golang-time-utility-functions-you-will-always-need-d7840d091468).
2203. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-06 11:43:30

```
class Solution {
 public:
  long long minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2,
                          int dest) {
    vector<vector<pair<int, int>>> graph1(n);
    vector<vector<pair<int, int>>> graph2(n);  // reversed(graph1)

    for (const auto& e : edges) {
      const int u = e[0];
      const int v = e[1];
      const int w = e[2];
      graph1[u].emplace_back(v, w);
      graph2[v].emplace_back(u, w);
    }

    const auto fromSrc1 = dijkstra(graph1, src1);
    const auto fromSrc2 = dijkstra(graph1, src2);
    const auto fromDest = dijkstra(graph2, dest);
    long ans = kMax;

    for (int i = 0; i < n; ++i) {
      if (fromSrc1[i] == kMax || fromSrc2[i] == kMax || fromDest[i] == kMax)
        continue;
      ans = min(ans, fromSrc1[i] + fromSrc2[i] + fromDest[i]);
    }

    return ans == kMax ? -1 : ans;
  }

 private:
  constexpr static long kMax = 1e10;

  vector<long> dijkstra(const vector<vector<pair<int, int>>>& graph, int src) {
    using P = pair<long, int>;
    priority_queue<P, vector<P>, greater<>> minHeap;  // (d, u)
    vector<long> dist(graph.size(), kMax);
    minHeap.emplace(0, src);
    while (!minHeap.empty()) {
      const auto [d, u] = minHeap.top();
      minHeap.pop();
      if (dist[u] != kMax)
        continue;
      dist[u] = d;
      for (const auto& [v, w] : graph[u])
        minHeap.emplace(d + w, v);
    }
    return dist;
  }
};

```
#leetcode
#challenge
here is the link for the problem:
https://leetcode.com/problems/minimum-weighted-subgraph-with-the-required-paths/
2172. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-06 11:40:45

```
class Solution {
 public:
  int maximumANDSum(vector<int>& nums, int numSlots) {
    const int n = 2 * numSlots;
    const int nSelected = 1 << n;
    // dp[i] := max value given mask representing the nums selected
    vector<int> dp(nSelected);

    nums.resize(n);

    for (int mask = 1; mask < nSelected; ++mask) {
      const int selected = __builtin_popcount(mask);
      const int slot = (selected + 1) / 2;  // (1, 2) -> 1, (3, 4) -> 2
      for (int i = 0; i < n; ++i)
        if (mask >> i & 1)  // assign nums[i] to `slot`-th slot
          dp[mask] = max(dp[mask], dp[mask ^ 1 << i] + (slot & nums[i]));
    }

    return dp.back();
  }
};

```

#leetcode
#challenge
here is the link for the problem:
https://leetcode.com/problems/maximum-and-sum-of-array/
2156. Leetcode Solution in CPP
Tags: cpp
Published: 2022-07-06 11:38:54

```
class Solution {
 public:
  string subStrHash(string s, int power, int modulo, int k, int hashValue) {
    long maxPower = 1;
    long hashed = 0;
    int bestLeft = -1;

    auto val = [](char c) -> int { return c - 'a' + 1; };

    for (int i = s.length() - 1; i >= 0; --i) {
      hashed = (hashed * power + val(s[i])) % modulo;
      if (i + k < s.length())
        hashed = (hashed - val(s[i + k]) * maxPower % modulo + modulo) % modulo;
      else
        maxPower = maxPower * power % modulo;
      if (hashed == hashValue)
        bestLeft = i;
    }

    return s.substr(bestLeft, k);
  }
};

```
#leetcode
#challenge
here is the link for the problem:
https://leetcode.com/problems/find-substring-with-given-hash-value/submissions/
2151. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-06 11:36:36

```

// Time: O(2^N * N^2)
// Space: O(1)
class Solution {
public:
    int maximumGood(vector<vector<int>>& A) {
        int N = A.size(), ans = 0;
        auto valid = [&](int m) {
            for (int i = 0; i < N; ++i) {
                if (m >> i & 1) { // person i is good
                    for (int j = 0; j < N; ++j) { // test if there is any contradiction in the statements from person i
                        int good = m >> j & 1; // whether person j is good
                        if ((A[i][j] == 0 && good) || (A[i][j] == 1 && !good)) return false;
                    }
                }
            }
            return true;
        };
        for (int m = 1; m < (1 << N); ++m) {
            if (valid(m)) ans = max(ans, __builtin_popcount(m));
        }
        return ans;
    }
};
```

#leetcode
#challenge
here is the link for the problem:
https://leetcode.com/problems/maximum-good-people-based-on-statements/submissions/
2136. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-06 11:35:07

```
struct Seed {
  int p;
  int g;
  Seed(int p, int g) : p(p), g(g) {}
};

class Solution {
 public:
  int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime) {
    int ans = 0;
    int time = 0;
    vector<Seed> seeds;

    for (int i = 0; i < plantTime.size(); ++i)
      seeds.emplace_back(plantTime[i], growTime[i]);

    sort(begin(seeds), end(seeds),
         [](const auto& a, const auto& b) { return a.g > b.g; });

    for (const auto& [p, g] : seeds) {
      time += p;
      ans = max(ans, time + g);
    }

    return ans;
  }
};

```
#leetcode
#challenge
here is the link for the problem:
https://leetcode.com/problems/earliest-possible-day-of-full-bloom/
2132. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-06 11:33:59

```
class Solution {
 public:
  bool possibleToStamp(vector<vector<int>>& grid, int stampHeight,
                       int stampWidth) {
    const int m = grid.size();
    const int n = grid[0].size();
    // A[i][j] := # of 1s in grid[0..i)[0..j)
    vector<vector<int>> A(m + 1, vector<int>(n + 1));
    // B[i][j] := # of ways to stamp the submatrix in [0..i)[0..j)
    vector<vector<int>> B(m + 1, vector<int>(n + 1));
    // fit[i][j] := true if the stamps can fit with right-bottom at (i, j)
    vector<vector<bool>> fit(m, vector<bool>(n));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        A[i + 1][j + 1] = A[i + 1][j] + A[i][j + 1] - A[i][j] + grid[i][j];
        if (i + 1 >= stampHeight && j + 1 >= stampWidth) {
          const int x = i - stampHeight + 1;
          const int y = j - stampWidth + 1;
          if (A[i + 1][j + 1] - A[x][j + 1] - A[i + 1][y] + A[x][y] == 0)
            fit[i][j] = true;
        }
      }

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        B[i + 1][j + 1] = B[i + 1][j] + B[i][j + 1] - B[i][j] + fit[i][j];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (!grid[i][j]) {
          const int x = min(i + stampHeight, m);
          const int y = min(j + stampWidth, n);
          if (B[x][y] - B[i][y] - B[x][j] + B[i][j] == 0)
            return false;
        }

    return true;
  }
};

```


#leetcode
#challenge
here is the link for the problem:
https://leetcode.com/problems/stamping-the-grid/
Save your users from notification overload
Published: 2022-07-06 11:11:20

Nobody wants to be spammed with notifications. Recently while working on social media app, I ran into that exact problem. Every time a user would get a follow, they would be notified with a simple: “@Username started following you”. Every single time. Of course, some users get hundreds and thousands of new followers every day, so the situation quickly became extremely annoying for them.

After some thought, I decided to create a solution that would group these notifications into one. The resulting code was supposed to let users know something along the lines of  "Username1, Username2, and other 7 followed you".

Managing all the moving parts of an app, such as this one, is not easy. So, we needed a scalable, long-term solution. Next came searching for a platform that would help automate the process. We needed a system that would help orchestrate the process and optimise this frequently occurring process. I stumbled across [Temporal.io. ](https://temporal.io)

The open source platform allows for a reliable and scalable function execution. Solutions built via Temporal are also durable, meaning there is no time limit. Whether my code was supposed to execute for seconds or years, the platform was supposed to help me make it run forever. And here’s how I did it:

- Here’s how developing the code for a single user follow went done:
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1veyr9xl5990p1xkk4u1.png)

- Next was implementing an activity that could execute a send notification code. Workflow code cannot use 3rd party API or have access to the file system. So we need to implement it in activities and to pass a client as a dependancy injection.
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tsvpr29j2v749yzi4yzi.png)

- Later I had to proxy activities in order to use them in a workflow:
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tva9f1lulcxykksdtb6j.png)

- A two hour period was picked for grouping notifications. Use a utility function from Temporal to make a time based condition: 
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jd06ar3uwqbav4zm5yg8.png)

- The next step includes adding a worker that will execute tasks from the queue:
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/aipubvjzbfhu74cftda8.png)

And here it is. We are ready to run the Temporal workflow.
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5z6hfjofpmkxxhjz4yxr.png)
2127. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-06 11:32:27

```
enum class State { INIT, VISITING, VISITED };

class Solution {
 public:
  int maximumInvitations(vector<int>& favorite) {
    const int n = favorite.size();
    int sumComponentsLength = 0;  // component: a -> b -> c <-> x <- y
    vector<vector<int>> graph(n);
    vector<int> inDegree(n);
    vector<int> maxChainLength(n, 1);
    queue<int> q;

    // build graph
    for (int i = 0; i < n; ++i) {
      graph[i].push_back(favorite[i]);
      ++inDegree[favorite[i]];
    }

    // topology
    for (int i = 0; i < n; ++i)
      if (inDegree[i] == 0)
        q.push(i);

    while (!q.empty()) {
      const int u = q.front();
      q.pop();
      for (const int v : graph[u]) {
        if (--inDegree[v] == 0)
          q.push(v);
        maxChainLength[v] = max(maxChainLength[v], 1 + maxChainLength[u]);
      }
    }

    for (int i = 0; i < n; ++i)
      if (favorite[favorite[i]] == i)
        // i <-> favorite[i] (cycle's length = 2)
        sumComponentsLength += maxChainLength[i] + maxChainLength[favorite[i]];

    int maxCycleLength = 0;  // cycle : a -> b -> c -> a
    vector<int> parent(n, -1);
    vector<bool> seen(n);
    vector<State> state(n);

    for (int i = 0; i < n; ++i)
      if (!seen[i])
        findCycle(graph, i, parent, seen, state, maxCycleLength);

    return max(sumComponentsLength / 2, maxCycleLength);
  }

 private:
  void findCycle(const vector<vector<int>>& graph, int u, vector<int>& parent,
                 vector<bool>& seen, vector<State>& state,
                 int& maxCycleLength) {
    seen[u] = true;
    state[u] = State::VISITING;

    for (const int v : graph[u]) {
      if (!seen[v]) {
        parent[v] = u;
        findCycle(graph, v, parent, seen, state, maxCycleLength);
      } else if (state[v] == State::VISITING) {
        // find the cycle's length
        int curr = u;
        int cycleLength = 1;
        while (curr != v) {
          curr = parent[curr];
          ++cycleLength;
        }
        maxCycleLength = max(maxCycleLength, cycleLength);
      }
    }

    state[u] = State::VISITED;
  }
};

```

#leetcode
#challenge
here is the link for the problem:
https://leetcode.com/problems/maximum-employees-to-be-invited-to-a-meeting/
2106. Leetcode Solution in CPP
Tags: cpp
Published: 2022-07-06 11:31:00

```
class Solution {
 public:
  int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
    const int maxRight = max(startPos, fruits.back()[0]);
    int ans = 0;
    vector<int> amounts(1 + maxRight);
    vector<int> prefix(2 + maxRight);

    for (const auto& f : fruits)
      amounts[f[0]] = f[1];

    partial_sum(begin(amounts), end(amounts), begin(prefix) + 1);

    auto getFruits = [&](int leftSteps, int rightSteps) {
      const int l = max(0, startPos - leftSteps);
      const int r = min(maxRight, startPos + rightSteps);
      return prefix[r + 1] - prefix[l];
    };

    // go right first
    const int maxRightSteps = min(maxRight - startPos, k);
    for (int rightSteps = 0; rightSteps <= maxRightSteps; ++rightSteps) {
      const int leftSteps = max(0, k - 2 * rightSteps);  // turn left
      ans = max(ans, getFruits(leftSteps, rightSteps));
    }

    // go left first
    const int maxLeftSteps = min(startPos, k);
    for (int leftSteps = 0; leftSteps <= maxLeftSteps; ++leftSteps) {
      const int rightSteps = max(0, k - 2 * leftSteps);  // turn right
      ans = max(ans, getFruits(leftSteps, rightSteps));
    }

    return ans;
  }
};

```

#leetcode
#challenge
here is the link for the problem:
https://leetcode.com/problems/maximum-fruits-harvested-after-at-most-k-steps/
2065. Leetcode Solution in CPP
Tags: cpp
Published: 2022-07-06 11:29:35

```
class Solution {
 public:
  int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges,
                         int maxTime) {
    const int n = values.size();
    int ans = 0;
    vector<vector<pair<int, int>>> graph(n);
    vector<int> seen(n);
    seen[0] = 1;

    for (const auto& e : edges) {
      const int u = e[0];
      const int v = e[1];
      const int time = e[2];
      graph[u].emplace_back(v, time);
      graph[v].emplace_back(u, time);
    }

    dfs(graph, values, 0, values[0], maxTime, seen, ans);
    return ans;
  }

 private:
  void dfs(const vector<vector<pair<int, int>>>& graph,
           const vector<int>& values, int u, int quality, int remainingTime,
           vector<int>& seen, int& ans) {
    if (u == 0)
      ans = max(ans, quality);
    for (const auto& [v, time] : graph[u]) {
      if (time > remainingTime)
        continue;
      const int newQuality = quality + values[v] * (seen[v] == 0);
      ++seen[v];
      dfs(graph, values, v, newQuality, remainingTime - time, seen, ans);
      --seen[v];
    }
  }
};

```

#leetcode
#challenge
here is the link for the problem:
https://leetcode.com/problems/maximum-path-quality-of-a-graph/submissions/
2060. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-06 11:27:09

```
class Solution {
 public:
  bool possiblyEquals(string s1, string s2) {
    dp.resize(s1.length() + 1,
              vector<unordered_map<int, bool>>(s2.length() + 1));
    return f(s1, s2, 0, 0, 0);
  }

 private:
  vector<vector<unordered_map<int, bool>>> dp;

  bool f(const string& s1, const string& s2, int i, int j, int paddingDiff) {
    // Return true if s1[i:] matches s2[j:] with given padding difference
    // i := s1's index
    // j := s2's index
    // paddingDiff := signed padding, if positive, s1 has a positive number of
    //                offset bytes relative to s2
    if (dp[i][j].count(paddingDiff))
      return dp[i][j][paddingDiff];
    if (i == s1.length() && j == s2.length())
      return paddingDiff == 0;
    if (i < s1.length() && isdigit(s1[i])) {
      // add padding on s1
      const int nextLetterIndex = getNextLetterIndex(s1, i);
      for (const int num : getNums(s1.substr(i, nextLetterIndex - i)))
        if (f(s1, s2, nextLetterIndex, j, paddingDiff + num))
          return true;
    } else if (j < s2.length() && isdigit(s2[j])) {
      // add padding on s2
      const int nextLetterIndex = getNextLetterIndex(s2, j);
      for (const int num : getNums(s2.substr(j, nextLetterIndex - j)))
        if (f(s1, s2, i, nextLetterIndex, paddingDiff - num))
          return true;
    } else if (paddingDiff > 0) {
      // s1 has more padding, j needs to catch up
      if (j < s2.length())
        return f(s1, s2, i, j + 1, paddingDiff - 1);
    } else if (paddingDiff < 0) {
      // s2 has more padding, i needs to catch up
      if (i < s1.length())
        return f(s1, s2, i + 1, j, paddingDiff + 1);
    } else {  // paddingDiff == 0
      // no padding difference, consue the next letter
      if (i < s1.length() && j < s2.length() && s1[i] == s2[j])
        return f(s1, s2, i + 1, j + 1, 0);
    }
    return dp[i][j][paddingDiff] = false;
  }

  int getNextLetterIndex(const string& s, int i) {
    int j = i;
    while (i < s.length() && isdigit(s[j]))
      ++j;
    return j;
  }

  vector<int> getNums(const string& s) {
    vector<int> nums{stoi(s)};
    if (s.length() == 2) {
      nums.push_back(stoi(s.substr(0, 1)) + stoi(s.substr(1, 1)));
    } else if (s.length() == 3) {
      nums.push_back(stoi(s.substr(0, 1)) + stoi(s.substr(1, 2)));
      nums.push_back(stoi(s.substr(0, 2)) + stoi(s.substr(2, 1)));
      nums.push_back(stoi(s.substr(0, 1)) + stoi(s.substr(1, 1)) +
                     stoi(s.substr(2, 1)));
    }
    return nums;
  }
};

```


#leetcode
#challenge
here is the link for the problem:
https://leetcode.com/problems/check-if-an-original-string-exists-given-two-encoded-strings/
2056. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-06 11:25:29

```
class Solution {
 public:
  int countCombinations(vector<string>& pieces,
                        vector<vector<int>>& positions) {
    const int n = pieces.size();
    unordered_set<unsigned long long> ans;
    vector<vector<pair<int, int>>> combMoves;
    vector<pair<int, int>> board;

    getCombMoves(pieces, 0, {}, combMoves);

    for (const auto& pos : positions)
      board.emplace_back(pos[0], pos[1]);

    for (const auto& combMove : combMoves)
      dfs(board, n, combMove, (1 << n) - 1, ans);

    return ans.size();
  }

 private:
  const unordered_map<string, vector<pair<int, int>>> moves{
      {"rook", {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}},
      {"bishop", {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}},
      {"queen",
       {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}}};

  void getCombMoves(const vector<string>& pieces, int ithPiece,
                    vector<pair<int, int>>&& path,
                    vector<vector<pair<int, int>>>& combMoves) {
    if (ithPiece == pieces.size()) {
      combMoves.push_back(path);
      return;
    }

    for (const auto& move : moves.at(pieces[ithPiece])) {
      path.push_back(move);
      getCombMoves(pieces, ithPiece + 1, std::move(path), combMoves);
      path.pop_back();
    }
  }

  void dfs(const vector<pair<int, int>>& board, int n,
           const vector<pair<int, int>>& combMove, int activeMask,
           unordered_set<unsigned long long>& ans) {
    if (activeMask == 0)
      return;
    ans.insert(hash(board));

    for (int nextActiveMask = 1; nextActiveMask < 1 << n; ++nextActiveMask) {
      if ((activeMask & nextActiveMask) != nextActiveMask)
        continue;

      // make sure to copy the board
      auto nextBoard(board);

      // move pieces that are active in this turn
      for (int i = 0; i < n; ++i)
        if ((nextActiveMask >> i) & 1) {
          nextBoard[i].first += combMove[i].first;
          nextBoard[i].second += combMove[i].second;
        }

      // check no two or more pieces occupy the same square
      if (getUniqueSize(nextBoard) < n)
        continue;

      // check if all in boundary
      if (all_of(begin(nextBoard), end(nextBoard), [](const auto& piece) {
            const int x = piece.first;
            const int y = piece.second;
            return 1 <= x && x <= 8 && 1 <= y && y <= 8;
          }))
        dfs(nextBoard, n, combMove, nextActiveMask, ans);
    }
  }

  unsigned long long hash(const vector<pair<int, int>>& board) {
    unsigned long long hashed;
    for (const auto& [x, y] : board)
      hashed = (hashed * 64) + (x - 1 << 3) + (y - 1);
    return hashed;
  }

  int getUniqueSize(const vector<pair<int, int>>& board) {
    unordered_set<int> unique;
    for (const auto& [x, y] : board)
      unique.insert(x * 8 + y);
    return unique.size();
  }
};

```
#leetcode
#challenge
here is the link for the problem:
https://leetcode.com/problems/number-of-valid-move-combinations-on-chessboard/
2050. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-06 11:24:01

```
class Solution {
 public:
  int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
    vector<vector<int>> graph(n);
    vector<int> inDegree(n);
    queue<int> q;
    vector<int> dist(time);

    // build graph
    for (const auto& r : relations) {
      const int u = r[0] - 1;
      const int v = r[1] - 1;
      graph[u].push_back(v);
      ++inDegree[v];
    }

    // topology
    for (int i = 0; i < n; ++i)
      if (inDegree[i] == 0)
        q.push(i);

    while (!q.empty()) {
      const int u = q.front();
      q.pop();
      for (const int v : graph[u]) {
        dist[v] = max(dist[v], dist[u] + time[v]);
        if (--inDegree[v] == 0)
          q.push(v);
      }
    }

    return *max_element(begin(dist), end(dist));
  }
};

```
#leetcode
#challenge
here is the link for the problem:
https://leetcode.com/problems/parallel-courses-iii/