#+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