- start_date: 08-09-2022
- end_date: ...
-
O(nlogn) or O(n) is basically worst case time complexity. Here it is assumed n is very large. Under such circumstances, your nlogn solution may not be as efficient as an O(n) solution. For example nlogn with a small constant c may sometimes perform better than an O(n) solution with a large enough constant. Lastly, I'd like to mention that nlogn > n is only valid for n>10.
-
Competitive coding solved questions learnings:
- To maximise sum of MEX of all elements in array (i.e picking up elements one by one like 1 element, then 2, then 3... & finding sum of MEX of each...), we have to rearrange array such that all unique elements are put in increasing order & then put all repeated elements at last. Sorting would be used in beginning to do that ~ o(nlogn)
- 1e9+7 would be coprime with all.
- To find max of this equation where a,b are distinct elements of array ~ (ab + a-b); We can rewrite it as: ((a-1)(b-1)+1), ~ hence our a,b should either be first 2 or last 2 elements of the sorted array.
- In array, check if 4 distinct elements in different index exist such that x1+x2=x3+x4; Simply take a map<int,pii> mp, & store m[v[i]+v[j]]={i,j} in a loop (we will be having 2 for loops, one from i to n & inside loop from j to i+1),... and then if we have mp.count(v[i]v[j]) as non 0 means sum found & then we check if mp[...].first or .second exist...
- Only perfect squares have odd no. of factors. Eg: 1,4,9,25...
- XOR a no. 'n' odd/even times -> n^n^n = n ...&... n^n = 0
- Map mp.count(key) return 1 if element is present in the map, else 0.
- Also: auto it = map.rbegin(); it!=map.rend(); ++it ... this will reverse iterate map.
- vectorv(n), initializes a vector of n size with 0s.
- __gcd(n1,n2) gives GCD of 2 numbers. Or using recursive function: return b == 0 ? a : gcd(b, a % b);
- If x has 'a' digits, y has 'b' digits, z has 'c' digits & z is gcd(x,y). In such case to get x,y,z, it's simple: x = pow(10,a-1), similarly y-b relation, z-c relation. Hence if x<y then x,y+z no's ~ meaning pow(10,a-1) will have 'a' digits, y+z ~ pow(10,b-1)+pow(10,c-1) will have 'b' digits & gcd of both will yield some no. that will be having 'c' digits. Similarly for x>=y, we have x+z, y.
- If we have a,b & we can perform operations in a,b by either +/-1 to both a,b, i.e a+1,b+1 or a-1,b-1 & so on; Then to find max(gcd(a,b)) we do: Visualize & you'll realise: gcd(a,b) & gcd(a-b,b) will be same in ideal cases like take example of 50 & 100. In other cases we'll note, gcd can never exceed |a-b|. At max, gcd will be |a-b|, in all cases it will otherwise be less only. Hence with this hint all you have to do with 'a' and 'b' is increase/decrease them in a way that they lie closer to |a-b| since max gcd possible will be that only...
- Arrays are by default passed by reference in a function, unlike vectors where we explicitly pass them that way.
- No. of digits in a number: floor(log10(n)) + 1
- 1 sec time limit is 10^7 computations.
- Branch prediction in sorted/unsorted arr. , Tail Call optimisation,
- To hash negative no's add +100 or a big positive no. & hash it.
- Recursion vs Iteration ~ Both have almost same computation time.. depends on use case though.
- #define - preprocessor token ~ (compiler never interprets), typedef - compiler interprets...
- ...
- ...
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> mp;
vector<int> ans;
for(int i = 0 ; i< nums.size(); i++){
int x = (target-nums[i]); // not using abs() since no. can be negative
if(mp.find(x)!=mp.end()){
// means no. has been found
ans.push_back(i);
ans.push_back(mp[x]);
}
mp[nums[i]] = i;
}
return ans;
/*
for case of not using a map o(n) ~ using sorting + 2 pointer ~ o(nlogn)
int n = nums.size();
vector<pair<int, int>> arr(n);
for (int i = 0; i < n; ++i) {
arr[i] = make_pair(nums[i], i);
}
sort(arr.begin(), arr.end()); // Sort arr in increasing order by their values.
int left = 0, right = n- 1;
while (left < right) {
int sum2 = arr[left].first + arr[right].first;
if (sum2 == target)
return {arr[left].second, arr[right].second};
if (sum2 > target)
right -= 1; // Try to decrease sum2
else
left += 1; // Try to increase sum2
}
return {};
*/
}
};
int closestToZero(int arr[], int n)
{
// below will use sort + 2 pointer approach
sort(arr,arr+n);
int i = 0; int j = n-1;
int sum = 0;
int flag = INT_MAX;
int res;
while(i<j){
sum = arr[i] + arr[j];
if(sum>0) j--;
else if(sum<0) i++;
else return 0;
if(abs(sum)<flag){
flag = abs(sum);
res = sum;
}
/////////////// //
// this is just an edge case in the case of gfg... not actually needed unless explicitly given in question...
else if(abs(sum)==flag){
res = max(res,sum);
}
/////////////////////////////////////
}
return res;
}
class Solution {
public:
bool rotateString(string s, string goal) {
if(s=="" or goal == "") return false;
if(s.length()!=goal.length()) return false;
s = s+s;
if(s.find(goal) != std::string::npos) return true;
else return false;
}
};
bool isRotated(string str1, string str2)
{
if (str1.length() != str2.length())
return false;
if(str1.length()<2){
return str1.compare(str2) == 0;
}
string clock_rot = "";
string anticlock_rot = "";
int len = str2.length();
// Initialize string as anti-clockwise rotation
anticlock_rot = anticlock_rot +
str2.substr(len-2, 2) +
str2.substr(0, len-2) ;
// Initialize string as clock wise rotation
clock_rot = clock_rot +
str2.substr(2) +
str2.substr(0, 2) ;
// check if any of them is equal to string1
return (str1.compare(clock_rot) == 0 ||
str1.compare(anticlock_rot) == 0);
}
- Create a linkedlist
// before writing linkedlist code, first noting the difference between . & -> operator:
class A {
public: int a;
A(){
a = 100;
}
};
main(){
A x = A();
A *y = &A();
A *z = new A();
cout << x.a or y->a or z-> a ~ all of them will give same output
}
////////////////////////////////
// Now ll code
class Node { public:
int data; Node*next ;
Node(int data) {
this->data = data;
next = 0;
}
};
void addFront(Node*&node, int data) {
Node *nn = new Node(data); // //nn->data = data; nn->next = 0;
if (node == 0) {
node = nn; return;
}
nn->next = node;
node = nn;
return;
}
/*
if passed by reference, then use ** ...
eg:
addFront(Node**node, int data) {
Node *nn = new Node(data);
if (*node == 0) {
*node = nn; return;
}
nn->next = *node;
*node = nn;
return;
}
main(){ // passed by reference
addFront(&root, data);
}
*/
void addBack(Node*&node , int data) {
Node*nn = new Node(data);
Node*temp = node;
if (node == 0) {
node = nn; return;
}
while (temp->next) temp = temp->next;
temp->next = nn;
return;
}
void display(Node*head) {
while (head) {
cout << head->data << " ";
head = head->next;
}
}
main() {
Node * root = 0 ;
int n = 5; // nodes...
for (int i = 0 ; i < n ; i++) {
int data; data = i;
addFront(root, data);
// addBack(root, data);
}
display(root);
}
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
// multiply left and right sides...
int t = 1;
vector<int> res(nums.size());
for(int i = 0; i < nums.size(); i++)
{
res[i] = t;
t*=nums[i];
}
t = 1; // re initialising
for(int i = nums.size()-1; i >= 0; i--)
{
res[i] *= t;
t*=nums[i];
}
return res;
}
};
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
// unordered_set<int> s;
// for(auto x:nums) s.insert(x);
// int count = 0;
// for(auto x: nums){
// if(!s.count(x-1)){
// /* if a number one less than x doesn't exist means
// x is the minimum number and know we can move
// upwards and count all the numbers in this
// streak. As if a number less than x existed means
// x is not the minimum so we skip it. We must start
// with minimum number only and move upwards
// to maintain o(n) complexity...
// */
// int num = x;
// int curCount = 1;
// while(s.count(num+1)){
// curCount++;
// num++; // incrementing num...
// }
// count = max(count,curCount);
// }
// }
// return count;
// practice attempt:
// insert operation in set is o(logn)
if(nums.size()==0) return 0;
unordered_set<int> s;
for(auto i: nums) s.insert(i);
// brute force will be to sort the whole array and then find the longest consecutive sequence, which is iterating and checking if a[i] is a[i-1] + 1, means incrementing by 1.. since it wants consecutive, we also maintain a flag which will be holding the max of the count++ we get.....
// coming to optimal approach
// we check the no. and see if count or no. less than that exist... basically jump into the lowest no. and then increment and increase the count...
int count = INT_MIN;
for(auto x: nums){
if(!s.count(x-1)){
int num = x;
int curCount = 1;
while(s.count(num+1)){
curCount++;
num++; // incrementing num...
}
count = max(count,curCount);
}
}
return count;
}
};
int fun(int W, int wt[], int val[], int n, vector<vector<int>> &dp) {
if(W==0 or n==0) return 0;
if(dp[n][W]!=INT_MIN/2) return dp[n][W];
if(wt[n-1]>W) return dp[n][W] = fun(W,wt,val,n-1,dp);
else return dp[n][W] = max(val[n-1]+ fun(W-wt[n-1],wt,val,n-1,dp), fun(W,wt,val,n-1,dp) );
}
int knapSack(int W, int wt[], int val[], int n)
{
vector<vector<int>> dp(n+1, vector<int>(W+1, INT_MIN/2));
return fun(W,wt,val,n,dp);
}
int fun(int W, int wt[], int val[], int n, vector<vector<int>> &dp) {
if(W==0 or n==0) return 0;
if(dp[n][W]!=INT_MIN/2) return dp[n][W];
if(wt[n-1]>W) return dp[n][W] = fun(W,wt,val,n-1,dp);
else return dp[n][W] = max(val[n-1]+ fun(W-wt[n-1],wt,val,n,dp), fun(W,wt,val,n-1,dp) );
}
int knapSack(int N, int W, int val[], int wt[])
{
vector<vector<int>> dp(N+1, vector<int>(W+1, INT_MIN/2));
return fun(W,wt,val,N,dp);
}
int minOperation(int n)
{
int dp[n+1];
dp[0] = 0 ; dp[1] = 1; dp[2] = 2; dp[3] = 3;
for(int i = 1; i <= n ; i++){
if(i&1) dp[i] = 1+ dp[i-1];
else dp[i] = 1 + dp[i/2];
}
return dp[n];
}
class Solution {
public:
int dp[1007][1007];
int fun(vector<vector<int>>&grid,int m,int n)
{
if(m==0 and n==0) return grid[m][n];
else if(m<0 or n<0) return INT_MAX/2;
/* since if m==0 and n!=0 then our path would be moving in the leftward direction everytime ~one direction towards the 0,0..., than zig zag, hence we must put m<0 and n<0 rather than putting a condition like if((m==0 and n!=0) or (m!=0 and n==0))...*/
if(dp[m][n]!=-1) return dp[m][n];
return dp[m][n] = grid[m][n] + min(fun(grid,m-1,n), fun(grid,m,n-1));
}
// practice approach done
int minPathSum(vector<vector<int>>& grid) {
/*
int m = grid.size(); // rows...
int n = grid[0].size();
vector<vector<int>> dp(m,vector<int>(n,0));
dp[0][0] = grid[0][0];
// intialising the rows & columns of dp table...
// rows
for(int i = 1 ; i < m ; i++ )
{
dp[i][0] = dp[i-1][0] + grid[i][0];
}
// cols
for(int j = 1 ; j < n ; j++ )
{
dp[0][j] = dp[0][j-1] + grid[0][j];
}
// now dp
for(int i = 1 ; i < m ; i++)
{
for(int j = 1 ; j < n ; j++){
dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + grid[i][j];
}
}
return dp[m-1][n-1];
*/
int m = grid.size();
int n = grid[0].size();
memset(dp,-1,sizeof(dp));
return fun(grid,m-1,n-1);
/* note that greedy approach won't work...*/
// approach for practice
//done
}
};
bool compare(Item a, Item b){
double x = (double)a.weight/(double)a.value;
double y = (double)b.weight/(double)b.value;
return x>y;
}
double fractionalKnapsack(int W, Item arr[], int n)
{
sort(arr,arr+n,compare);
double ans = 0.0;
int wt = 0;
for(int i = 0 ; i < n ; i++){
if(wt + arr[i].weight <=W){
wt += arr[i].weight;
ans += arr[i].value;
}
else{
int x = W - wt;
double val = (double) x * (arr[i].value)/(double) arr[i].weight;
ans+=val;
break;
}
}
return ans;
}
- Finding MEX of array- https://www.geeksforgeeks.org/find-the-prefix-mex-array-for-given-array/
# MEX of an array refers to the smallest missing non-negative integer of the array.
fun(vector<int> v, int n ){
int mxe = *max_element(v.begin(), v.end())
set<int> s;
for(int i = 0 ; i <= mxe+1; i++){
s.insert(i);
}
vector<int> ans;
for(int i = 0 ; i < v.size(); i++)
{
if(s.find(v[i]) != s.end()){
s.erase(v[i]);
}
ans.push_back(*s.begin());
}
return ans;
}
void recur(vector<int>& arr, int target, vector<int> &ds , vector<vector<int>>& ans,int ind){
if(ind==arr.size()) {
if(target==0) ans.push_back(ds);
return;
}
if(arr[ind]<=target){
ds.push_back(arr[ind]);
recur(arr,target-arr[ind],ds,ans,ind);
ds.pop_back();
}
recur(arr,target,ds,ans,ind+1);
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
// **********SORT**********
sort(candidates.begin(), candidates.end());
vector<vector<int>> ans;
vector<int> ds;
int ind = 0 ;
recur(candidates,target,ds,ans,ind);
return ans;
}
void recur(vector<int>& arr, int target, vector<int> &ds , vector<vector<int>>& ans,int ind){
if(target==0){
ans.push_back(ds);
return;
}
for(int i = ind ; i < arr.size();i++){
if(i>ind and arr[i]==arr[i-1]) continue;
if(arr[i]<=target){
ds.push_back(arr[i]);
recur(arr,target-arr[i],ds,ans,i+1);
ds.pop_back();
}
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> ds;
int ind = 0 ;
sort(candidates.begin(),candidates.end());
recur(candidates,target,ds,ans,ind);
return ans;
}
// void fun(vector<int>& nums, int i, vector<int>& sub, vector<vector<int>>& subs) {
// subs.push_back(sub);
// for (int j = i; j < nums.size(); j++) {
// sub.push_back(nums[j]);
// subsets(nums, j + 1, sub, subs);
// sub.pop_back();
// }
// }
vector<vector<int>> subsets(vector<int>& nums) {
// vector<int> temp;
// vector<vector<int>> ans;
// using bits
// int n = nums.size();
// for(int i = 0 ; i < (1<<n); i++ )
// {
// for(int j = 0 ; j < n;j++){
// if(i&(1<<j)) temp.push_back(nums[j]);
// }
// ans.push_back(temp);
// temp.clear();
// }
// return ans;
// iterative approach
vector<vector<int>> ans;
ans.push_back({});
for(auto x:nums){
int n = ans.size();
for(int i = 0 ; i < n ;i++){
ans.push_back(ans[i]);
ans.back().push_back(x);
}
}
return ans;
}
// recursive approach
void fun(vector<vector<int>>& res, vector<int>& temp, vector<int>& nums, int ind){
res.push_back(temp);
for(int i=ind; i<nums.size(); ++i){
temp.push_back(nums[i]);
fun(res, temp, nums, i + 1);
temp.pop_back();
}
}
void fun(vector<vector<int>> &ans, vector<int> nums, vector<int> & temp, int ind){
ans.push_back(temp);
for(int i=ind; i < nums.size(); i++){
if(i!=ind and nums[i]==nums[i-1]) continue; // if same element... to prevent duplicate..
temp.push_back(nums[i]);
fun(ans,nums,temp,i+1);
temp.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> ans;
int ind =0;
vector<int> temp;
// ...SORT THE ARRAY TO EASILY CHECK ON DUPLICATES... //
sort(nums.begin(),nums.end());
fun(ans, nums, temp, ind);
return ans;
}
void fun(vector<vector<int>>&ans, vector<int> nums, int l, int r){
if(l==r){
ans.push_back(nums);
return;
}
for(int i = l ; i <= r;i++ )
{
swap(nums[i],nums[l]);
fun(ans, nums, l+1, r);
swap(nums[i],nums[l]);
}
return;
}
int findMaxLength(vector<int>& nums) {
for(int i = 0 ; i < nums.size();i++)
{
if(nums[i]==0) nums[i]=-1;
}
int r = 0 ; int sum = 0 ;
unordered_map<int,int> mp;
mp[0] = -1; // initialised for 0 sum
for(int i = 0; i< nums.size(); i++){
sum+=nums[i];
// if(sum==0) r = max(r,i);
if(mp.find(sum)!=mp.end()){
r = max(r,i-mp[sum]); // this actually works because say in along array, if the sum is same at 2 different points while we iterate means, between the 2 points, the sum is gonna be 0... thats why we derived at same sum for 2 different points.
}
else mp[sum] = i;
}
return r;
}
int maxArea(vector<int>& height) {
int l,r;
l = 0 ; r = height.size()-1;
int ar = INT_MIN;
while(l<r){
ar = max(ar,abs(r-l)*min(height[l],height[r]));
if(height[l]<height[r]) l++;
else if(height[l]>height[r]) r--;
else{
l++;r--;
}
}
return ar;
}
ListNode* swapNodes(ListNode* head, int k) {
ListNode* l = head;
ListNode* r = head;
ListNode* curr = head;
int count = 1;
while(curr){
if(count<k) l = l->next;
if(count>k) r = r->next;
curr = curr->next;
count++;
}
swap(l->val, r->val);
return head;
}
int threeSumMulti(vector<int>& arr, int target) {
unordered_map<int,int>mp;
int k = 0;
int sum=0;
for(int i = 0; i<arr.size();i++){
k+=mp[target-arr[i]];
for(int j = 0;j<i;j++){
sum = arr[j]+arr[i];
mp[sum]++;
}
}
return k;
}
vector<int> dailyTemperatures(vector<int>& temperatures) {
// it is using the logic of nearest greatest to right ~ NGR logic
vector<int> arr(temperatures);
int n = temperatures.size();
vector<int> ans;
stack<pair<int,int>> st;
ans.push_back(0);
st.push({arr[n-1],n-1});
for(int i = n-2; i>=0; i--)
{
if(!st.empty() and arr[i]<st.top().first){
int x = abs(i-st.top().second);
ans.push_back(x);
}
else{
while(!st.empty() and arr[i]>=st.top().first) st.pop();
if(!st.empty() and arr[i]<st.top().first) {
int x = abs(i-st.top().second);
ans.push_back(x);
}
else ans.push_back(0);
}
st.push({arr[i],i});
}
reverse(ans.begin(), ans.end());
return ans;
}
bool canJump(vector<int>& nums) {
int ind = 0;
for(int i = 0; i < nums.size(); i++){
if(i>ind) return false;
ind = max(ind, i+nums[i]);
}
return true;
}
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<vector<int>>arr(flights);
vector<int> dist(n,1e7);
dist[src] = 0;
for(int i = 0 ; i < k+1; i++){
// doing k+1 since, thats how it will work...~ bellman ford
vector<int> temp(dist);
for(auto j:arr){
int a,b,d; // point a to b with distance d
a=j[0]; b=j[1]; d=j[2];
temp[b] = min(temp[b], dist[a] + d );
}
dist = temp;
}
return dist[dst]==1e7?-1:dist[dst];
}
bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
vector<vector<int>>arr(triplets);
// we will check if elements in the triplets are less than equal to target elements, else if greater then the condition to take max() will lead to wrong elements being selected & later will yield false...
int f,s,t; // first,second,third
f=s=t=0;
for(auto i:arr){
if(i[0]<=target[0] and i[1]<=target[1] and i[2]<=target[2]){
f=max(f,i[0]);
s=max(s,i[1]);
t=max(t,i[2]);
}
}
return (f==target[0] and s==target[1] and t==target[2])?true:false;
}
bool compare(vector<int>&a, vector<int>&b){
return a[1]<b[1];
}
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int remove = 0;
vector<vector<int>>arr(intervals);
sort(arr.begin(), arr.end(), compare);
if(arr.size()==0) return 0;
vector<int> x = arr[0];
for(auto i:arr){
if(i[0]<x[1]) remove++;
else {
x=i;
}
}
return --remove;// subtracting, since think of case when only 2 arr..given...
}
};
class Twitter {
unordered_map<int, unordered_map<int,int>> follow_node;
vector<pair<int,int>> post;
public:
Twitter() {}
void postTweet(int userId, int tweetId) {
// post.push_back({userId, tweetId});
post.push_back(make_pair(userId, tweetId));
}
vector<int> getNewsFeed(int userId) {
vector<int> news;
int count = 0; // since only top 10 tweets to retrieve according to question
for(int i = post.size()-1; i>=0 and count<10; i--){
if(post[i].first==userId || follow_node[userId][post[i].first]){
// 2 conditions in `if` since give: Each item in the news feed must be posted by users who the user followed or by the user themself.
news.push_back(post[i].second);
count++;
}
}
return news;
}
void follow(int followerId, int followeeId) {
follow_node[followerId][followeeId] =1;
}
void unfollow(int followerId, int followeeId) {
follow_node[followerId][followeeId] =0;
}
};
/**
* Your Twitter object will be instantiated and called as such:
* Twitter* obj = new Twitter();
* obj->postTweet(userId,tweetId);
* vector<int> param_2 = obj->getNewsFeed(userId);
* obj->follow(followerId,followeeId);
* obj->unfollow(followerId,followeeId);
*/
int carFleet(int target, vector<int>& position, vector<int>& speed) {
// if(position.empty() or speed.empty()) return 0;
// priority_queue<vector<double>> pq; // max heap
// int n = position.size();
// for(int i = 0 ; i < n; i++)
// {
// double time = (double)abs(target-position[i])/speed[i];
// double pos = (double)abs(position[i]);
// double spd = (double)speed[i];
// pq.push({pos,spd,time});
// }
// int fleet = 0 ;
// while(true){
// if(pq.size()==1){
// fleet++; break;
// }
// auto ahead = pq.top();
// pq.pop();
// auto behind = pq.top();
// pq.pop();
// if(ahead[2]>=behind[2]){
// // means time taken by car ahead, since our queue is storing/sorting based on distance is more means low speed & then means car behind can overtake car ahead
// // if it can overtake means they may end up becoming a fleet, so we must drop car behind, since when car behind merges with car ahead, the speed will be that of car ahead which is low speed for both cars now...
// pq.push(ahead);
// }
// else{
// fleet++;
// pq.push(behind);
// }
// }
// return fleet;
// other approach is play with the time......
vector<pair<int,double>> v; // having position & time, position used to sort the whole list in order & time used to find the fleet
int n = position.size();
for(int i = 0 ; i < n; i++)
{
double time = (double)abs(target-position[i])/speed[i];
int pos = position[i];
v.push_back({pos,time});
}
sort(v.begin(), v.end());
double xtime = 0; int fleet = 0;
// iterate backwards
for(int i = n-1; i>=0; i--){
auto t = v[i].second-xtime;
if(t>0){
fleet++;
xtime+=t;
}
}
return fleet;
}
int minEatingSpeed(vector<int>& piles, int h) {
long low = 1;
long high = *max_element(piles.begin(), piles.end());
// now binary search
while(low<=high){
long mid = (low+high)/2;
long time = 0;
for(auto i:piles){
time+=ceil((double)i/mid);
}
if(time>h)low = mid+1;
else high = mid-1;
}
return low;
// complexity: o(log(max n)*n);
}
class SeatManager {
public:
// note that we can also use priority queue...
set<int> s;
SeatManager(int n) {
for(int i = 1 ; i <=n ; i++){
s.insert(i);
}
}
int reserve() {
auto x = *begin(s);
s.erase(x);
return x;
}
void unreserve(int seatNumber) {
s.insert(seatNumber);
}
};
int hardestWorker(int n, vector<vector<int>>& logs) {
int id = logs[0][0]; int lt = logs[0][1]; // id & leaveTime
int diff;
for(int i = 0; i < logs.size()-1; i++)
{
diff = logs[i+1][1]-logs[i][1];
if(diff>lt){
lt = diff;
id = logs[i+1][0];
}
else if(diff==lt) id = min(id,logs[i+1][0]); // return minimum id
}
return id;
}
vector<int> findArray(vector<int>& pref) {
vector<int> ans(pref.size());
ans[0]= pref[0];
for(int i = 1 ; i < pref.size(); i++){
ans[i] = pref[i]^pref[i-1];
}
// note that since pref[i] = pref[i-1] ^ A[i] should be true, hence ~ pref[i] ^ pref[i-1] = A[i]
return ans;
}
bool pal(string s, int i, int j){
while(i<=j){
if(s[i++]!=s[j--]) return false;
}
return true;
}
void fun(int index, string s, vector<vector<string>>& ans, vector<string> &temp ){
if(index==s.length()){
ans.push_back(temp);
return;
}
for(int i = index ; i < s.length(); i++){
if(pal(s,index,i)){
temp.push_back(s.substr(index, i-index+1));
fun(i+1, s,ans,temp);
temp.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> ans;
vector<string> temp;
int index = 0;
fun(index,s, ans,temp);
return ans;
}
void fun(TreeNode* root, int target, vector<int> temp, vector<vector<int>> &ans){
if(root==0) return;
temp.push_back(root->val);
if(root->left==0 and root->right==0 and target==root->val) ans.push_back(temp);
fun(root->left, target-root->val, temp, ans);
fun(root->right, target-root->val, temp, ans);
temp.pop_back();
return;
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<int> temp;
vector<vector<int>> ans;
fun(root, targetSum, temp, ans);
return ans;
}
void fun(int i, int j, string s, vector<string>& vs){
while(i>=0 and j<s.length() and s[i]==s[j]){
vs.push_back(s.substr(i,j-i+1));
i--;j++;
}
}
int countSubstrings(string s) {
if(s.length()==0) return 0;
vector<string> vs;
for(int i = 0 ; i < s.length(); i++){
fun(i,i,s, vs);
// if(i<=s.length()-1)
fun(i,i+1,s, vs);
}
return vs.size();
}
/*
// Using dp
string s;
vector<vector<int>>dp;
int f(int l , int r){
if(l>r)return 1;
if(l==r)return 1;
if(dp[l][r]!=-1)return dp[l][r];
if(s[l]!=s[r])return dp[l][r]=0;
if(f(l+1,r-1))return dp[l][r]=1;
return dp[l][r]=0;
}
int countSubstrings(string s) {
this->s=s;
int ans=0,n=s.size();
dp.resize(n,vector<int>(n,-1));
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
ans+=f(i,j);
}
}
return ans;
}
*/