LeetCode, GeeksForGeeks Problem of the day solution
Відкрити в Telegram
Complete daily challenges from LeetCode, GeeksForGeeks and redeem their rewards Channel link : https://t.me/leetcode_gfg_potd
Показати більше1 250
Підписники
+224 години
+147 днів
+2930 день
Архів дописів
class Solution {
public:
string smallestFromLeaf(TreeNode* root) {
priority_queue<string, vector<string>, greater<string>> pq;
dfs(root, pq, "");
return pq.top();
}
void dfs(TreeNode* root, priority_queue<string, vector<string>, greater<string>>& pq, string cur) {
if (root) {
cur += (root->val + 'a');
if (!root->left && !root->right) {
reverse(begin(cur), end(cur));
pq.push(cur);
}
dfs(root->left, pq, cur);
dfs(root->right, pq, cur);
}
}
};
class Solution{
public:
int merge(int arr[], int st, int mid, int en, int n){
int n1 = mid-st+1;
int n2 = en-mid;
vector<int> v1(n1); // left array
vector<int> v2(n2); // right array
int cnt = 0;
int k = 0;
for(int i=st; i<=mid; i++){
v1[k++] = arr[i];
}
k = 0;
for(int i=mid+1; i<=en; i++){
v2[k++] = arr[i];
}
k = st;
int pt1 = 0, pt2 = 0;
while(pt1<n1 && pt2<n2){
if(v1[pt1]>v2[pt2]){
arr[k++] = v2[pt2];
cnt += n1-pt1; // adding number of times v2[pt2] can be less than elements in the left
pt2++;
}
else{
arr[k++] = v1[pt1];
pt1++;
}
}
while(pt1<n1){
arr[k++] = v1[pt1];
pt1++;
}
while(pt2<n2){
arr[k++] = v2[pt2];
pt2++;
}
return cnt;
}
int mergeSort(int arr[], int n, int l, int r){
if(l>=r) return 0;
int mid = (l+r)/2;
int cnt = 0;
cnt += mergeSort(arr, n, l, mid);
cnt += mergeSort(arr, n, mid+1, r);
cnt += merge(arr, l, mid, r, n);
return cnt;
}
int countPairs(int arr[] , int n )
{
// Your code goes here
for(int i=0; i<n; i++){
arr[i] *= i;
}
int ans = mergeSort(arr, n, 0, n-1);
return ans;
}
};
class Solution {
public:
TreeNode* addOneRow(TreeNode* root, int val, int depth) {
if(!root)
return new TreeNode(val);
if(depth==1){
TreeNode* ans=new TreeNode(val);
ans->left=root;
return ans;
}
queue q;
q.push(root);
int l=0;
while(lleft){
q.push(curr->left);
}
if(curr->right){
q.push(curr->right);
}
}
l++;
}
while(!q.empty()){
TreeNode* curr=q.front();
q.pop();
TreeNode* ans1=new TreeNode(val);
TreeNode* ans2=new TreeNode(val);
TreeNode* p=curr->left;
TreeNode* q=curr->right;
curr->left=ans1;
curr->right=ans2;
ans1->left=p;
ans2->right=q;
}
return root;
}
};
class Solution {
public:
int minimizeDifference(int n, int k, vector &arr) {
vector post_max(n);
vector post_min(n);
post_min[n-1] = arr[n-1];
post_max[n-1] = arr[n-1];
for(int i = n-2; i>= 0; --i) {
post_max[i] = max(arr[i] , post_max[i+1]);
post_min[i] = min(arr[i] , post_min[i +1]);
}
int min_diff = post_max[k] - post_min[k];
int p_min = arr[0];
int p_max = arr[0];
for( int i = 1; i
class Solution {
public:
int res=0;
void rec(TreeNode* root,int ans){
if (root->left==NULL && root->right==NULL) {
res+=ans;
ans-=root->val;
return ;
}
if(root->left!=NULL) rec(root->left,ans*10+root->left->val);
if(root->right!=NULL) rec(root->right,ans*10+root->right->val);
}
int sumNumbers(TreeNode* root) {
rec(root,root->val);
return res;
}
};
class Solution {
public:
vector countElements(vector &a, vector &b, int n, vector &query,int q) {
vectorans;
sort(b.begin(),b.end());
for(int i=0;i
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if(!root){
return 0;
}
queue que;
que.push(root);
int sum=0;
while(!que.empty()){
for(int i =0 ; i< que.size() ; i++){
TreeNode* node=que.front();
que.pop();
if(node->left){
if(node->left->left==NULL and node->left->right==NULL){
sum+=node->left->val;
}
que.push(node->left);
}
if(node->right){
que.push(node->right);
}
}
}
return sum;
}
};
class Solution {
public:
void printArr(int n, int arr[]) {
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout <res;
for(int i=0;i
class Solution {
public:
int largestRectangleArea(vector<int> height){
stack<int> st;
int maxi = 0;
int n=height.size();
for(int i=0;i<=n;i++){
while(st.empty()==false && (i==n || height[st.top()]>=height[i])){
int tempHeight = height[st.top()];
st.pop();
int width;
if(st.empty()==true){
width = i;
}
else{
width = i - st.top() - 1;
}
maxi = max(maxi, width*tempHeight);
}
st.push(i);
}
return maxi;
}
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<int> height(n, 0);
int maxArea = 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]=='1'){
height[j]++;
}
else{
height[j] = 0;
}
}
int tempMaxArea = largestRectangleArea(height);
maxArea = max(maxArea, tempMaxArea);
}
return maxArea;
}
};
class Solution {
public:
long long reversedBits(long long x) {
int i =0;
long long ans =0;
while(x!=0){
if(x%2!=0){
ans+=pow(2,31-i);
}
i++;
x/=2;
}
return ans;
}
};
