Intern

C++ Solution: 

vector maxSlidingWindow(vector& nums, int k) {
vectorans;
int n = nums.size();
if(nq;
int i=0,j=0;
while(j {
while(q.size() && q.back() {
q.pop_back();
}
q.push_back(nums[j]);
if(j-i+1==k)
{
ans.push_back(q.front());
if(nums[i]==q.front())
{
q.pop_front();
}
i++;
}
j++;
}
return ans;
}

Solution in Java

class Solution {
public int maxProfit(int k, int[] prices) {
if(prices.length==0 || k==0) return 0;
int dp[][]=new int[k+1][prices.length];
for(int i=1;i<=k;i++){
int max=Integer.MIN_VALUE;
for(int j=1;j max=Math.max(max,dp[i-1][j-1]-prices[j-1]);
dp[i][j]=Math.max(max+prices[j],dp[i][j-1]);
}
}
return dp[k][prices.length-1];
}
}

Time complexity
The time complexity of the above algorithm is O(n)
Space complexity
The algorithm runs in constant space O(1)

function findDuplicate(nums: number[]): number {

let orderedIndex=0;

while(orderedIndex 
if(nums[orderedIndex]!==orderedIndex+1){// because our range from 1 to n
let unorderedIndex=nums[orderedIndex]-1;

if(nums[orderedIndex]!==nums[unorderedIndex]){
[nums[orderedIndex],nums[unorderedIndex]]=[nums[unorderedIndex],nums[orderedIndex]]
}else{
return nums[orderedIndex]
}

}else{
orderedIndex++;
}
}
return -1
};

class Solution {
private:
int fn(int i,int tar,vector&nums,vector>&dp){
if(i==0){
if(tar%nums[i]==0){
return tar/nums[i];
}
else{
return 1e9;
}
}
if(dp[i][tar]!=-1){
return dp[i][tar];
}
int np=fn(i-1,tar,nums,dp);
int p= 1e9;
if(tar>=nums[i]){
p=1+fn(i,tar-nums[i],nums,dp);
}
return dp[i][tar]=min(p,np);
}
public:
int coinChange(vector& nums, int tar) {
int n=nums.size();
vector>dp(n,vector(tar+1,-1));
long ans=fn(n-1,tar,nums,dp);
if(ans== 1e9){
return -1;
}
return ans;
}
};