Competitive Programming

Leet Code Daily 2024-08-10

* [Description](https://leetcode.com/problems/regions-cut-by-slashes) ## Solution Disjoint sets. ## Code ```c++const int kTop = 0, kLeft = 1, kRight = 2, kBottom = 3; class Solution {

2024-08-10 · 2 min

Leet Code Daily 2024-08-09

* [Description](https://leetcode.com/problems/magic-squares-in-grid/) ## Code ```c++const vector<int> kAllowedVals = {    1, 2, 3, 4, 5, 6, 7, 8, 9,}; class Solution {public:    int numMagicSquaresInside(vector<vector<int>>& grid) {

2024-08-09 · 2 min

Leet Code Daily 2024-08-08

* [Description](https://leetcode.com/problems/spiral-matrix-iii/) ## Code ```c++const vector<pair<int, int>> kDir = {    {0, +1},    {+1, 0},    {0, -1},    {-1, 0},};

2024-08-08 · 1 min

Leet Code Daily 2024-08-07

## Solution Simulation. ## Code ```c++constexpr int kBillion = 1E9;constexpr int kMillion = 1E6;constexpr int kThousand = 1E3;constexpr int kHundred = 1E2;constexpr int kTwenty = 2E1;

2024-08-07 · 2 min

Leet Code Daily 2024-08-06

* [Description](https://leetcode.com/problems/minimum-number-of-pushes-to-type-word-ii/) ## Code ```c++class Solution {public:    int minimumPushes(string word) {        vector<int> freq(26, 0);        for (const auto& c : word) {            freq[c - 'a']++;        }

2024-08-06 · 1 min

Leet Code Daily 2024-08-05

* [Description](https://leetcode.com/problems/kth-distinct-string-in-an-array/) ## Code ```c++class Solution {public:    string kthDistinct(vector<string>& arr, int k) {        unordered_map<string, int> cnt;        for (const auto& a : arr) {            cnt[a]++;        }

2024-08-05 · 1 min

Leet Code Daily 2024-08-04

* [Description](https://leetcode.com/problems/range-sum-of-sorted-subarray-sums) ## Code ```c++constexpr int kMod = 1E9 + 7; class Solution {public:    int rangeSum(vector<int>& nums, int n, int left, int right) {        vector<int> sums;        for (int i = 0; i < n; i++) {

2024-08-04 · 1 min

Leet Code Daily 2024-08-03

* [Description](https://leetcode.com/problems/make-two-arrays-equal-by-reversing-subarrays/) ## Code ```c++class Solution {public:    bool canBeEqual(vector<int>& target, vector<int>& arr) {        sort(target.begin(), target.end());        sort(arr.begin(), arr.end());        for (int i = 0; i < target.size(); i++) {            if (target[i] != arr[i]) {

2024-08-03 · 1 min

Leet Code Daily 2024-08-02

* [Description](https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together-ii/) ## Code ```c++class Solution {public:    int minSwaps(vector<int>& nums) {         int num_ones = 0;        for (const auto& x : nums) {            num_ones += (x == 1);

2024-08-02 · 1 min

Leet Code Daily 2024-08-01

* [Description](https://leetcode.com/problems/number-of-senior-citizens/) ## Code ```c++class Solution {public:    int countSeniors(vector<string>& details) {        int ret = 0;        for (const auto& detail : details) {            if ((detail[11] == '6' && detail[12] >= '1') ||                (detail[11] >= '7')) {

2024-08-01 · 1 min

Leet Code Daily 2024-07-31

* [Description](https://leetcode.com/problems/filling-bookcase-shelves/) ## Solution **DP**. ## Code ```c++class Solution {public:    int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {

2024-07-31 · 1 min

Leet Code Daily 2024-07-30

* [Description](https://leetcode.com/problems/minimum-deletions-to-make-string-balanced/) ## Code ```c++class Solution {public:    int minimumDeletions(string s) {         int CBL = 0, CAR = 0;        for (const auto& c : s) {            if (c == 'a') {

2024-07-30 · 1 min

Leet Code Daily 2024-07-29

* [Description](https://leetcode.com/problems/count-number-of-teams/) ## Solution * Binary search. ## Code ```c++class Solution {public:    int numTeams(vector<int>& rating) {

2024-07-29 · 1 min

Leet Code Daily 2024-07-28

* [Description](https://leetcode.com/problems/second-minimum-time-to-reach-destination/) ## Code ```c++constexpr int kVeryLong = 100000000; class Solution {public:    int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {         auto neighborhood = vector<vector<int>>(n);

2024-07-28 · 1 min

Leet Code Daily 2024-07-27

* [Description](https://leetcode.com/problems/minimum-cost-to-convert-string-i/) ## Solution Floyd-Warshall Algorithm. ## Code ```c++constexpr int kFarAway = 2600000; class Solution {

2024-07-27 · 1 min

Leet Code Daily 2024-07-26

* [Description](https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance) ## Solution Floyd-Warshall Algorithm. ## Code ```c++constexpr int kFarAway = 1000000; class Solution {

2024-07-27 · 1 min

Leet Code Daily 2024-07-25

* [Description](https://leetcode.com/problems/sort-an-array/) ## Code ```c++constexpr int kNumMin = -50000;constexpr int kNumMax = +50000; class Solution {public:    vector<int> sortArray(vector<int>& nums) {        vector<int> freq(kNumMax - kNumMin + 1, 0);

2024-07-25 · 1 min

Leet Code Daily 2024-07-24

* [Description](https://leetcode.com/problems/sort-the-jumbled-numbers/) ## Code ```c++class Solution {public:    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {        auto mapped_val = [&](int x) {            int ret = 0;            for (const auto& c : to_string(x)) {                ret = 10 * ret + mapping[c - '0'];

2024-07-24 · 1 min

Leet Code Daily 2024-07-23

* [Description](https://leetcode.com/problems/sort-array-by-increasing-frequency/) ## Code ```c++class Solution {public:    vector<int> frequencySort(vector<int>& nums) {        unordered_map<int, int> freq;        for (const auto& num : nums) {            freq[num]++;        }

2024-07-23 · 1 min

Leet Code Daily 2024-07-22

* [Description](https://leetcode.com/problems/sort-the-people/) ## Code ```c++class Solution {public:    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {        const int n = names.size();         vector<shared_ptr<pair<string, int>>> people;        for (int i = 0; i < n; i++) {

2024-07-22 · 1 min

Leet Code Daily 2024-07-21

* [Description](https://leetcode.com/problems/build-a-matrix-with-conditions) ## Solution Topological Sort. ## Code ```c++class Solution {public:    pair<bool, shared_ptr<vector<int>>> tsort(int k,

2024-07-21 · 1 min

Leet Code Daily 2024-07-20

* [Description](https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/) ## Code ```c++class Solution {public:    vector<vector<int>> restoreMatrix(vector<int>& rowSum,                                      vector<int>& colSum) {        const int n = rowSum.size(), m = colSum.size();        auto ret = vector<vector<int>>(n, vector<int>(m, 0));        for (int i = 0; i < n; i++) {

2024-07-20 · 1 min

Leet Code Daily 2024-07-19

* [Description](https://leetcode.com/problems/lucky-numbers-in-a-matrix/) ## Code ```c++class Solution {public:    vector<int> luckyNumbers(vector<vector<int>>& matrix) {        const int n = matrix.size(), m = matrix.front().size();        auto min_per_row = vector<int>(n, numeric_limits<int>::max());        auto max_per_col = vector<int>(m, numeric_limits<int>::min());        for (int i = 0; i < n; i++) {

2024-07-19 · 1 min

Leet Code Daily 2024-07-18

* [Description](https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/) ## Code ```c++/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

2024-07-18 · 1 min

Leet Code Daily 2024-07-17

* [Description](https://leetcode.com/problems/delete-nodes-and-return-forest/description/) ## Code ```c++/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

2024-07-17 · 2 min

Leet Code Daily 2024-07-16

* [Description](https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/) ## Code ```c++/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

2024-07-16 · 2 min

Leet Code Daily 2024-07-15

* [Description](https://leetcode.com/problems/create-binary-tree-from-descriptions/) ## Code ```c++/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

2024-07-15 · 1 min

Leet Code Daily 2024-07-14

* [Description](https://leetcode.com/problems/number-of-atoms/) ## Solution **Stack**. ## Code ```c++class Formula { public:

2024-07-14 · 2 min

Leet Code Daily 2024-07-13

* [Description](https://leetcode.com/problems/robot-collisions/) ## Solution **Sort** & **Stack**. ## Code ```c++struct robot {    int position;    int health;

2024-07-13 · 1 min

Leet Code Daily 2024-07-12

* [Description](https://leetcode.com/problems/maximum-score-from-removing-substrings) ## Solution * **Greedy** + **Stack**. ## Code ```c++class Solution {public:    int maximumGain(string s, int x, int y) {

2024-07-12 · 1 min

Leet Code Daily 2024-07-11

* [Description](https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/) ## Solution **Stack** + **Tree Traversial**. ## Code ```c++enum class NodeType {    kOpen = 0,    kChar = 1,

2024-07-11 · 1 min

Leet Code Daily 2024-07-10

* [Description](https://leetcode.com/problems/crawler-log-folder/) ## Code ```c++class Solution {public:    int minOperations(vector<string>& logs) {        int ans = 0;        for (const auto& log : logs) {            if (log[0] != '.') {                ans++;

2024-07-10 · 1 min

Leet Code Daily 2024-07-09

* [Description](https://leetcode.com/problems/average-waiting-time/) ## Code ```c++class Solution {public:    double averageWaitingTime(vector<vector<int>>& customers) {        double total_wait_time = 0;        int last_idle_time = INT_MIN;        for (const auto& customer : customers) {            last_idle_time = max(last_idle_time, customer[0]) + customer[1];

2024-07-09 · 1 min

Leet Code Daily 2024-07-08

* [Description](https://leetcode.com/problems/find-the-winner-of-the-circular-game/) ## Code ```c++class Solution {public:    int findTheWinner(int n, int k) {         vector<int> friends;        for (int i = 1; i <= n; i++) {            friends.push_back(i);

2024-07-08 · 1 min

Leet Code Daily 2024-07-07

* [Description](https://leetcode.com/problems/water-bottles/) ## Code ```c++class Solution {public:    int numWaterBottles(int numBottles, int numExchange) {        int ans = numBottles;        while (numBottles >= numExchange) {            int t = numBottles / numExchange;            ans += t;

2024-07-07 · 1 min

Leet Code Daily 2024-07-06

* [Description](https://leetcode.com/problems/pass-the-pillow/) ## Code ```c++class Solution {public:    int passThePillow(int n, int time) {        int p = time / (n - 1), q = time % (n - 1);        return p % 2 == 0 ? (1 + q) : (n - q);    }};

2024-07-06 · 1 min

Leet Code Daily 2024-07-05

* [description](https://leetcode.com/problems/find-the-minimum-and-maximum-number-of-nodes-between-critical-points/) ## Code ```c++/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode() : val(0), next(nullptr) {} *     ListNode(int x) : val(x), next(nullptr) {}

2024-07-05 · 1 min

Leet Code Daily 2024-07-04

* [Description](https://leetcode.com/problems/merge-nodes-in-between-zeros) ## Code ```c++/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode() : val(0), next(nullptr) {} *     ListNode(int x) : val(x), next(nullptr) {}

2024-07-04 · 1 min

Leet Code Daily 2024-07-03

* [Description](https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/) ## Code ```c++class Solution {public:    int minDifference(vector<int>& nums) {        sort(nums.begin(), nums.end());        int n = nums.size(), ans = INT_MAX;        for (int i = 0; i < 4 && i < n; i++) {            ans = min(ans, nums[max(n + i - 4, i)] - nums[i]);

2024-07-03 · 1 min

Leet Code Daily 2024-07-02

* [Description](https://leetcode.com/problems/intersection-of-two-arrays-ii/) ## Code ```c++class Solution {public:    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {        sort(nums1.begin(), nums1.end());        sort(nums2.begin(), nums2.end());        vector<int> ret;        for (int i = 0, j = 0; i < nums1.size() && j < nums2.size();) {

2024-07-02 · 1 min

Leet Code Daily 2024-07-01

* [Description](https://leetcode.com/problems/three-consecutive-odds) ## Code ```c++class Solution {public:    bool threeConsecutiveOdds(vector<int>& arr) {        for (int i = 1; i + 1 < arr.size(); i++) {            if (arr[i - 1] % 2 == 1 && arr[i] % 2 == 1 && arr[i + 1] % 2 == 1) {                return true;            }

2024-07-01 · 1 min

Leet Code Daily 2024-06-30

* [Description](https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/) ## Solution **Greedy + Disjoint Sets** ## Code ```c++class Solution {public:    int find(vector<int>& parent, int x) {

2024-06-30 · 2 min

Leet Code Daily 2024-06-29

* [Description](https://leetcode.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph) ## Code ```c++class Solution {public:    void compute(int x, unordered_map<int, set<int>>& ancestors,                 unordered_map<int, set<int>>& parent) {        if (ancestors.find(x) == ancestors.end()) {            for (const auto y : parent[x]) {                compute(y, ancestors, parent);

2024-06-29 · 1 min

Leet Code Daily 2024-06-28

* [Description](https://leetcode.com/problems/maximum-total-importance-of-roads/) ## Solution **Greedy**. The total importance of all roads is: $$\sum_{i \in \text{nodes}} \text{value}_i \times \text{degree}_i$$

2024-06-28 · 1 min

Leet Code Daily 2024-06-27

* [Description](https://leetcode.com/problems/find-center-of-star-graph/) ## Code ```c++class Solution {public:    int findCenter(vector<vector<int>>& edges) {        unordered_set<int> nodes_with_edge;        for (const auto& edge : edges) {            for (const auto& node : edge) {                if (nodes_with_edge.contains(node)) {

2024-06-27 · 1 min

Leet Code Daily 2024-06-26

* [Description](https://leetcode.com/problems/balance-a-binary-search-tree) ## Code ```c++/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

2024-06-26 · 1 min

Leet Code Daily 2024-06-25

* [Description](https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree) ## Solution BFS ## Code ```c++/** * Definition for a binary tree node. * struct TreeNode {

2024-06-25 · 1 min

Leet Code Daily 2024-06-24

* [Description](https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/) ## Solution Greedy, always flip from the first 0 bit. ## Code ```c++class Solution {public:    int minKBitFlips(vector<int>& nums, int k) {

2024-06-24 · 1 min

Leet Code Daily 2024-06-23

* [Description](https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit) ## Code ```c++class Solution {public:    int longestSubarray(vector<int>& nums, int limit) {        int n = nums.size(), ans = 0;        multiset<int> s;        for (int i = 0, j = 0; j < n; j++) {            s.insert(nums[j]);

2024-06-23 · 1 min

Leet Code Daily 2024-06-22

* [Description](https://leetcode.com/problems/count-number-of-nice-subarrays) ## Solution Preffix sum. ## Code ```c++class Solution {public:    int numberOfSubarrays(vector<int>& nums, int k) {

2024-06-22 · 1 min

Leet Code Daily 2024-06-21

* [Description]() ## Solution * Sliding window. ## Code ```c++class Solution {public:    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {

2024-06-21 · 1 min

Leet Code Daily 2024-06-20

* [Description](https://leetcode.com/problems/magnetic-force-between-two-balls) ## Solution Binary search. ## Code ```c++class Solution {public:    // Given `position` sorted in increasing order and `min_dis`,

2024-06-20 · 1 min

Leet Code Daily 2024-06-19

* [Description](https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets) ## Solution Binary search. ## Code ```c++class Solution {public:    int cntBouquets(vector<int>& bloomDay, int day, int k) {

2024-06-19 · 1 min

Leet Code Daily 2024-06-18

* [Description](https://leetcode.com/problems/most-profit-assigning-work) ## Solution * Given each worker is independent, we can see this as RMQ problem and each worker represents one query.* Or we can just sort. ## Code ```c++class Solution {public:

2024-06-18 · 1 min

Leet Code Daily 2024-06-17

* [Description](https://leetcode.com/problems/sum-of-square-numbers) ## Code ```c++class Solution {public:    bool judgeSquareSum(int c) {        for (int a = 0; a <= sqrt(c); a++) {            int b = sqrt(c - a * a);            if (a * a + b * b == c) {                return true;

2024-06-17 · 1 min

Leet Code Daily 2024-06-16

* [Description](https://leetcode.com/problems/patching-array) ## Solution Assuming we have completed range `[1, x]` and the next given but not used number is `y`, * If `y <= x + 1`, then we just use $y$ and expand the range to `[1, x + y]`.* Otherwise, we must patch a new number `x + 1`, and the new range would be `[1, x + x + 1]`. ## Code ```c++

2024-06-16 · 1 min

Leet Code Daily 2024-06-15

* [Description](https://leetcode.com/problems/ipo) ## Solution **Greedy**, always take current available project with maximum profit. ## Code ```c++class Solution {public:    int findMaximizedCapital(int k, int w, vector<int>& profits,

2024-06-15 · 1 min

Leet Code Daily 2024-06-14

* [Description](https://leetcode.com/problems/minimum-increment-to-make-array-unique) ## Code ```c++class Solution {public:    int minIncrementForUnique(vector<int>& nums) {        sort(nums.begin(), nums.end());        int ans = 0;        for (int i = 1; i < nums.size(); i++) {            int diff = max(nums[i - 1] + 1, nums[i]) - nums[i];

2024-06-14 · 1 min

Leet Code Daily 2024-06-13

* [Description](https://leetcode.com/problems/minimum-number-of-moves-to-seat-everyone) ## Code ```c++class Solution {public:    int minMovesToSeat(vector<int>& seats, vector<int>& students) {        sort(seats.begin(), seats.end());        sort(students.begin(), students.end());        int ans = 0, n = seats.size();        for (int i = 0; i < n; i++) {

2024-06-13 · 1 min

Leet Code Daily 2024-06-12

* [Description](https://leetcode.com/problems/sort-colors) ## Code ```c++class Solution {public:    void sortColors(vector<int>& nums) {        int cnt[3] = {0};        for (const auto& x : nums) {            cnt[x]++;        }

2024-06-12 · 1 min

Leet Code Daily 2024-06-11

* [Description](https://leetcode.com/problems/relative-sort-array) ## Code ```c++class Solution {public:    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {        map<int, int> freq;        for (const auto& x : arr1) {            freq[x]++;        }

2024-06-11 · 1 min

Leet Code Daily 2024-06-10

* [Description](https://leetcode.com/problems/height-checker) ## Solution ```c++class Solution {public:    int heightChecker(vector<int>& heights) {        vector<int> expected(heights.begin(), heights.end());        sort(expected.begin(), expected.end());        int ans = 0;        for (int i = 0; i < heights.size(); i++) {

2024-06-10 · 1 min

Leet Code Daily 2024-06-09

* [Description](https://leetcode.com/problems/subarray-sums-divisible-by-k) ## Code ```c++class Solution {public:    int subarraysDivByK(vector<int>& nums, int k) {        unordered_map<int, int> cnt;        cnt[0] = 1;        int sum = 0, ans = 0;        for (const auto& x : nums) {

2024-06-09 · 1 min

Leet Code Daily 2024-06-08

## Solution **Preffix sum** & **hash**. ## Code ```c++class Solution {public:    bool checkSubarraySum(vector<int>& nums, int k) {        vector<int> sums = {0};        for (const auto& x : nums) {

2024-06-08 · 1 min

Leet Code Daily 2024-06-07

* [Description](https://leetcode.com/problems/replace-words) ## Solution **Trie** ## Code ```c++constexpr int kMaxChars = 26; typedef struct trie trie;

2024-06-07 · 1 min

Leet Code Daily 2024-06-06

* [Description](https://leetcode.com/problems/hand-of-straights) ## Code ```c++class Solution {public:    bool isNStraightHand(vector<int>& hand, int groupSize) {        unordered_map<int, int> cnt_unused;        for (const auto& val : hand) {            cnt_unused[val]++;        }

2024-06-06 · 1 min

Leet Code Daily 2024-06-05

* [Description](https://leetcode.com/problems/find-common-characters/description) ## Code ```c++class Solution {public:    vector<string> commonChars(vector<string>& words) {        unordered_map<char, int> min_cnt;        for (char c = 'a'; c <= 'z'; c++) {            min_cnt[c] = INT_MAX;        }

2024-06-05 · 1 min

Leet Code Daily 2024-06-04

* [Description](https://leetcode.com/problems/longest-palindrome/) ## Code ```c++class Solution {public:    int longestPalindrome(string s) {        unordered_map<char, int> cnt_chars;        for (const auto& c : s) {            cnt_chars[c]++;        }

2024-06-04 · 1 min

Leet Code Daily 2024-06-03

* [Description](https://leetcode.com/problems/append-characters-to-string-to-make-subsequence) ## Code ```c++constexpr int kMaxSize = 100001;constexpr int kNumChars = 26; class Solution {public:    int appendCharacters(string s, string t) {        int n = s.size(), m = t.size();

2024-06-03 · 1 min

Leet Code Daily 2024-06-02

* [Description](https://leetcode.com/problems/reverse-string) ## Code ```c++class Solution {public:    void reverseString(vector<char>& s) {        for (int i = 0, j = s.size() - 1; i < j;) {            swap(s[i++], s[j--]);        }    }

2024-06-03 · 1 min

Leet Code Daily 2024-06-01

* [Description](https://leetcode.com/problems/score-of-a-string/description) ## Code ```c++class Solution {public:    int scoreOfString(string s) {        int n = s.size(), ret = 0;        for (int i = 0; i + 1 < n; i++) {            ret += abs(s[i] - s[i + 1]);        }

2024-06-02 · 1 min

Leet Code Daily 2024-05-31

* [Description](https://leetcode.com/problems/single-number-iii/description) ## Solution Let's say $x$ and $y$ are the numbers we are looking for. We know: $$x \oplus y = \oplus_{i = 0}^{n - 1} A_i$$

2024-06-01 · 1 min

Leet Code Daily 2024-05-30

* [Description](https://leetcode.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/) ## Solution **Preffix Sum + Hash**  First, let's define preffix sum under `XOR` operator: $$S_{i} =  \begin{cases}    0 & i = 0 \\

2024-05-30 · 1 min

Leet Code Daily 2024-05-29

* [Description](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one) ## Solution **Simulation** ## Code ```c++class Solution {public:    int numSteps(string s) {

2024-05-29 · 1 min

Leet Code Daily 2024-05-28

* [Description](https://leetcode.com/problems/get-equal-substrings-within-budget) ## Solution Linear scan. ## Code ```c++class Solution {public:    int equalSubstring(string s, string t, int maxCost) {

2024-05-28 · 1 min

Leet Code Daily 2024-05-27

* [Description](https://leetcode.com/problems/special-array-with-x-elements-greater-than-or-equal-x) ## Code ```c++class Solution {public:    int specialArray(vector<int>& nums) {        sort(nums.begin(), nums.end());        for (int i = 0; i < nums.size(); i++) {            int c = nums.size() - i;            if (c <= nums[i] && (i == 0 || nums[i - 1] < c)) {

2024-05-27 · 1 min

Leet Code Daily 2024-05-26

## Leet Code Daily 2024-05-26 - Student Attendance Record II * [Description](https://leetcode.com/problems/student-attendance-record-ii) ## Solution It's just math.. Let's say $F(n)$ is the number of possible student attendance records of which: - The last record is `P`.- It contains no record `A`.

2024-05-26 · 2 min

Leet Code Daily 2024-05-25

* [Description](https://leetcode.com/problems/word-break-ii) ## Solution **DFS** ## Code ```c++class Solution {public:    unordered_set<string> wordSet;

2024-05-25 · 1 min

Leet Code Daily 2024-05-24

* [Description](https://leetcode.com/problems/maximum-score-words-formed-by-letters) ## Solution **DFS** ## Code ```c++constexpr int kNumLetters = 26; class Solution {

2024-05-24 · 2 min

Leet Code Daily 2024-05-23

* [Description](https://leetcode.com/problems/the-number-of-beautiful-subsets) ## Code ```c++class Solution {public:    int dfs(vector<int>& nums, unordered_map<int, int>& cnt, int i, int k) {        if (i == nums.size()) {            return cnt.empty() ? 0 : 1;        }        int ret = dfs(nums, cnt, i + 1, k);

2024-05-23 · 1 min

Leet Code Daily 2024-05-22

* [Description](https://leetcode.com/problems/palindrome-partitioning) ## Code ```c++class Solution {public:    void dfs(int x, int n, vector<vector<string>>& p, vector<string>& current,             vector<vector<string>>& ans) {        if (x == n) {            ans.push_back(vector<string>(current.begin(), current.end()));            return;

2024-05-22 · 1 min

Leet Code Daily 2024-05-21

* [Description](https://leetcode.com/problems/subsets) ## Code ```c++class Solution {public:    vector<vector<int>> subsets(vector<int>& nums) {        vector<vector<int>> ret;        const int n = nums.size();        for (int mask = 0; mask < (1 << n); mask++) {            vector<int> s;

2024-05-21 · 1 min

Leet Code Daily 2024-05-20

* [Description](https://leetcode.com/problems/sum-of-all-subset-xor-totals/) ## Code ```c++class Solution {public:    int dfs(vector<int>& nums, int i, int current_xor) {        return (i >= nums.size()) ? current_xor                                  : (dfs(nums, i + 1, current_xor) +                                     dfs(nums, i + 1, current_xor ^ nums[i]));    }

2024-05-20 · 1 min

Leet Code Daily 2024-05-19

* [Description](https://leetcode.com/problems/find-the-maximum-sum-of-node-values) ## Solution **Tree DP**. $$F(x, c) = \text{maximum sum of sub-tree x when the parent edge is operated } c \text{ times}$$ $$F(x, c) = \max{

2024-05-19 · 2 min

Leet Code Daily 2024-05-18

* [Description](https://leetcode.com/problems/distribute-coins-in-binary-tree) ## Code ```c++/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

2024-05-18 · 1 min

Leet Code Daily 2024-05-17

* [Description](https://leetcode.com/problems/delete-leaves-with-a-given-value) ## Code ```c++/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

2024-05-17 · 1 min

Leet Code Daily 2024-05-16

* [Description](https://leetcode.com/problems/evaluate-boolean-binary-tree) ## Code ```c++/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

2024-05-16 · 1 min

Leet Code Daily 2024-05-15

* [Description](https://leetcode.com/problems/find-the-safest-path-in-a-grid) ## Solution First, we can compute $F$ by **BFS**, where $$F_{i,j} = \text{ min manhattan distance from any leave to cell (i, j)}$$ Then we just need to find the best path $P$ where$\max_{(i, j) \in P}{F_{i, j}}$ is minimized. That can be done by **SPFA**.

2024-05-15 · 2 min

Leet Code Daily 2024-05-14

* [Description](https://leetcode.com/problems/path-with-maximum-gold) ## Solution **DFS** ## Code ```c++vector<pair<int, int>> kDir = {    { -1,  0 },    { +1,  0 },

2024-05-14 · 1 min

Leet Code Daily 2024-05-13

* [Description](https://leetcode.com/problems/score-after-flipping-matrix) ## Solution Enumerate $2^m$ possible states of toggling columns and for each case, decide the bestresult per row. ## Code ```c++class Solution {public:

2024-05-13 · 1 min

Leet Code Daily 2024-05-12

* [Description](https://leetcode.com/problems/largest-local-values-in-a-matrix) ## Code ```c++class Solution {public:    vector<vector<int>> largestLocal(vector<vector<int>>& grid) {        int n = grid.size(), m = grid[0].size();        vector<vector<int>> ans;        for (int i = 1; i + 1 < n; i++) {            vector<int> row;

2024-05-12 · 1 min

Leet Code Daily 2024-05-11

* [Description](https://leetcode.com/problems/minimum-cost-to-hire-k-workers) ## Solution Let's say $H$ is the set of hired workers and $C_i$ is the cost of hired worker $i$. $$\lvert H \rvert = k$$ We know all hired workers must be paid equally.

2024-05-11 · 2 min

Leet Code Daily 2024-05-10

* [Description](https://leetcode.com/problems/k-th-smallest-prime-fraction) ## Solution ### Monotonicity Optimization First, let's define: $$F(x, y) =\lvert  \{

2024-05-10 · 2 min

Leet Code Daily 2024-05-09

* [Description](https://leetcode.com/problems/maximize-happiness-of-selected-children) ## Code ```c++class Solution {public:    long long maximumHappinessSum(vector<int>& happiness, int k) {        sort(happiness.begin(), happiness.end());        long long ans = 0;        for (int i = happiness.size() - 1, d = 0; i >= 0 && d < k; i--, d++) {            ans += max(0, happiness[i] - d);

2024-05-09 · 1 min

Leet Code Daily 2024-05-08

* [Description](https://leetcode.com/problems/relative-ranks) ## Code ```c++unordered_map<int, string> kNames = {    { 1, "Gold Medal" },    { 2, "Silver Medal" },    { 3, "Bronze Medal" },}; class Solution {

2024-05-08 · 1 min

Leet Code Daily 2024-05-07

* [Description](https://leetcode.com/problems/double-a-number-represented-as-a-linked-list) ## Code ```c++/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode() : val(0), next(nullptr) {} *     ListNode(int x) : val(x), next(nullptr) {}

2024-05-07 · 1 min

Leet Code Daily 2024-05-06

* [Description](https://leetcode.com/problems/remove-nodes-from-linked-list) ## Code ```c++/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode() : val(0), next(nullptr) {} *     ListNode(int x) : val(x), next(nullptr) {}

2024-05-06 · 1 min

Leet Code Daily 2024-05-05

* [Description](https://leetcode.com/problems/delete-node-in-a-linked-list) ## Code ```c++/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * };

2024-05-05 · 1 min

Leet Code Daily 2024-05-04

* [Description](https://leetcode.com/problems/boats-to-save-people) ## Solution * First, sort all `people` in incresing order.* Let's say `people[i..j]` are the people which are not shipped yet.* There are several cases:  * `i == j`, then we only need last boat.  * `people[i] + people[j] <= limit`, then we carry both of them.  * otherwise, `people[j]` must be shipped alone. ### Code

2024-05-04 · 1 min

Leet Code Daily 2024-05-03

* [Description](https://leetcode.com/problems/compare-version-numbers) ## Code ```c++constexpr int kMaxLen = 500;typedef long long ll; class Solution {public:    void parseVersion(const string version, ll* v) {        int i = 0;

2024-05-03 · 1 min

Leet Code Daily 2024-05-02

* [Description](https://leetcode.com/problems/largest-positive-integer-that-exists-with-its-negative) ## Code ```c++constexpr int kMaxNum = 1000; class Solution {public:    int findMaxK(vector<int>& nums) {        bool has_pos[kMaxNum + 1] = { false };        bool has_neg[kMaxNum + 1] = { false };

2024-05-02 · 1 min

Leet Code Daily 2024-05-01

* [Description](https://leetcode.com/problems/reverse-prefix-of-word) ## Solution * Naive. ## Code ```c++class Solution {public:    string reversePrefix(string word, char ch) {

2024-05-01 · 1 min

Leet Code Daily 2024-04-30

* [Description](https://leetcode.com/problems/number-of-wonderful-substrings) ## Solution `Preffix Sum` + `Bit Mask`. ## Code ```c++class Solution {public:    int flip(int mask, int pos) {

2024-04-30 · 1 min

Leet Code Daily 2024-04-29

* [Description](https://leetcode.com/problems/minimum-number-of-operations-to-make-array-xor-equal-to-k) ## Solution * We need to flip each bit at most once.* So the answer is the number of `1` bits in $\oplus_{i=0}^{n - 1} \text{nums}_i \oplus k$. ## Code ```c++class Solution {public:

2024-04-29 · 1 min

Leet Code Daily 2024-04-28

* [Description](https://leetcode.com/problems/sum-of-distances-in-tree/description) ## Solution Let's take node `0` as the root and form the graph as a tree. By DFS, we can get: * $C(i) = \text{set of children of node } i$* $P(i) = \text{parent of node } i$ If we define:

2024-04-28 · 3 min

Leet Code Daily 2024-04-27

* [Description](https://leetcode.com/problems/freedom-trail) ## Solution First, let's say: * $M = len(\text{ring})$* $N = len(\text{key})$ ### DP If we define:

2024-04-27 · 2 min

Leet Code Weekly Contest 297

## 1. Calculate Amount Paid in Taxes * Simulation. ```c++class Solution {public:    double calculateTax(vector<vector<int>>& brackets, int income) {        double ans = 0;        for (int i = brackets.size() - 1; i > 0; i--) {            brackets[i][0] -= brackets[i - 1][0];        }

2022-06-12 · 3 min

Leet Code Weekly Contest 296

## 1. Min Max Game * Simulation. ```c++class Solution {public:    int minMaxGame(vector<int>& nums) {        while (nums.size() > 1) {            vector<int> tmp;            for (int i = 0, j = 0; i + 1 < nums.size(); i += 2, j = 1 - j) {                tmp.push_back(j == 0 ? min(nums[i], nums[i + 1]) : max(nums[i], nums[i + 1]));

2022-06-05 · 2 min

Leet Code Weekly Contest 295

## 1. Rearrange Characters to Make Target String * Hash-map. ```c++class Solution {public:    int rearrangeCharacters(string s, string target) {        unordered_map<char, int> cnt, tgt;        for (auto &c : s) {            cnt[c]++;        }

2022-05-29 · 4 min

Leet Code Weekly Contest 294

## 1. Percentage of Letter in String * Naive. ```c++class Solution {public:    int percentageLetter(string s, char letter) {        int cnt = 0, len = s.length();        for (auto &c : s) {            if (c == letter) {                cnt++;

2022-05-22 · 4 min

Leet Code Weekly Contest 293

## 1. Find Resultant Array After Removing Anagrams * Bruce-force. ```c++class Solution {public:    vector<string> removeAnagrams(vector<string>& words) {        vector<string> ans;        ans.push_back(words.front());        for (int i = 1; i < words.size(); i++) {            string x = ans.back(), y = words[i];

2022-05-15 · 3 min

Leet Code Weekly Contest 292

## 1. Largest 3-Same-Digit Number in String * Naive. ```c++class Solution {public:    string largestGoodInteger(string num) {        string ans = "";        for (int i = 0; i + 2 < num.length(); i++) {            string s = num.substr(i, 3);            if (s[0] == s[1] && s[1] == s[2] && s > ans) {

2022-05-08 · 4 min

Leet Code Weekly Contest 291

## 1. Remove Digit From Number to Maximize Result * Brute-force.* Be careful about the constaints! Use string comparision instead of converting to integer. ```c++class Solution {public:    string removeDigit(string number, char digit) {        string ans = "";                for (int i = 0; i < number.length(); i++) {

2022-05-01 · 2 min

Leet Code Weekly Contest 290

## 1. Intersection of Multiple Arrays * Take a **hash-map** to count the frequency of numbers.* The numbers with frequency $n$ should be part of the answer. ```c++class Solution {public:    vector<int> intersection(vector<vector<int>>& nums) {        int n = nums.size();        unordered_map<int, int> cnt;        for (auto &row : nums) {

2022-04-24 · 3 min

Leet Code Weekly Contest 289

## 1.  Calculate Digit Sum of a String * Simulation, naive :) ```c++class Solution {public:    string digitSum(string s, int k) {        while (s.length() > k) {            string t;            for (int i = 0; i < s.length(); i += k) {                int sum = 0;

2022-04-17 · 5 min

Leet Code Weekly Contest 288

## 1.  Largest Number After Digit Swaps by Parity * Well, just sort :) ```c++class Solution {public:    int largestInteger(int num) {        string digits = to_string(num);        for (int i = 0; i < digits.length(); i++) {            for (int j = i + 1; j < digits.length(); j++) {                int x = digits[i] - '0', y = digits[j] - '0';

2022-04-10 · 4 min

Leet Code Weekly Contest 287

## 1.  Minimum Number of Operations to Convert Time * Greedy. ```c++class Solution {public:    int toMins(string time) {        int h = 10 * (time[0] - '0') + (time[1] - '0');        int m = 10 * (time[3] - '0') + (time[4] - '0');        return h * 60 + m;    }

2022-04-03 · 3 min

Leet Code Weekly Contest 286

## 1.  Find the Difference of Two Arrays * Hash-set. ```c++class Solution {public:    vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {        unordered_set<int> set1(nums1.begin(), nums1.end()), set2(nums2.begin(), nums2.end());        vector<vector<int>> ans(2);                for (auto &x : set1) {

2022-03-30 · 3 min

Leet Code Weekly Contest 284

## 1. Find All K-Distant Indices in an Array * $O(n^2)$ brute-force is enough. ```c++class Solution{public:     vector<int> findKDistantIndices(vector<int>& nums, int key, int k)    {        int n = nums.size();

2022-03-16 · 4 min

Leet Code Weekly Contest 283

## 1. Cells in a Range on an Excel Sheet * Brute-force. ```c++class Solution{public:     vector<string> cellsInRange(string s)    {        vector<string> ans;

2022-03-06 · 3 min

Leet Code Weekly Contest 282

## 1. Counting Words With a Given Prefix * Brute-force. ```c++class Solution{public:        bool valid(string &word, string &ref)    {        if (ref.length() > word.length())

2022-02-27 · 3 min

Leet Code Weekly Contest 281

## 1. Count Integers With Even Digit Sum * Naive. ```c++class Solution{public:        int digitSum(int x)    {        int ret = 0;

2022-02-20 · 4 min

Leet Code Weekly Contest 280

## 1. Count Operations to Obtain Zero * Naive. ```c++class Solution{public:    int countOperations(int num1, int num2)    {        int ans = 0;

2022-02-13 · 5 min

Leet Code Weekly Contest 279

## 1. Sort Even and Odd Indices Independently Naive. ```c++class Solution{public:    vector<int> sortEvenOdd(vector<int>& nums)    {        vector<int> a, b;

2022-02-06 · 4 min

Leet Code Weekly Contest 278

## 1. Keep Multiplying Found Values by Two * Hash. ```c++class Solution{public:        int findFinalValue(vector<int>& nums, int original)    {        unordered_set<int> s(nums.begin(), nums.end());

2022-01-30 · 3 min

Leet Code Weekly Contest 277

## 1. Count Elements With Strictly Smaller and Greater Elements Count the numbers which are strictly greater than the minimum and strictly lower than the maximum. ```c++class Solution{public:     int countElements(vector<int>& nums)    {        int a = INT_MAX, b = INT_MIN;

2022-01-23 · 3 min

Leet Code Weekly Contest 276

## 1. Divide a String Into Groups of Size k * Naive. ```c++class Solution{public:    vector<string> divideString(string s, int k, char fill)    {        vector<string> ans = { "" };

2022-01-16 · 2 min

Leet Code Weekly Contest 275

## 1. Check if Every Row and Column Contains All Numbers * Naive ```c++class Solution{public:    bool valid(set<int> &s, int n)    {        for (int i = 1; i <= n; i++)        {

2022-01-09 · 3 min

Leet Code Weekly Contest 274

## 1. Check if All A's Appears Before All B's It can be done in $O(n)$ time. But to save time, $O(n^2)$ brute-force is enough :). ```c++class Solution{public:    bool checkString(string s)    {        for (int i = 0; i < s.length(); i++)        {

2022-01-02 · 4 min

Leet Code Weekly Contest 273

## 1. A Number After a Double Reversal Naive. ```c++class Solution{public:        int rev(int x)    {        int ret = 0;

2021-12-26 · 4 min

Leet Code Weekly Contest 272

## 1. Find First Palindromic String in the Array Palindromic string detection, naive :) ```c++class Solution{public:        bool valid(string &s)    {        for (int i = 0, j = s.length() - 1; i < j; i++, j--)

2021-12-19 · 3 min

Leet Code Weekly Contest 271

## 1. Rings and Rods Native. ```c++class Solution {public:    int countPoints(string rings)    {        bool has[10][3];                for (int i = 0; i < 10; i++)

2021-12-12 · 4 min

Leet Code Weekly Contest 270

## 1. Finding 3-Digit Even Numbers Brute-force. ```c++class Solution {public:    vector<int> findEvenNumbers(vector<int>& digits)    {        unordered_set<int> ret;                for (int i = 0; i < digits.size(); i++)

2021-12-05 · 3 min

Leet Code Weekly Contest 269

## 1. Find Target Indices After Sorting Array Naive, sort and linear-scan. ```c++class Solution{public:        vector<int> targetIndices(vector<int>& nums, int target)    {        sort(nums.begin(), nums.end());

2021-11-28 · 3 min

Leet Code Weekly Contest 268

## 1. Two Furthest Houses With Different Colors Simply enumerate all pairs of indexes. $O(n^2)$. ```c++class Solution {public:    int maxDistance(vector<int>& colors)    {        int ans = INT_MIN;                for (int i = 0; i < colors.size(); i++)

2021-11-21 · 5 min

Leet Code Weekly Contest 267

## 1. Time Needed to Buy Tickets Simulate the process as descriped. ```c++class Solution{public:    int timeRequiredToBuy(vector<int>& tickets, int k)     {        queue<pair<int, int>> q;

2021-11-14 · 3 min

Leet Code Weekly Contest 266

## 1. Count Vowel Substrings of a String Brute-force, time complexity: $O(n^2)$ ```c++class Solution {public:        bool valid(string s)    {        bool has[5];

2021-11-07 · 4 min

Leet Code Weekly Contest 265

## 1. Smallest Index With Equal Value $O(n)$ linear scan. ```c++class Solution{public:    int smallestEqual(vector<int>& nums)    {        for (int i = 0; i < nums.size(); i++)        {

2021-10-31 · 6 min

Leet Code Weekly Contest 264

## 1. Number of Valid Words in a Sentence Naive, simple string processing. ```c++inline vector<string> split(string s, char delimiter = ' '){    auto words = vector<string>({ "" });     for (auto &c : s)    {        if (c == delimiter)

2021-10-24 · 4 min

Leet Code Weekly Contest 263

## 1. Check if Numbers Are Ascending in a Sentence Naive. Simple string processing. $O(n)$.  ```c++class Solution{public:    bool isNum(string &s)    {        for (int i = 0; i < s.length(); i++)        {

2021-10-17 · 4 min

Leet Code Weekly Contest 262

## 1. [Two Out of Three](https://leetcode.com/contest/weekly-contest-262/problems/two-out-of-three/) Naive. Just do it as described. ```c++class Solution {public:    vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) {              set<int> any, s[3];       for (int i = 0; i < nums1.size(); i++)

2021-10-11 · 4 min

Leet Code Weekly Contest 261

## 1. [Minimum Moves to Convert String](https://leetcode.com/contest/weekly-contest-261/problems/minimum-moves-to-convert-string/) Simple DP. $$F_i = \begin{cases}	F_{i + 1} & S_i = 'O' \\	F_{i + 3} + 1 & S_i = '1' \land i + 3 <= n \\	1 & S_i = '1' \land i + 3 > n \\\end{cases}$$

2021-10-03 · 5 min

Leet Code Weekly Contest 260

## 1. Maximum Difference Between Increasing Elements Linear scan. Time complexity: $O(n)$. ```c++class Solution {public:     int maximumDifference(vector<int>& nums) {        int ans = -1, n = nums.size();

2021-11-08 · 4 min

Leet Code Weekly Contest 191

## 1. Maximum Product of Two Elements in an Array Naive. ```c++class Solution {public:    int maxProduct(vector<int>& nums) {          int ans = 0;            for (int i = 0; i < nums.size(); i++)

2020-06-26 · 2 min

Leet Code Weekly Contest 190

## 1. Check If a Word Occurs As a Prefix of Any Word in a Sentence Naive. ```javascriptvar isPrefixOfWord = function(sentence, searchWord) {        return sentence        .split(' ')        .reduce((ans, word, idx) =>             (ans == -1 && word.startsWith(searchWord)) ? (idx + 1) : ans        , -1);

2020-06-12 · 2 min

Leet Code Weekly Contest 189

## 1. Number of Students Doing Homework at a Given Time No need to talk. ```javascriptvar busyStudent = function(startTime, endTime, queryTime) {   return startTime.filter((idx, s) =>		s <= queryTime && queryTime <= endTime[idx]).length;};```

2020-05-17 · 2 min

Leet Code Weekly Contest 188

## 1. Build an Array With Stack Operations Stack is a FIFO container. Pop all useless elements before pushing the nextelement. ```c++class Solution {public:    vector<string> buildArray(vector<int>& target, int n) {         bool useful[101];

2020-05-10 · 4 min

Leet Code Weekly Contest 187

## 1. Destination City Let's say, * $S = \{ x \mid (x, y) \text{ is a path} \}$* $T = \{ y \mid (x, y) \text{ is a path} \}$ The answer is $T - S$. ```c++class Solution {public:

2020-05-03 · 3 min

Leet Code Weekly Contest 186

## 1. Maximum Score After Splitting a String Preffix-sum. ```c++class Solution {public:    int maxScore(string s) {                int s0[501],s1[501];                s0[0] = s1[0] = 0;

2020-04-27 · 3 min

Leet Code Weekly Contest 185

## 1. Reformat The String Divide the characters into two groups: `digits` and `letters`, just try`digits` first or `letters` first. ```c++class Solution {public:    string reformat(string s) {                string s1 = "";        string s2 = "";

2020-04-24 · 5 min

Leet Code Weekly Contest 184

## 1. [String Matching in an Array](https://leetcode.com/contest/weekly-contest-184/problems/string-matching-in-an-array/) KMP. ```c++class kmp {   public:        static vector<int> pmt_of(string p) {       vector<int> pmt = { -1 };

2020-04-12 · 4 min

Leet Code Weekly Contest 183

## 1. [Minimum Subsequence in Non-Increasing Order](https://leetcode.com/contest/weekly-contest-183/problems/minimum-subsequence-in-non-increasing-order/) Just sort. ```c++#include<vector> using namespace std; template<typename T>class quick_sort {

2020-04-05 · 8 min

Leet Code Weekly Contest 182

## 1. [Find Lucky Integer in an Array](https://leetcode.com/contest/weekly-contest-182/problems/find-lucky-integer-in-an-array/) $O(n)$, just show the code. ```c++class Solution {public:    int findLucky(vector<int>& arr) {                int f[501];                for (int i = 1; i <= 500; i++) {

2020-03-31 · 7 min

Leet Code Weekly Contest 181

## 1. [Create Target Array in the Given Order](https://leetcode.com/contest/weekly-contest-181/problems/create-target-array-in-the-given-order/) Naive, no need to talk. ```c++int* createTargetArray(int* nums, int numsSize, int* index, int indexSize, int* returnSize){     int i, j, *ret = (int*) malloc(sizeof(int) * numsSize);        for (i = 0; i < numsSize && i < indexSize; i++) {                for (j = i; j > index[i]; j--) {

2020-03-22 · 3 min

Leet Code Weekly Contest 180

## 1. [Lucky Numbers in a Matrix](https://leetcode.com/contest/weekly-contest-180/problems/lucky-numbers-in-a-matrix/) Saddle point of a matrix. ```c++int* luckyNumbers (int** matrix, int matrixSize, int* matrixColSize, int* returnSize){     int *min = (int*) malloc(sizeof(int) * matrixSize);    int *max = (int*) malloc(sizeof(int) * matrixColSize[0]);     int i, j, k, *ret;

2020-03-24 · 5 min

Leet Code Weekly Contest 179

## 1. [Generate a String With Characters That Have Odd Counts](https://leetcode.com/contest/weekly-contest-179/problems/generate-a-string-with-characters-that-have-odd-counts/) One simple solution could be: $$\text{answer} = \begin{cases}\underbrace{\text{a}, \dots, \text{a}}_n, \text{b} & n \mod 2 = 0 \\\underbrace{\text{a}, \dots, \text{a}}_n & n \mod 2 = 1 \\ \end{cases}$$

2020-04-13 · 4 min

Leet Code Weekly Contest 178

## 1. [How Many Numbers Are Smaller Than the Current Number](https://leetcode.com/contest/weekly-contest-178/problems/how-many-numbers-are-smaller-than-the-current-number/) Brute force. ```c++class Solution {public:    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {                vector<int> result;                for (int i = 0; i < nums.size(); i++) {

2020-04-14 · 5 min

Leet Code Weekly Contest 177

## 1. Number of Days Between Two Dates To save time, I use javascript for this problem. ```javascriptvar daysBetweenDates = function(date1, date2) {   return Math.abs(Math.floor((Date.parse(date2) - Date.parse(date1)) / 86400000));};``` ## 2. Validate Binary Tree Nodes

2020-04-24 · 4 min

SPOJ 4061 - MPOLY - Polygon

There are N points in a plane whose coordinates are natural numbers. A convex polygon with maximal number of vertices is a convex polygon whose vertices are some of given points and the origin having maximal possible number of vertices. Origin, i.e. point with coordinates (0,0), must be one of vertices of a convex polygon with maximal number of vertices. Write a program that will determine number of vertices in such polygon. A polygon is convex if every line segment whose endpoints are inside that polygon is also completely inside it. Consecutive edges of a polygon must not be parallel. ## Input The first line of input file contains a natural number N, 2 ≤ N ≤ 100, a number of given points. Each of the following N lines contains two natural numbers X and Y, 1 ≤ X ≤ 100, 1 ≤ Y ≤ 100, separated by a space character, coordinates of one point.

2019-06-29 · 4 min

SPOJ 34409 - DISGRAPH - Disconnected country

Cities of the ancient country GRAPH connected by two-way (bidirectional) roads so that from any city you can get to any other city. The Sultan wants to destroy some roads and divide the country into two separate (disconnected) areas, so that from the city of one area it was impossible to get to the city of another area. You are the Minister of transportation and your task is to minimize the number of roads that need to be destroyed. You have a lot of time and the Sultan hopes :-) that you will solve this task. ## Input The first line of input will contain one integer number 8 ≤ N ≤ 1400, number of cities in GRAPH. Follow N lines. Each line represents cities (direct neighbors) connected to the city number i (cities numbering is zero based) by one road. There will be 7 input files. ## Output One integer number. The minimum number of roads that need to be destroyed. ## Example

2019-06-18 · 4 min

SPOJ 5732 - PARADOX - Paradox

A paradox is a statement or group of statements that leads to a contradiction. Consider the following two statements. * "The statement below is false."* "The statement above is true." If we assume that 1st statement is true then according to 1st statement the 2nd statement is false. Since the 2nd statement is false and it says that 1st statement is true, 1st statement must be false which is a contradiction. If we assume that 1st statement is false then the 2nd statement must be true (since 1st statement says 2nd statement is false). Then according to 2nd statement 1st statement must be true which is a contradiction. Thus the statement cannot be classified as true or false. This is a paradox. Given N statements of the form "Statement X is true/false", 1<=X<=N, your task is to find if these set of statements are paradoxical or not. A set of statements is paradoxical if one or more statements cannot be classified as true or false. ## Input Multiple test cases. Each test cases begins with an integer N representing the number of statements. **1<=N<=100**. Then follow N lines, representing N statements in the order 1,2,3, ...,N. Each line contains an integer X and a string S separated by a space. **1<=X<=N. S is either "true" or "false"** (quotes for clarity), which means the statement is "Statement X is S". N=0 indicates the end of testcases and should not be processed. There are atmost 10000 testcases.

2019-06-16 · 4 min

SPOJ 10394 - ABA12C - Buying Apples!

Harish went to a supermarket to buy exactly ‘k’ kilograms apples for his ‘n’ friends. The supermarket was really weird. The pricing of items was very different. He went to the Apples section and enquired about the prices. The salesman gave him a card in which he found that the prices of apples were not per kg. The apples were packed into covers, each containing ‘x’ kg of apples, x > 0 and ‘x’ is an integer. An ‘x’ kg packet would be valued at ‘y’ rupees. So, the placard contained a table with an entry ‘y’ denoting the price of an ‘x’ kg packet. If ‘y’ is -1 it means that the corresponding packet is not available. Now as apples are available only in packets, he decides to buy atmost ‘n’ packets for his ‘n’ friends i.e he will not buy more than n packets of apples. Harish likes his friends a lot and so he does not want to disappoint his friends. So now, he will tell you how many friends he has and you have to tell him the minimum amount of money he has to spend for his friends. ## Input The first line of input will contain the number of test cases, C. Each test case will contain two lines. The first line containing N and K, the number of friends he has and the amount of Apples in kilograms which he should buy.