# Travelyoka

Can anyone share “traveloka” hackereaeth hiring challenge “Top speed” and “divide array” solution.

Need help with code because I was getting TLe

1 Like

Devide Array Solution :

Top Speed Solution :

Edit : In top speed problem use binary search to avoid tle

1 Like

@aman0077
Example : 5 4 3 2 1
right most vehicle always runs at her maximum speed in this case vehicle 1 runs at max
after vehicle 1 any vehicle have lesser speed than vehicle 1 runs at max speed if not than run at max speed of previous vehicle than array looks like this 1 1 1 1 1 then just apply binary search for each i th vehicle any previous vehicle runs at her max speed and has greater than or equals speed to i th vehicle than just stop and you got index of that prev vehicle than calculate ans using index.

2 Likes

Understood! Thanks for the explanation.

1 Like

Bro please explain Approach the logic for Divide Array

@rishabhjha708
Example :
I - 0 0 0 3 3 3
O - 0 1 3 0 0 3
bro just use simple mapping & code according to above example.

TOP SPEED

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli arr[200009];
lli tree[200009];
lli brr[200009];
lli crr[200009];
unordered_map<lli,lli>mp;
lli maxi=INT_MIN;

void update(lli index,lli val,lli n)
{
while(index<=n)
{
tree[index]=max(tree[index],val);
index+=index&(-index);
}
}

lli query(lli index)
{
maxi=INT_MIN;

``````while(index>0)
{
maxi=max(maxi,tree[index]);
index-=index&(-index);
}

return maxi;
``````

}

int main()
{
lli i,j,k,n,m,t,ans;

``````cin>>t;

while(t--)
{
cin>>n;

mp.clear();

for(i=1;i<=n;i++)
{
cin>>arr[i];
crr[i]=arr[i];
}

sort(crr+1,crr+n+1);

for(i=1;i<=n;i++)
{
if(mp[crr[i]]==0)
{
mp[crr[i]]=i;
}
}

for(i=1;i<=n;i++)
tree[i]=INT_MIN;

for(i=n;i>=1;i--)
{
ans=query(mp[arr[i]]-1);

if(ans==INT_MIN)
brr[i]=0;
else
brr[i]=ans-i;

update(mp[arr[i]],i,n);
}

for(i=1;i<=n;i++)
{
cout<<brr[i]<<" ";
}

cout<<"\n";
}
``````

}