algorithms/leetcode/solutions.org

#+title: Leetcode doc
#+author: Aryadev Chavali
#+description: Description
#+date: 2024-04-29

* 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++ :comments link
#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 - 1; ++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 :comments link
#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 :comments link
#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 :comments link
#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 :comments link
#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 :comments link
#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 :comments link
#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 :comments link
#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 arrays which are smaller and easier for the CPU to work with.

#+begin_src c++ :tangle 36.cpp :comments link
#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 :comments link
#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
** DONE (#53) Maximum Subarray
Find the maximal sum of a subarray in some array.  This is actually a
dynamic programming problem.
*** Brute force
If there's only one element then that is obviously the maximal sum.
A brute force approach would compute it every subarray sum and then
return the best one.

#+begin_src c++ :tangle 53-bf.cpp :comments link
#include <bits/stdc++.h>
using namespace std;

int maxSubArray(vector<int> &nums)
{
  int max_sum = nums[0];
  for (int i = 1; i < nums.size(); ++i)
  {
    // Is nums[i] alone better than what we've made so far?
    max_sum = std::max(nums[i], max_sum);
    int cur_sum = 0;
    for (int j = 0; j <= i; ++j)
      cur_sum += nums[i];
    // Is the sum nums[0..i] better than what we've done so far?
    max_sum = std::max(std::max(cur_sum, max_sum));
  }
  return max_sum;
}
#+end_src

O(n^2) but can we do better?
*** Dynamic programming
Look at the tree of cur_sum's we need to
compute:
+ at i = 1, cur_sum is sum[0..1]
+ at i = 2, cur_sum is sum[0..2]
+ at i = k, cur_sum is sum[0..k] = sum[0..k-1] + k

At each iteration we're essentially checking if nums[i] is better or
the sum is better than what we've seen before.

Obviously the sum is stupidly expensive.  Furthermore, we may not even
need to do the entire sum; if the best sum starts at k and ends at k'
there's literally no point in summing numbers before k in cur_sum.  So
we may as well introduce that optimisation.
#+begin_src c++ :tangle 53-dp.cpp :comments link
#+end_src
*** Kadane's formulation
#+begin_src c++ :tangle 53-kadane.cpp :comments link
#include <bits/stdc++.h>

using namespace std;

int maxSubArray(vector<int> &nums)
{
  if (nums.size() == 1)
    return nums[0];
  int max_sum = nums[0], cur_sum = nums[0];
  for (size_t i = 1; i < nums.size(); ++i)
  {
    cur_sum = std::max(cur_sum + nums[i], nums[i]);
    max_sum = std::max(cur_sum, max_sum);
  }
  return max_sum;
}
#+end_src
* Stack
** DONE (#20) Valid Parentheses
#+begin_src c++ :tangle 20.cpp :comments link
#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 :comments link
#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 :comments link
#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 :comments link
#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 :comments link
#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
* Linked Lists
** TODO (#2) Add two numbers
Given two linked lists representing the digits of a number in reverse
order, return their sum.
#+begin_src c++ :tangle 2.cpp :comments link
#include <bits/stdc++.h>
using namespace std;

struct ListNode
{
  int val;
  ListNode *next;

  ListNode() : val{0}, next{nullptr}
  {
  }

  ListNode(int val) : val{val}, next{nullptr}
  {
  }

  ListNode(int val, ListNode *next) : val{val}, next{next}
  {
  }

  ~ListNode()
  {
    if (next)
      delete next;
  }
};

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
{
  if (!(l1 && l2) ||
      (l1->val == l2->val && l1->val == 0 && !(l1->next || l2->next)))
    return l1;

  int carry = 0;
  int sum   = l1->val + l2->val;

  ListNode *root = new ListNode(sum % 10);
  ListNode *end  = root;

  carry = sum / 10;
  l1    = l1->next;
  l2    = l2->next;

  for (; l1 && l2; l1 = l1->next, l2 = l2->next)
  {
    sum   = l1->val + l2->val + carry;
    carry = sum / 10;
    sum %= 10;

    auto node = new ListNode(sum, nullptr);
    end->next = node;
    end       = node;
  }

  if (l1 || l2)
  {
    auto remaining = l1 ? l1 : l2;
    for (; remaining; remaining = remaining->next)
    {
      remaining->val += carry;
      carry = remaining->val / 10;
      remaining->val %= 10;
      end->next = remaining;
      end       = remaining;
    }
  }

  if (carry != 0)
  {
    auto node = new ListNode(carry, nullptr);
    end->next = node;
  }

  return root;
}
#+end_src
* Blind 75