aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAryadev Chavali <aryadev@aryadevchavali.com>2024-07-17 20:10:06 +0100
committerAryadev Chavali <aryadev@aryadevchavali.com>2024-07-17 20:10:06 +0100
commit6d21bce57be8440b56df10fe5d0ae7bd7e86037a (patch)
tree806b1c6e28bfa4f3a8a03d5a232b0099b57f3c53
parent4359caa3ca15c75c4241d869259af3be8cc8375f (diff)
downloadalgorithms-6d21bce57be8440b56df10fe5d0ae7bd7e86037a.tar.gz
algorithms-6d21bce57be8440b56df10fe5d0ae7bd7e86037a.tar.bz2
algorithms-6d21bce57be8440b56df10fe5d0ae7bd7e86037a.zip
Tons of solutions
-rw-r--r--leetcode/solutions.org531
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