diff options
| -rw-r--r-- | leetcode/solutions.org | 531 |
1 files changed, 531 insertions, 0 deletions
diff --git a/leetcode/solutions.org b/leetcode/solutions.org new file mode 100644 index 0000000..9be16cc --- /dev/null +++ b/leetcode/solutions.org @@ -0,0 +1,531 @@ +#+title: Leetcode doc +#+author: Aryadev Chavali +#+description: Description +#+date: 2024-04-29 + +* Prelude +#+begin_src c++ :session c++ +test +#+end_src +* Arrays +** DONE (#217) Contains duplicate +If there are any duplicates, then when the list is sorted they would +be consecutive. +#+begin_src c++ :tangle 217.cpp :session c++ +#include <bits/stdc++.h> + +using namespace std; + +bool containsDuplicate(vector<int> &nums) +{ + std::sort(nums.begin(), nums.end()); + const size_t n = nums.size() - 1; + for (const size_t i = 0; i < n; ++i) + if (nums[i] == nums[i + 1]) + return true; + return false; +} +#+end_src +** DONE (#242) Valid anagram +If two things are anagrams of each other then they are equivalent +disregarding ordering. + +*** Sorting the strings +Sorting the two strings would force the same +order for both strings. + +#+begin_src c++ :tangle 242-sort.cpp +#include <bits/stdc++.h> +using namespace std; +bool isAnagram(string s, string t) +{ + std::sort(s.begin(), s.end()); + std::sort(t.begin(), t.end()); + return s == t; +} +#+end_src +*** Simple table +#+begin_src c++ :tangle 242-table.cpp +#include <bits/stdc++.h> +using namespace std; +bool isAnagram(string s, string t) +{ + if (s.size() != t.size()) + return false; + int table[26] = {0}; + for (size_t i = 0; i < s.size(); ++i) + { + table[s[i] - 'a'] += 1; + table[t[i] - 'a'] -= 1; + } + + return std::all_of(table, table + 26, [](int i) { return i == 0; }); +} +#+end_src +** DONE (#1) Two sum +Given a target find two elements which sum to it. +#+begin_src c++ :tangle 1.cpp +#include <bits/stdc++.h> +using namespace std; +vector<int> twoSum(vector<int> &nums, int target) +{ + unordered_map<int, int> diffs; + for (int i = 0; i < nums.size(); ++i) + { + if (diffs.find(target - nums[i]) != diffs.end()) + return {diffs[target-nums[i]], i}; + else + diffs[nums[i]] = i; + } + return {}; +} +#+end_src +** DONE (#49) Group anagrams +#+begin_src c++ :tangle 49.cpp +#include <bits/stdc++.h> +using namespace std; +vector<vector<string>> groupAnagrams(vector<string> &strs) +{ + unordered_map<string, vector<string>> map; + for (auto str : strs) + { + string s = str; + sort(s.begin(), s.end()); + map[s].push_back(str); + } + + vector<vector<string>> ret; + for (const auto &x : map) + ret.push_back(x.second); + return ret; +} +#+end_src +** DONE (#347) Top k frequent elements +Get the top k most frequency elements in an array. Frequencies imply +hash tables. +*** Sorting the map +Once you've generated the map, sort it by frequency (then by number) +then take the top k off it. +#+begin_src c++ :tangle 347-sort.cpp +#include <bits/stdc++.h> +using namespace std; +vector<int> topKFrequent(vector<int> &nums, int k) +{ + unordered_map<int, int> map; + for (auto num : nums) + map[num] += 1; + + vector<pair<int, int>> vec(map.begin(), map.end()); + sort(vec.begin(), vec.end(), + [](pair<int, int> a, pair<int, int> b) + { + if (a.second == b.second) + return a.first > b.first; + return a.second > b.second; + }); + + vector<int> topk; + for (size_t i = 0; i < k; ++i) + topk.push_back(vec[i].first); + return topk; +} +#+end_src +*** Using a queue +Instead of sorting the map, we can use a priority queue. Remember +that an item in a priority queue has two members: the priority and the +value. The priority sorts the members. + +Hence, if we generate the map then place them all in a priority queue, +we just need to get the k highest priority items to finish the +problem. +#+begin_src c++ :tangle 347-queue.cpp +#include <bits/stdc++.h> +using namespace std; + +vector<int> topKFrequent(vector<int> &nums, int k) +{ + unordered_map<int, int> map; + for (const auto num : nums) + map[num] += 1; + + priority_queue<pair<int, int>> queue; + for (const auto &pair : map) + // priority=frequency, value=value + queue.push({pair.second, pair.first}); + + vector<int> topk; + for (size_t i = 0; i < k; ++i) + { + topk.push_back(pq.top().second); + pq.pop(); + } + return topk; +} +#+end_src +** DONE (#238) Product of array except self +Return an array where at each index i the element is simply the +product of all elements except the input@i. You cannot use division +and it has to be O(n). + +Mathematically this is asking for the product [nums[x] | x from 0 to +n] / nums[i]. We can split this into [x from 0 to i - 1] and [x from +i to n] and consider them. These products work linearly as we iterate +i: [x from 0 to i - 1] * i is the product [x from 0 to i]. Same the +other way. So we can iterate once to produce the products before i +and once for the products after i while only doing a set once! + +#+begin_src c++ :tangle 238.cpp +#include <bits/stdc++.h> + +using namespace std; + +vector<int> productexceptself(vector<int> &nums) +{ + const int n = nums.size(); + vector<int> out(n, 0); + out[0] = 1; + for (int i = 0; i < n - 1; ++i) + out[i + 1] = out[i] * nums[i]; + int postfix = 1; + for (int i = n - 1; i >= 0; --i) + out[i] *= postfix; + postfix *= nums[i]; + return out; +} +#+end_src +** DONE (#36) Valid sudoku +Determine if a 9x9 grid is a valid sudoku. + +You can use a set of hashsets (where membership testing is O(1)) to +just check if you've seen a number before. In this case, since we +know the exact input data and the properties we want we can use +boolean tables to speed up the process. + +I also use a little maths technique to produce a correct ordering of +the boxes via integer division. +#+begin_src c++ :tangle 36.cpp +#include <bits/stdc++.h> +using namespace std; + +constexpr size_t box_count(const size_t row, const size_t col) +{ + return (3 * (row / 3)) + (col / 3); +} + +bool isValidSudoku(vector<vector<char>> &board) +{ + bool row_digits[9][9] = { 0 }; + bool col_digits[9][9] = { 0 }; + bool box_digits[9][9] = { 0 }; + + for (size_t i = 0; i < 9; ++i) + { + for (size_t j = 0; j < 9; ++j) { + if (board[i][j] == '.') + continue; + const auto val = board[i][j] - '0' - 1; + if (box_digits[box_count(i, j)][val] || col_digits[j][val] || + row_digits[i][val]) + return false; + box_digits[box_count(i, j)][val] = true; + col_digits[j][val] = true; + row_digits[i][val] = true; + } + } + + return true; +} +#+end_src +** DONE (#128) Longest consecutive sequence + +#+begin_src c++ :tangle 128.cpp +#include <bits/stdc++.h> +using namespace std; + +int longestConsecutive(vector<int> &nums) +{ + unordered_set<int> s{nums.begin(), nums.end()}; + size_t size = 0; + for (auto num : nums) + { + if (s.find(num - 1) != s.end()) + continue; + size_t seq = 1; + for (size_t x = num; s.find(x + 1) != s.end(); ++x, ++seq) + continue; + size = size < seq ? seq : size; + } + return size; +} +#+end_src +* Stack +** DONE (#20) Valid Parentheses +#+begin_src c++ :tangle 20.cpp +#include <bits/stdc++.h> +using namespace std; + +#define check_top(COUNTER, WANTED) !(COUNTER.size() != 0 && COUNTER.top() == WANTED) + +bool isValid(string s) +{ + stack<char> counter; + for (const auto x : s) + { + switch (x) { + case '(': + case '{': + case '[': + counter.push(x); + break; + case ')': + if (check_top(counter, '(')) + return false; + counter.pop(); + break; + case '}': + if (check_top(counter, '{')) + return false; + counter.pop(); + break; + case ']': + if (check_top(counter, '[')) + return false; + counter.pop(); + break; + } + } + return counter.size() == 0; +} +#+end_src +** DONE (#155) Min Stack +Make a minimal implementation of a stack which does all its main +functions in O(1) (what?!). + +In exchange for O(n) memory we can implement most of them. +Unfortunately all the high performance implementations also use stacks +(what's the point!). +#+begin_src c++ :tangle 155.cpp +#include <bits/stdc++.h> + +using namespace std; + +class MinStack +{ +private: + stack<int> ordered; + size_t ptr; + vector<int> data; +public: + MinStack(): data{}, ptr{0} + { + } + + void push(int val) + { + if (ptr == data.size()) + data.push_back(val); + else + data[ptr] = val; + + if (ordered.size() == 0 || ordered.top() >= val) + ordered.push(val); + + ++ptr; + } + + void pop() + { + --ptr; + if (data[ptr] == ordered.top()) + ordered.pop(); + } + + int top() + { + return data[ptr - 1]; + } + + int getMin() + { + return ordered.top(); + } +}; +#+end_src +** DONE (#150) Evaluate RPN +You're given an RPN expression in tokens e.g. ["2", "3", "+"], run it. + +Encountered an issue with C/C++'s semantics when it comes prefix +decrement: it doesn't have an effect until after the statement so the +other side of the assignment still considers ~ptr~ to be the same +value. Bit interesting, good to note. +#+begin_src c++ :tangle 150.cpp +#include <bits/stdc++.h> +using namespace std; + +int evalRPN(vector<string>& tokens) +{ + vector<int> stack{}; + size_t ptr = 0; + for (const auto &token : tokens) + { + if (token == "+") + stack[(--ptr) - 1] += stack[ptr - 1]; + else if (token == "-") + stack[(--ptr) - 1] -= stack[ptr - 1]; + else if (token == "*") + stack[(--ptr) - 1] *= stack[ptr - 1]; + else if (token == "/") + stack[(--ptr) - 1] /= stack[ptr - 1]; + else + { + int n = stoi(token); + if (stack.size() <= ptr) + stack.push_back(n); + else + stack[ptr] = n; + ++ptr; + } + } + return stack[0]; +} +#+end_src +** DONE (#22) Generate Parentheses +Given n, generate all possible well formed combinations of +parentheses. + +*** Naive solution +I generate all 2^n bit strings (where n = 2 * number of pairs) then +filer all the invalid bit strings. +#+begin_src c++ :tangle 22-naive.cpp +#include <bits/stdc++.h> + +using namespace std; + +unordered_map<int, unordered_set<bitset<16>>> memo; + +bool is_valid(size_t size, bitset<16> n) +{ + stack<bool> s; + for (size_t i = 0; i < size; ++i) + { + if (n[i]) + s.push(true); + else + { + if (s.size() == 0) + return false; + s.pop(); + } + } + return s.size() == 0; +} + +string bits_to_string(size_t size, bitset<16> n) +{ + stringstream ss; + for (size_t i = 0; i < size; ++i) + ss << (n[i] ? "(" : ")"); + return ss.str(); +} + +unordered_set<bitset<16>> recursive(int n) +{ + if (memo.find(n) != memo.end()) + return memo[n]; + auto prev = recursive(n - 1); + unordered_set<bitset<16>> res{}; + for (const auto &map : prev) + { + bitset<16> has_1 = map; + has_1[n - 1] = true; + res.insert(has_1); + res.insert(map); + } + memo[n] = res; + return res; +} + +vector<string> generateParenthesis(int n) +{ + memo[1].insert(0); + memo[1].insert(1); + unordered_set<bitset<16>> sets = recursive(2 * n); + vector<string> strings; + for (const auto &set : sets) + if (is_valid(2 * n, set)) + strings.push_back(bits_to_string(2 * n, set)); + return strings; +} +#+end_src +*** Backtracking +Instead of generating all bit strings and then filtering out, let's +just build the strings bit by bit? Here we use a queue (though we +could use recursion) to generate bigger and bigger paren strings. We +pop off the queue and check three things: if the string is the right +size then push it onto the vector. If the string has insufficient +number of open braces, add an open brace. If the string has +insufficient closed braces in comparison to open braces add a close +brace. + +Notice the heuristic: we generate both combinatorial paths for the +string (add an open brace or add a closed brace) but only generate the +second one based on a condition on the first. As we do these +simultaneously we can generate the two possible next steps given an +input string. +#+begin_src c++ :tangle 22-backtrack.cpp +#include <bits/stdc++.h> + +using namespace std; + +struct Work +{ + int open_braces, close_braces; + string str; +}; + +vector<string> generateParenthesis(int n) +{ + vector<string> results; + queue<Work> queue; + queue.push({0, 0, ""}); + while (queue.size() != 0) + { + auto res = queue.front(); + queue.pop(); + if (res.str.size() == (size_t)2 * n) + results.push_back(res.str); + if (res.open_braces < n) + queue.push({res.open_braces + 1, res.close_braces, res.str + "("}); + if (res.close_braces < res.open_braces) + queue.push({res.open_braces, res.close_braces + 1, res.str + ")"}); + } + return results; +} +#+end_src +** TODO (#739) Daily temperatures +Given an array of temperatures t[i], generate an array /a/ where a[i] +is the number of days it takes to surpass t[i]. If there is no +temperature which surpasses t[i], a[i] = 0. + +#+begin_src c++ :tangle 739.cpp :comments link +#include <bits/stdc++.h> + +using namespace std; + +vector<int> dailyTemperatures(vector<int> &temperatures) +{ + stack<int> stack; + vector<int> days{(int)temperatures.size()}; + for (size_t i = 0; i < temperatures.size(); ++i) + { + while (!stack.empty() && temperatures[stack.top()] < temperatures[i]) + { + int prev = stack.top(); + days[prev] = i - prev; + stack.pop(); + } + stack.push(i); + } + return days; +} +#+end_src |