stack<pair<int, int>> st;
// Finding minimum
return st.top().second;
// Adding an element (newElem)
int newMin = st.empty() ? newElem : min(newElem, st.top().second);
st.push({newElem, newMin});
// Removing and element
int removedElement = st.top().first;
st.pop();Store only those items which are needed to determine the minimum (Monotonic queue). All the elements that we removed can never be a minimum itself, so this operation is allowed.
When we extract minimum from (original queue) it might not be there since we removed it so we should check before removing.
deque<int> q;
// Finding minimum
return q.front();
// Adding an element (newElem)
while (!q.empty() && q.back() > newElem) q.pop_back();
q.push_back(newElem);
// Removing an element
if (!q.empty() && q.front() == removeElement) q.pop_front();Storing index of each element (This doesn't require knowledge of removeElement) making it independent of original queue
deque<int> q;
int cntAdded = 0, cntRemoved = 0;
// Finding minimum
return q.front().first;
// Adding an element (newElem)
while (!q.empty() && q.back() > newElem) q.pop_back();
q.push_back({newElem, cntAdded});
cntAdded++;
// Removing an element
if (!q.empty() && q.front().second == cntRemoved) q.pop_front();
cntRemoved++;Heap like idea of swapping with last element while deleting
class RandomizedSet {
public:
unordered_map<int, int> rec;
vector<int> arr;
default_random_engine seed;
RandomizedSet()
{
rec.clear();
arr.clear();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool insert(int val)
{
if (rec.find(val) != rec.end()) return false;
rec[val] = arr.size();
arr.push_back(val);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
bool remove(int val)
{
if (rec.find(val) == rec.end()) return false;
arr[rec[val]] = arr.back();
rec[arr.back()] = rec[val];
arr.pop_back();
rec.erase(val);
return true;
}
/** Get a random element from the set. */
int getRandom()
{
int rand = uniform_int_distribution<>(0, arr.size()-1)(seed);
return arr[rand];
}
};for (int i = 0; i < A.n; i++)
{
for (int j = 0; j < B.m; j++)
{
res[i][j] = 0;
for (int k = 0; k < A.m; k++)
res[i][j] += A[i][k] * B[k][j];
}
}Stressan's Divide and Conquer approach
Pad zeroes in case of non 2 power matrix
- Each row can have <= m number of elements. We will keep track of vals and cols of those non-zero entries.
- Size of non-zero elements in a row will be stored in rows (see get function)
template<typename T>
class SparseMatrix
{
private:
vector<T> *vals;
vector<T> *rows, *cols;
public:
int n, m;
SparseMatrix(int _n, int _m)
{
assert(_n > 0 && _m > 0);
n = _n, m = _m;
vals = NULL, cols = NULL;
rows = new vector<int>(n+1, 1);
}
~SparseMatrix()
{
if (vals)
{
delete vals;
delete cols;
}
delete cols;
}
T get(int i, int j) const
{
assert(i >= 1 && j >= 1 && i <= n && j <= m);
for (int pos = ((*rows)[i-1] - 1); pos < ((*rows)[i] - 1); ++pos)
{
int curCol = (*cols)[pos];
if (curCol == j) return (*vals)[pos];
else if (curCol > j) break;
}
return T();
}
SparseMatrix& set(T val, int i, int j)
{
assert(i >= 1 && j >= 1 && i <= n && j <= m);
int pos = (*rows)[i-1] - 1, curCol = 0;
for (; pos < (*rows)[i] - 1; ++pos)
{
curCol = (*cols)[pos];
if (curCol >= j) break;
}
if (curCol != j && val != T()) insert(pos, i, j, val);
else if (val == T()) remove(pos, i);
else (*vals)[pos] = val;
return *this;
}
SparseMatrix<T> multiply(const SparseMatrix<T> &x) const
{
assert (m == x.n);
SparseMatrix<T> res(n, x.m);
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= x.m; ++j)
{
T cur = T();
for (int k = 1; k <= m; ++k)
cur += get(i, k) * x.get(k, j);
res.set(cur, i, j);
}
}
return res;
}
private:
void insert(int index, int i, int j, T val)
{
if (!vals)
{
vals = new vector<T>(1, val);
cols = new vector<int>(1, j);
}
else
{
vals->insert(vals->begin() + index, val);
cols->insert(cols->begin() + index, j);
}
for (int x = i; x <= n; ++x) (*rows)[x] += 1;
}
void remove(int index, int i)
{
vals->erase(vals->begin() + index);
cols->erase(cols->begin() + index);
for (int x = i; x <= n; ++x) (*rows)[x] -= 1;
}
};class NestedIterator {
public:
stack<vector<NestedInteger>::iterator> front, back;
NestedIterator(vector<NestedInteger> &nestedList)
{
front.push(nestedList.begin());
back.push(nestedList.end());
}
int next()
{
return (front.top()++)->getInteger();
}
bool hasNext()
{
while (!front.empty())
{
auto it = front.top();
if (it == back.top())
{
front.pop(); back.pop();
if (!front.empty()) front.top()++;
}
else if (it->isInteger()) return true;
else
{
front.push(it->getList().begin());
back.push(it->getList().end());
}
}
return false;
}
};/* LRU = Least Recently Used Cache
say a cache of size 4 we insert 0 then 1 then 2 then 3 i.e our cache becomes
3 2 1 0 if we insert another item size becomes 5 we can only have a capacity of 4
so while insertion least recently used gets deleted i.e. 4 3 2 1 [0 gets deleted]
If we access say 2 then it becomes 2 4 3 1 Now if we insert 5, 1 gets removed
i.e. 5 2 4 3 this get & set function should be in O(1) */
class LRUCache {
private:
struct Node { int key, val; Node *prev, *next; };
unordered_map<int, Node*> rec;
Node *head, *tail;
int sz, maxCapacity;
public:
LRUCache(int capacity)
{
head = NULL, tail = NULL;
sz = 0, maxCapacity = capacity;
}
void put(int key, int value)
{
if (rec.find(key) == rec.end())
{
Node *newNode = new Node({key, value, NULL, NULL});
rec[key] = newNode;
if (!head && !tail) head = newNode, tail = newNode;
else
{
newNode->next = head;
head->prev = newNode;
head = newNode;
}
sz++;
if (sz > maxCapacity)
{
Node *toDel = tail;
tail = tail->prev;
if (tail) tail->next = NULL;
rec.erase(toDel->key);
delete (toDel);
sz--;
}
}
else
{
get(key);
rec[key]->val = value;
}
}
int get(int key)
{
auto it = rec.find(key);
if (it != rec.end())
{
Node *newHead = it->second;
if (newHead == head) return newHead->val;
Node *p = newHead->prev, *q = newHead->next;
if (p) p->next = q;
if (q) q->prev = p;
if (newHead == tail) tail = p;
newHead->next = head;
newHead->prev = NULL;
head->prev = newHead;
head = newHead;
return newHead->val;
}
else return -1;
}
};class LFUCache {
private:
struct Node { int key, value, freq; list<int>::const_iterator it; };
int maxCapacity, minFrequency;
unordered_map<int, Node> nodeByKey;
unordered_map<int, list<int>> nodeKeysListByFrequency;
public:
LFUCache(int capacity): maxCapacity(capacity), minFrequency(0) {}
int get(int key) {
if (nodeByKey.find(key) == nodeByKey.end()) return -1;
Node& node = nodeByKey[key];
updateFrequency(node);
return node.value;
}
void put(int key, int value) {
if (maxCapacity == 0) return;
if (nodeByKey.find(key) != nodeByKey.end()) {
Node& node = nodeByKey[key];
node.value = value;
updateFrequency(node);
return;
}
if (nodeByKey.size() == maxCapacity) {
const int requiredKey = nodeKeysListByFrequency[minFrequency].back();
nodeKeysListByFrequency[minFrequency].pop_back();
nodeByKey.erase(requiredKey);
}
minFrequency = 1;
nodeKeysListByFrequency[1].push_front(key);
nodeByKey[key] = {key, value, 1, cbegin(nodeKeysListByFrequency[1])};
}
private:
void updateFrequency(Node& node) {
int prevFreq = node.freq, newFreq = ++node.freq;
nodeKeysListByFrequency[prevFreq].erase(node.it);
if (nodeKeysListByFrequency[prevFreq].empty()) {
nodeKeysListByFrequency.erase(prevFreq);
if (prevFreq == minFrequency) ++minFrequency;
}
nodeKeysListByFrequency[newFreq].push_front(node.key);
node.it = cbegin(nodeKeysListByFrequency[newFreq]);
}
};class Twitter {
public:
unordered_map<int, vector<pair<int, int>>> rec;
unordered_map<int, unordered_set<int>> followers;
int timer = 0;
Twitter() { rec.clear(); followers.clear(); timer = 0; }
void postTweet(int userId, int tweetId) { rec[userId].push_back({++timer, tweetId}); }
void follow(int followerId, int followeeId)
{
if (followerId == followeeId) return;
followers[followerId].insert(followeeId);
}
void unfollow(int followerId, int followeeId)
{
if (followerId == followeeId) return;
followers[followerId].erase(followeeId);
}
vector<int> getNewsFeed(int userId)
{
vector<pair<int, int>> tmp;
for (auto &y : rec[userId]) tmp.push_back(y);
for (auto &x : followers[userId])
for (auto &y : rec[x]) tmp.push_back(y);
int sz = min(10, (int)tmp.size());
partial_sort(tmp.begin(), tmp.begin()+sz, tmp.end(), greater<pair<int, int>>());
vector<int> res;
for (int i = 0; i < sz; ++i)
res.push_back(tmp[i].second);
return res;
}
};- Sort numbers find median, we can maintain sorted array while addNum it will take O(logN) time in lower_bound and worst case all numbers have to be shifted so O(NlogN)
// Avg case logN, but worst case linear
vector<int> arr;
int sz = 0;
MedianFinder() { }
void addNum(int num)
{
sz++;
if (arr.empty()) arr.push_back(num);
else arr.insert(lower_bound(arr.begin(), arr.end(), num), num);
}
double findMedian()
{
return sz&1 ? arr[sz/2] : (arr[sz/2 + 1] + arr[sz/2])/2.0;
}- Maintain two heaps i.e. left and right half from middle. We are performing 3 push and 2 pop operations making it total O(5logN)
priority_queue<int> left;
priority_queue<int, vector<int>, greater<int>> right;
MedianFinder() { }
// LogN Solution
/* Think 3 steps: sz(left) == sz(right), sz(left) > sz(right), sz(left) < sz(right) */
void addNum(int num)
{
left.push(num);
right.push(left.top());
left.pop();
if (left.size() < right.size())
{
left.push(right.top());
right.pop();
}
}
double findMedian()
{
return (left.size() > right.size()) ? left.top() : (left.top() + right.top())/2.0;
}- We can use policy based data structure, both insertion and find takes logN & 3logN time here but there's no overhead of inserting 5 times so this might perform better in some scenerios
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> orderedMultiSet;
class MedianFinder {
public:
orderedMultiSet st;
int n = 0;
MedianFinder() { }
void addNum(int num)
{
st.insert(num);
n++;
}
double findMedian()
{
return n&1 ? *st.find_by_order(n/2) : (*st.find_by_order(n/2 - 1) + *st.find_by_order(n/2))/2.0;
}
};
// Regular set uses a BST internally, red black tree uses a red black tree
// Regular set has this drawback that we cannot do random access, with policy based you can even do that in O(LogN) time
// order_of_key(k) number of items strictly smaller than k
// find_by_order(k) kth element from set counting from zero
/*
A BST is simply whose left node is small and right large. But often BST can end up as skewed (like a linked list)
Solution is balanced trees like AVL or Red black tree which is a type of balanced tree.
- A node is either black or red.
- The root and nil are always black.
- If a node is red its childrens are black.
- All path from its nil descendants contains the same number of black nodes.
*/class MyHashMap {
private:
int hashfunction(int key)
{
return key&127; // negative num % 128 may give negative val, but & 127 won't
}
vector<pair<int, int>> data[128];
public:
MyHashMap() { for (auto &x : data) x.clear(); }
void put(int key, int value)
{
int hash = hashfunction(key);
for (auto &x : data[hash])
if (x.first == key) { x.second = value; return; }
data[hash].push_back({key, value});
}
int get(int key)
{
int hash = hashfunction(key);
for (auto &x : data[hash])
if (x.first == key) return x.second;
return -1;
}
void remove(int key)
{
int hash = hashfunction(key);
for (int i = 0; i < data[hash].size(); ++i)
if (data[hash][i].first == key) { data[hash].erase(data[hash].begin() + i); break; }
}
};class MyCalendar {
public:
set<pair<int, int>> st1, st2;
MyCalendar() { }
bool book(int s, int e)
{
/*
--- case 1 ----- avoid case 1
======= ======
------ case 2 ------ avoid case 2
===== ======
------ case 3
======
-------------- case 4
======
Above cases can be concluded in two lines:
- find a booking with start atleast s+1 if it's start < e
then it's an overlap
- find a booking with end atleast s+1 if it's start < e */
auto it1 = st1.lower_bound({s+1, INT_MIN});
if (it1 != st1.end() && it1->first < e) return false;
auto it2 = st2.lower_bound({s+1, INT_MIN});
if (it2 != st2.end() && it2->second < e) return false;
st1.insert({s, e});
st2.insert({e, s});
return true;
}
};The API: int read4(char *buf) reads 4 characters at a time from a file. The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file. By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file. Note: The read function will only be called once for each test case.
int read(char *buf, int n)
{
int index = 0;
char r4[4];
while (index < n)
{
int c = read4(r4);
for (int i = 0; i < c && index < n; ++i)
buf[index++] = r4[i];
if (c < 4) break;
}
return index;
}/* Previously it was called only once so:
"filetestbuffer"
read(6)
read(5)
Gives output: [6, buf = "filete"] [5, buf = "buffe"]
which is incorrect, now we want output as: [6, buf = "filete"] [5, buf = "stbuf"] */
queue<char> q;
int read(char *buf, int n)
{
int index = 0;
while (!q.empty() && index < n)
{
buf[index++] = q.front();
q.pop();
}
if (index == n) return n;
char r4[4];
while (index < n)
{
int c = read4(r4);
int i = 0;
for (; i < c && index < n; ++i)
buf[index++] = r4[i];
while (i < c) q.push(r4[i++]);
if (c < 4) break;
}
return index;
}class Solution {
public:
string encode(vector<string> &strs)
{
string header = "(", body = "";
for (auto &x : strs)
{
header += to_string(x.size()) + ',';
body += x;
}
header = header.substr(0, header.size()-1) + ')';
return header + body;
}
vector<string> decode(string &str)
{
string header = str.substr(1, str.find(')')-1);
stringstream ss(header);
string tmp;
vector<string> res;
int i = str.find(')')+1;
while (getline(ss, tmp, ','))
{
int sz = stoi(tmp);
res.push_back(str.substr(i, sz));
i += sz;
}
return res;
}
};We could use tries also but that would be less optimal (can't guess in 10 options)
void findSecretWord(vector<string>& wordlist, Master& master)
{
vector<string> words = wordlist;
for (int i = 0; i < 10; ++i)
{
string guess = words[rand()%words.size()];
int matches = master.guess(guess);
if (matches == 6)
break;
vector<string> newWords;
for (const string cur : words)
{
int curMatches = 0;
for (int j = 0; j < 6; ++j)
if (guess[j] == cur[j]) curMatches++;
if (curMatches == matches)
newWords.push_back(cur);
}
words = newWords;
}
}class Solution {
public:
vector<pair<int, int>> directions = {{1, -1}, {1, 0}, {1, 1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}};
bool valid(int x, int y, vector<vector<char>> b)
{
return x >= 0 && x < b.size() && y >= 0 && y < b[0].size();
}
void dfs(vector<vector<char>>& board, int i, int j)
{
if (!valid(i, j, board)) return;
if (board[i][j] == 'E')
{
int cnt = 0;
for (const auto dir : directions)
{
if (valid(i + dir.first, j + dir.second, board) && board[i + dir.first][j + dir.second] == 'M')
cnt++;
}
if (cnt > 0) board[i][j] = ('0' + cnt);
else
{
board[i][j] = 'B';
for (const auto dir : directions) dfs(board, i + dir.first, j + dir.second);
}
}
}
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click)
{
if (board[click[0]][click[1]] == 'M') { board[click[0]][click[1]] = 'X'; return board; }
dfs(board, click[0], click[1]);
return board;
}
};map<int, int> mp;
MyCalendarTwo() { mp.clear(); }
bool book(int start, int end)
{
int cnt = 0;
mp[start]++, mp[end]--;
for (auto it = mp.begin(); it != mp.end(); ++it)
{
cnt += it->second;
if (cnt == 3) { mp[start]--, mp[end]++; return false; }
}
return true;
}#include <bits/stdc++.h>
using namespace std;
template<typename T>
class Vector
{
private:
T* m_Data = nullptr;
size_t m_Size, m_Capacity;
public:
Vector() : m_Size(0), m_Capacity(0) { ReAlloc(2); }
void pushBack(const T& value)
{
if (m_Size >= m_Capacity)
ReAlloc(m_Capacity + m_Capacity/2); // growing fx depends on use case
m_Data[m_Size++] = value;
}
void popBack()
{
if (m_Size > 0)
{
m_Size--;
m_Data[m_Size].~T();
}
}
T& operator[](size_t index)
{
assert(index >= 0 && index < m_Size);
return m_Data[index];
}
size_t size() const { return m_Size; }
~Vector() { delete[] m_Data; }
// Improvements
// this new fxn moves temp data provided as arg and moves instead of copy
void pushBack(T&& value)
{
if (m_Size >= m_Capacity)
ReAlloc(m_Capacity + m_Capacity/2);
m_Data[m_Size++] = std::move(value);
}
template<typename... Args>
T& emplaceBack(Args&&... args)
{
if (m_Size >= m_Capacity)
ReAlloc(m_Capacity + m_Capacity/2);
m_Data[m_Size] = T(std::forward<Args>(args)...);
return m_Data[m_Size++];
}
// End of Improvements
private:
void ReAlloc(size_t newCapacity)
{
/* Functions: Allocate new block of memory, copy/move existing
data, delete old memory block */
T* newBlock = new T[newCapacity];
// don't use smart pointers when dealing such low level data structure stuff
if (newCapacity < m_Size)
m_Size = newCapacity; // In case of shrinking (after pop)
for (size_t i = 0; i < m_Size; ++i)
newBlock[i] = m_Data[i];
// improvement -> newBlock[i] = std::move(m_Data[i]);
/* why not memcpy? memcpy is fine for simple flot int types but in custom
classes it won't call copy constructor above ensures that it gets called */
delete[] m_Data;
m_Data = newBlock;
m_Capacity = newCapacity;
}
};
// For demo
struct point
{
float x, y, z;
point() {}
point(float _x, float _y, float _z) : x(_x), y(_y), z(_z) { }
~point() { cout << "DESTROY\n"; }
point& operator=(const point& other)
{
cout << "COPY\n";
x = other.x, y = other.y, z = other.z;
return *this;
}
point& operator=(point&& other)
{
cout << "MOVE\n";
x = other.x, y = other.y, z = other.z;
return *this;
}
};
int main()
{
Vector<point> arr;
/* this arg is temp data, which gets constructed then copied then destroy
instead have a T&& method in vector */
arr.pushBack(point(1, 2, 3));
arr.pushBack(point(9, 8, 7));
arr.pushBack(point(0, 1, 0));
arr.popBack();
arr.emplaceBack(1, 2, 3);
for (int i = 0; i < arr.size(); ++i)
cout << arr[i].x << " " << arr[i].y << " " << arr[i].z << '\n';
return 0;
}class SnakeGame
{
private:
size_t curFood;
int width, height;
vector<pair<int, int>> food;
deque<pair<int, int>> snake;
public:
SnakeGame(int _width, int _height, vector<pair<int, int>> _food) :
curFood(0), width(_width), height(_height), food(_food)
{
snake.push_back({0, 0});
}
// direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down
// return the game's score after the move. Return -1 if game over.
int move(string direction)
{
int snakeLen = snake.size();
if (snakeLen > width*height) return -1;
auto snakeHead = snake.front().first;
if (direction == "U") snakeHead.first--;
else if (direction == "D") snakeHead.first++;
else if (direction == "L") snakeHead.second--;
else if (direction == "R") snakeHead.second++;
if (curFood < food.size() && snakeHead == food[curFood]) curFood++;
else snake.pop_back();
if (find(snake.begin(), snake.end(), snakeHead) != snake.end()) return -1;
snake.push_front(snakeHead);
return curFood;
}
};class textEditor
{
private:
stack<char> leftStk, rightStk;
public:
void insertWord(char word[])
{
int i = 0;
while (word[i] != '\0')
insertCharacters(word[i++]);
}
void insertCharacters(char character)
{
leftStk.push(character);
}
bool deleteCharacter()
{
if (rightStk.empty()) return false;
else rightStk.pop();
return true;
}
bool backSpaceCharacter()
{
if (leftStk.empty()) return false;
else leftStk.pop();
return true;
}
void moveCursor(int position)
{
int leftSz = leftStk.size(), rightSz = rightStk.size();
if (position < leftSz) moveLeft(position);
else moveRight(position - leftSz);
}
void moveLeft(int position)
{
int leftSz = leftStk.size();
while (position != leftSz)
{
rightStk.push(leftStk.top());
leftStk.pop();
leftSz--;
}
}
void moveRight(int cnt)
{
int rightSz = rightStk.size(), i = 1;
if (cnt > rightSz) cout << "Cannot move the cursor, right, to the specified position\n";
else
{
while (i <= cnt)
{
leftStk.push(rightStk.top());
rightStk.pop();
i++;
}
}
}
void findAndReplaceChar(char find, char replace)
{
int cnt = 1, originalCharPos = leftStk.size();
moveCursor(0);
while (!rightStk.empty())
{
if (rightStk.top() == find)
{
deleteCharacter();
insertCharacters(replace);
}
else moveCursor(cnt++);
}
moveCursor(originalCharPos);
}
void print()
{
int cnt = 1, originalCharPos = leftStk.size();
moveCursor(0);
while (!rightStk.empty())
{
cout << rightStk.top();
moveCursor(cnt++);
}
moveCursor(originalCharPos);
cout << '\n';
}
};
int main()
{
textEditor editor;
editor.insertWord("Ankit"); editor.insertWord(" Priyarup"); editor.insertWord(" is"); editor.insertWord(" a"); editor.insertWord(" good"); editor.insertWord(" boy!");
editor.insertCharacters(' '); editor.insertCharacters(':'); editor.insertCharacters(')');
editor.print();
editor.moveCursor(0);
editor.insertWord("AP, ");
editor.print();
return 0;
}unordered_map< string, set<pair<int, string>, greater<pair<int, string>>> > rec;
TimeMap() { }
void set(string key, string value, int timestamp)
{
rec[key].insert({timestamp, value});
}
string get(string key, int timestamp)
{
auto it = rec[key].lower_bound({timestamp+1, ""});
if (it != rec[key].end()) return it->second;
return "";
}