Arrays Flashcards
Rotation of array O(n) time, O(1) space
define ll long long
#include using namespace std;
ll gcd(ll a,ll b)
{
if(b==0)
return a;
return gcd(b,a%b);
}
int main() {
ll t;
cin>>t;
while(t--)
{
ll n,d,i,j;
cin>>n>>d;
ll a[n];
for(i=0;i>a[i];
}
ll g = gcd(d,n);
for(i=0;i=n)
k=k-n;
if(k==i)
break;
a[j]=a[k]; j=k; } a[j]=temp; } for(i=0;i
Rotation of array O(n) time, O(d) space
define ll long long
#include using namespace std;
int main() {
ll t;
cin>>t;
while(t--)
{
ll n,d,i,j;
cin>>n>>d;
vector a;
for(i=0;i>x;
a.push_back(x);
}
d = d%n;
vector save;
for(i=0;i
Find Transition point in array containing 0 and 1, O(logn)
int transitionPoint(int arr[], int n) {
int l=0,r=n-1;
while(l<=r)
{
int mid = (l+r)/2;
if(arr[mid]<1)
{
l=mid+1;
}
else
{
if(arr[mid-1]==1)
{
r=mid-1;
}
else
{
return mid;
}
}
}
return -1;
}Submatrix sum queries (given 2-d array, find sum from (x1,y1) to (x2,y2) ) O(1) time for each query.
define ll long long
#include using namespace std;
int main() {
ll t;
cin>>t;
while(t--)
{
ll n,m,i,j,x1,y1,x2,y2,sum=0;
cin>>n>>m;
ll a[n+1][m+1];
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
cin>>x1>>y1>>x2>>y2;
for(i=1;i<=n;i++)
{
for(j=2;j<=m;j++)
{
a[i][j]+=a[i][j-1];
}
}
for(i=2;i<=n;i++)
{
for(j=1;j<=m;j++)
{
a[i][j]+=a[i-1][j];
}
}
if(x2>=1 && y2>=1)
sum+=a[x2][y2];
if(x1-1>=1 && y2>=1)
sum-=a[x1-1][y2];
if(x2>=0 && y1-1>=1)
sum-=a[x2][y1-1];
if(x1-1>=1 && y1-1>=1)
sum+=a[x1-1][y1-1];
cout
Count number of 0’s in sorted array of 0 and 1 O(logn)
define ll long long
#include using namespace std;
int main() {
ll t;
cin>>t;
while(t--)
{
ll n,i;
cin>>n;
ll a[n];
for(i=0;i>a[i];
}
ll l=0,r=n-1,ans=-1;
while(l<=r)
{
ll mid = (l+r)/2;
if(a[mid]>0)
{
l=mid+1;
}
if(a[mid]==0)
{
if(a[mid-1]>0)
{
ans = mid;
break;
}
else
{
r=mid-1;
}
}
}
if(ans==-1)
ans=n;
cout<
Rotate a 2-D (N X N) array 90 degree clockwise without using extra space O(N^2)
define ll long long
#include using namespace std;
int main() {
ll t;
cin>>t;
while(t--)
{
ll n,i,j;
cin>>n;
ll a[n][n];
for(i=0;i>a[i][j];
}
}
//find A transpose
for(i=0;i
Magic Array (i
#include using namespace std;
#define ll long long #define N 1000000
int main() {
ll t;
cin>>t;
while(t--)
{
ll n,i,j;
cin>>n;
ll count[N],ans=0;
vector a;
ll st[n];
memset(count,0,sizeof(count));
for(i=0;i>x;
a.push_back(x);
}
for(i=0;i
Product array puzzle (product of all array values except the value of index itself) Space : O(n) Time: O(n)
vector productExceptSelf(vector& nums) {
int n=nums.size(),i;
vector p(n);
int temp=1;
if(n==1)
{
p.push_back(0);
return p;
}
for(i=0;i=0;i--)
{
p[i] = p[i]*temp;
temp*=nums[i];
}
return p;
}Kadanes’s algorithm (Maximum sum contiguous subarray) O(n)
define ll long long
#include using namespace std;
int main() {
ll t;
cin>>t;
while(t--)
{
ll n,i;
cin>>n;
ll a[n];
for(i=0;i>a[i];
}
ll maxm = INT_MIN ,sum = 0;
for(i=0;isum)
{
sum=a[i];
}
else
{
sum+=a[i];
}
if(sum>maxm)
{
maxm = sum;
}
}
cout<
Maximum product subarray O(n)
define ll long long
#include using namespace std;
int main() {
ll t;
cin>>t;
while(t--)
{
ll n,i;
cin>>n;
ll a[n];
for(i=0;i>a[i];
}
ll maxm = a[0], minm = a[0] , ans = a[0] , flag=0;
for(i=1;i
Convert all 0’s to 5 in a number ‘n’ O(k) where k is number of digits in n. (other method - recursion)
int convertFive(int n) {
int d = 1,num = n,f = 0;
if(n==0)
return 5;
while(num>0)
{
if(num%10==0)
{
f = 5*d + f;
}
d*=10;
num/=10;
}
return (n + f);
}
Maximum sum of lengths of non-overlapping subarrays with k as the max element O(n)
define ll long long
#include using namespace std;
int main() {
ll t;
cin>>t;
while(t--)
{
ll n,k,i,l=0,count=0,maxm=INT_MIN;
cin>>n;
ll a[n];
for(i=0;i>a[i];
}
cin>>k;
for(i=0;i
Find next greater number with same set of digits O(n) - spoj
#include using namespace std;
#define ll long long #define N 1000000
int main() {
ll t;
cin>>t;
while(t--)
{
ll n,i,save=-1,next,small=-1;
cin>>n;
ll a[n];
for(i=0;i>a[i];
}
for(i=n-1;i>=1;i--)
{
if(a[i]>a[i-1])
{
save=i-1;
next = i;
break;
}
}
if(save==-1)
{
cout<
Count pairs with given sum, time : O(n), space: O(n) using map method
define ll long long
using namespace std;
int main() {
ll t;
cin>>t;
while(t--)
{
ll n,k,i,count=0;
cin>>n>>k;
ll a[n];
map mp;
for(i=0;i>a[i];
mp[a[i]]++;
}
for(i=0;i
First negative integer in every window of size k O(n) - Another approach in queue flashcard using deque.
define ll long long
#include using namespace std;
int main() {
ll t;
cin>>t;
while(t--)
{
ll n,k,i,j;
cin>>n;
ll a[n];
deque d;
for(i=0;i>a[i];
}
cin>>k;
for(i=0;i
