Scribd
Upload
65 views8 pages

Dynamic Programming Problem Solutions

The document contains a comprehensive list of various coding problems and solutions from platforms like LeetCode and InterviewBit, categorized by different data structures and algorithms such as Dynamic Programming, Hashmaps, Priority Queues, and more. Each entry includes links to specific problems, often with descriptions and potential strategies for solving them. The document serves as a resource for programmers looking to enhance their problem-solving skills across a wide range of topics.

Uploaded by

Rohith Nalluri
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
65 views8 pages

Dynamic Programming Problem Solutions

The document contains a comprehensive list of various coding problems and solutions from platforms like LeetCode and InterviewBit, categorized by different data structures and algorithms such as Dynamic Programming, Hashmaps, Priority Queues, and more. Each entry includes links to specific problems, often with descriptions and potential strategies for solving them. The document serves as a resource for programmers looking to enhance their problem-solving skills across a wide range of topics.

Uploaded by

Rohith Nalluri
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

DP

[Link]
e-breakdown/. IMP
[Link]
[Link]
[Link] IMP
[Link] IMP
[Link]
[Link]
a-c-python-dp-o-nk/
[Link]
[Link]
[Link]
[Link]
[Link]
r_dp_videos&utm_source=youtube&utm_medium=affiliate&utm_campaign=striver_dp_videos
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
ks&itm_medium=article&itm_campaign=bottom_sticky_on_article
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
=daily-question&envId=2024-08-17
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
Id=2024-10-31
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
​
​
Hashmaps
[Link]
[Link]
[Link]
​
​
Priority QUEUE
[Link]
[Link]
[Link]
[Link]
ain9mt&
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
​
​
BIT Manipulations
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
​
​
​
​
Miscellaneous
[Link]
[Link]
[Link]
d=2024-06-24
[Link]
[Link] try in o(n) using prefix and
suffix method and kadane
[Link]
[Link]
[Link]
[Link]
[Link]
urce=geeksforgeeks&itm_medium=article&itm_campaign=bottom_sticky_on_article
[Link]
[Link]
[Link]
[Link]
-v2&envId=mgain9mt
[Link]
[Link] do this again
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
919/
[Link]
[Link]
[Link]
[Link]
​
​
​
​
​
Graphs
[Link]
[Link]
[Link]
eue-dp-dijkstra/
[Link]
[Link]
ch-c/
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
?envType=daily-question&envId=2024-06-30
[Link]
[Link]
estion&envId=2024-07-28
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
2&envId=shortest-path
[Link]
2792/
[Link]
[Link]
[Link]
[Link] solve using bfs
[Link]
[Link]
​
​
Arrays
[Link]
[Link]
d=2024-06-24
[Link]
[Link]
medium=collab_striver_ytdescription&utm_campaign=find-missing-and-repeating
[Link]
[Link]
[Link]
[Link] o(n)
[Link]
[Link]
stion&envId=2024-08-02
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
​
​
Binary search
[Link]
[Link]
mgain9mt&
[Link]
[Link]
[Link]
[Link]
[Link]
​
​
​
Strings
[Link] O(n) solve
[Link]
[Link]
[Link]
[Link]

Trees
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
2792/
[Link]
​
​
STACKS
[Link]
[Link]
[Link]
[Link]
[Link]
​
​
​
​
​
​
​
​
​
​
​
​
​
​
segment trees template
BUILD,QUERY
#include <bits/stdc++.h>
using namespace std;
void build(vector<int> &a,vector<int> &seg,int node,int start,int end){
if (start==end) seg[node]=a[start];
else {
int mid=(start+end)>>1;
build(a,seg,2*node,start,mid);
build(a,seg,2*node+1,mid+1,end);
seg[node]=min(seg[2*node],seg[2*node+1]);
}
}
int query(vector<int> &seg,int node,int start,int end,int left,int right){
if (left>end || right<start) return INT_MAX;
else if (start>=left && right>=end) return seg[node];
else {
int mid=(start+end)>>1;
int l=query(seg,2*node,start,mid,left,right);
int r=query(seg,2*node+1,mid+1,end,left,right);
return min(l,r);
}
}
int main(){
int n,q;cin>>n>>q;
vector<int> a(n);
for (int i=0;i<n;i++) cin>>a[i];
vector<int> seg(4*n);
build(a,seg,1,0,n-1);
for (int i=0;i<q;i++){
int a,b;cin>>a>>b;
a--;b--;
cout<<query(seg,1,0,n-1,a,b)<<endl;
}
BUILD, UPDATE,QUERY
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void build(vector<ll> &a,vector<ll> &seg,ll node,ll start,ll end){
if (start==end) seg[node]=a[start];
else {
ll mid=(start+end)>>1;
build(a,seg,2*node,start,mid);
build(a,seg,2*node+1,mid+1,end);
seg[node]=min(seg[2*node],seg[2*node+1]);
}
}
void update(vector<ll> &seg,ll node,ll start,ll end,ll ind,ll val){
if (ind>end || ind<start) return;
if (start==ind && end==ind) seg[node]=val;
else {
ll mid=(start+end)>>1;
update(seg,2*node,start,mid,ind,val);
update(seg,2*node+1,mid+1,end,ind,val);
seg[node]=min(seg[2*node],seg[2*node+1]);
}
}
ll query(vector<ll> &seg,ll node,ll start,ll end,ll left,ll right){
if (left>end || right<start) return INT_MAX;
else if (start>=left && right>=end) return seg[node];
else {
ll mid=(start+end)>>1;
ll l=query(seg,2*node,start,mid,left,right);
ll r=query(seg,2*node+1,mid+1,end,left,right);
return min(l,r);
}
}
int main(){
ll n,q;cin>>n>>q;
vector<ll> a(n);
for (ll i=0;i<n;i++) cin>>a[i];
ll treesize=4*n;
vector<ll> seg(4*n);
build(a,seg,1,0,n-1);
for (ll i=0;i<q;i++){
ll c,a,b;cin>>c>>a>>b;
if (c==1){
a--;
update(seg,1,0,n-1,a,b);
}
else {
a--;b--;
cout<<query(seg,1,0,n-1,a,b)<<endl;
}
}
}

You might also like