Count Number of Teams | Simple thought process | Intuition | Leetcode 1395

[@puneetkumar5703]

Sense of relief I get when I see you have uploaded solution of the question I am searching for is insane.

[@Elliethe_bunny]

HOMEWORK ANSWER :- (Recursion+Memoization) class Solution { public: int n; int t1[100001][3]; int t2[100001][3]; int solve_inc(vector&rating,int i,int count){ if(count==2) return 1; if(i>=n) return 0; if(t1[i][count]!=-1) return t1[i][count]; int ans=0; for(int j=i+1;jrating[i]){ ans+=solve_inc(rating,j,count+1); } } return t1[i][count]=ans; } int solve_dec(vector&rating,int i,int count){ if(count==2) return 1; if(i>=n) return 0; if(t2[i][count]!=-1) return t2[i][count]; int ans=0; for(int j=i+1;j

[@kunalsharma-zc2ho]

In Java :- private int n; private int[][] t1; private int[][] t2; // Recursive function to count increasing sequences private int solveInc(int[] rating, int i, int count) { if (count == 2) return 1; if (i >= n) return 0; if (t1[i][count] != -1) return t1[i][count]; int ans = 0; for (int j = i + 1; j < n; j++) { if (rating[j] > rating[i]) { ans += solveInc(rating, j, count + 1); } } return t1[i][count] = ans; } // Recursive function to count decreasing sequences private int solveDec(int[] rating, int i, int count) { if (count == 2) return 1; if (i >= n) return 0; if (t2[i][count] != -1) return t2[i][count]; int ans = 0; for (int j = i + 1; j < n; j++) { if (rating[j] < rating[i]) { ans += solveDec(rating, j, count + 1); } } return t2[i][count] = ans; } public int numTeams(int[] rating) { n = rating.length; t1 = new int[n][3]; t2 = new int[n][3]; // Initialize memoization tables with -1 for (int i = 0; i < n; i++) { Arrays.fill(t1[i], -1); Arrays.fill(t2[i], -1); } int ans = 0; for (int i = 0; i < n; i++) { ans += solveInc(rating, i, 0) + solveDec(rating, i, 0); } return ans; }

[@Cgarg2306]

class Solution { public: int count=0; void solve(vector& rating, vector& use, int index, int prev) { if (use.size() == 3) { count++; return; } for (int i = index; i < rating.size(); i++) { if (prev == -1 || rating[i] > rating[prev]) { use.push_back(rating[i]); solve(rating, use, i + 1, i); use.pop_back(); } } } void solve2(vector& rating, vector& use2, int index, int prev) { if (use2.size() == 3) { count++; return; } for (int i = index; i < rating.size(); i++) { if (prev == -1 || rating[i] < rating[prev]) { use2.push_back(rating[i]); solve2(rating, use2, i + 1, i); use2.pop_back(); } } } int numTeams(vector& rating) { int n = rating.size(); vectoruse; vectoruse2; solve(rating,use,0,-1); solve2(rating,use2,0,-1); return count; } };

[@krishgupta7690]

memoize it

[@GauravDuseja-t6q]

@@krishgupta7690 Ha bhai

[@bibekanandanayak8839]

tle de raha he bhai

[@ThakurIsGeek]

you are great guy , keep going never stop teaching you are helping many guys for building intuition . Have a great journey and happy life.

[@DevOpskagyaan]

You make every problem look easy 🥺 thanks

[@anshul3112_]

Bhaiya please kal ke leetcode contest ka 3rd question please

[@prajwalshaw9217]

Ha bhaiya. Plz

[@gui-codes]

yes please

[@sahilsukhdeve4695]

also 2nd question

[@zebra-er6xc]

@@sahilsukhdeve4695 iske lie sieve of erastothenes dekho aur jo bhi special numbers honge woh prime numbers ke square hi honge, give it a try

[@teamdeadshotyt840]

excellent approach

[@hackerab7923]

class Solution { public: int f(vector& rating,int idx,vector v,vector &dp){ if(v.size()==3) return 1; if(idx

[@hackerab7923]

please explain where i did error and why

[@edutrackers2457]

Bhai mila kya sol

[@KishanSingh-vc3re]

also we can caculate the less and more around an index using an array which would further cut down the complexity to 1

[@worldofgaming748]

Wow we really need guys Like You!

[@Robinkumar-ew9ky]

Nice explanation. But inner two loops have not time complexity O(2n), they have complete time complexity O(n). Because one loop is running from 0 to i - 1 and second is running from i + 1 to n , combination of both loop is running from 0 to n.

[@devanshsinghla4677]

class Solution { public: int inc(int i, int n, int lastIndex, vector& rating, int size, vector& dp) { if (size == 3) { return 1; } if (i >= n) { return 0; } if (dp[i][lastIndex + 1][size] != -1) { return dp[i][lastIndex + 1][size]; } int take = 0; if (lastIndex == -1 || rating[i] > rating[lastIndex]) { take = inc(i + 1, n, i, rating, size + 1, dp); } int notake = inc(i + 1, n, lastIndex, rating, size, dp); return dp[i][lastIndex + 1][size] = take + notake; } int dec(int i, int n, int lastIndex, vector& rating, int size, vector& dp) { if (size == 3) { return 1; } if (i >= n) { return 0; } if (dp[i][lastIndex + 1][size] != -1) { return dp[i][lastIndex + 1][size]; } int take = 0; if (lastIndex == -1 || rating[i] < rating[lastIndex]) { take = dec(i + 1, n, i, rating, size + 1, dp); } int notake = dec(i + 1, n, lastIndex, rating, size, dp); return dp[i][lastIndex + 1][size] = take + notake; } int numTeams(vector& rating) { int n = rating.size(); vector dpInc(n + 1, vector(n + 1, vector(4, -1))); vector dpDec(n + 1, vector(n + 1, vector(4, -1))); int increasing = inc(0, n, -1, rating, 0, dpInc); int decreasing = dec(0, n, -1, rating, 0, dpDec); return increasing + decreasing; } }; I have memoized but I am getting TLE for this code

[@dhruavgarg668]

bro use 2 1d vector instead of 1 2d vector

[@devanshsinghla4677]

@@dhruavgarg668 thanks i will try this as well

[@anshdholakia714]

Simple approach hai yeh -> class Solution: def numTeams(self, rating: List[int]) -> int: inc=[0]*len(rating) dec=[0]*len(rating) res=0 for i in range(len(rating)-2, -1, -1): for j in range(i+1,len(rating)): if rating[j]>rating[i]: inc[i]+=1 res+=inc[j] for i in range(len(rating)-2, -1, -1): for j in range(i+1, len(rating)): if rating[j]

[@someshnayakrollno.-09sec-b27]

void recursion(int i,int count ,int& result,int n,vector& rating){//2,5,3,4,1 count++; if(count==3){ result++; return; } // i

[@sauravchandra10]

NLogN approach using the concept of 'smaller number after self' (Leetcode 315) in Python class Solution: def countSmaller(self, nums: List[int]) -> List[int]: res = [0] * (len(nums)) arr = [] for i in range(len(nums)): arr.append([nums[i], i]) def merge(start, mid, end): temp = [] i, j = start, mid+1 while i

[@nishantdehariya5769]

class Solution { public: vector dpInc; vector dpDec; int calculateInc(vector& rating, int idx,int count) { if (count == 2) { return 1; } if(idx>=rating.size()) return 0; if(dpInc[idx][count] != -1) { return dpInc[idx][count]; } int total = 0; for (int i = idx+1; i < rating.size(); i++) { if (rating[idx] < rating[i]) { total +=calculateInc(rating, i, count+1); } } return dpInc[idx][count]=total; } int calculateDec(vector& rating, int idx,int count) { if (count == 2) { return 1; } if(idx>=rating.size()) return 0; if(dpDec[idx][count] != -1) { return dpDec[idx][count]; } int total = 0; for (int i = idx+1; i < rating.size(); i++) { if (rating[idx] > rating[i]) { total +=calculateDec(rating, i, count+1); } } return dpDec[idx][count]=total; } int numTeams(vector& rating) { dpInc.resize(rating.size(),vector(4,-1)); dpDec.resize(rating.size(),vector(4,-1)); int ans = 0; for(int i=0;i

[@visheshtiwari8176]

Love your videos . Approach: Time complexity: O(n log n) Space complexity: O(n) High-level idea: To find the number of increasing subsequences of length 3, follow these steps: 1. For each element, find the number of greater elements on its right and the number of smaller elements on its left. 2. For each middle element, use the counts from step 1 to calculate the total number of subsequences of length 3 in linear time. 3. The challenging part is finding the next greater element on the right and the previous smaller element on the left for all elements in O(n log n) time. Finding next greater element on the right: 1. Traverse the array from right to left. 2. Use a sorted set and insert each element into it. 3. The position of insertion can be used to calculate the number of greater elements to the right. Finding previous smaller element on the left: 1. Repeat the same process as above, but traverse from left to right. Repeat for decreasing subsequences: Repeat all steps to find the number of decreasing subsequences of length 3. By using a sorted set, you can achieve O(n log n) time complexity for finding the next greater and previous smaller elements. This approach allows you to efficiently calculate the number of increasing and decreasing subsequences of length 3.

[@Jagrit-k4b]

class Solution { public: int n; int f1(vector& rating,int i,int prev,int sz,vector& dp){ if(sz==3) return 1; if(i>=n) return 0; if(dp[i][sz]!=-1) return dp[i][sz]; int ans=0; for(int j=i;jprev){ ans+=f1(rating,j+1,rating[j],sz+1,dp); } } return dp[i][sz]=ans; } int f2(vector& rating,int i,int prev,int sz,vector& dp){ if(sz==3) return 1; if(i>=n) return 0; if(dp[i][sz]!=-1) return dp[i][sz]; int ans=0; for(int j=i;j

[@SaifShaikh-ss3fq]

class Solution { public: int dp1[1001][4]; int dp2[1001][4]; int solvedec(vector& arr, int index, int cnt){ if(cnt == 3){ return 1; } if(dp1[index][cnt] != -1){ return dp1[index][cnt]; } int res = 0; for(int i = index + 1; i < arr.size(); i++){ if(arr[i] < arr[index]){ res += solvedec(arr, i, cnt + 1); } } return dp1[index][cnt] = res; } int solveinc(vector& arr, int index, int cnt){ if(cnt == 3){ return 1; } if(dp2[index][cnt] != -1){ return dp2[index][cnt]; } int res = 0; for(int i = index + 1; i < arr.size(); i++){ if(arr[i] > arr[index]){ res += solveinc(arr, i, cnt + 1); } } return dp2[index][cnt] = res; } int numTeams(vector& arr) { ios_base::sync_with_stdio(false); cin.tie(NULL); memset(dp1, -1, sizeof(dp1)); memset(dp2, -1, sizeof(dp2)); int n = arr.size(); //increasing int res1 = 0; int res2 = 0; for(int i = 0; i < n; i++){ res1 += solveinc(arr, i, 1); } //decreasing for(int i = 0; i < n; i++){ res1 += solvedec(arr, i, 1); } return res1 + res2; } };

[@GauravDuseja-t6q]

class Solution { public: int solve(int ind, vector& rating, int ans1, vector& dp) { if (dp[ind][ans1] != -1) return dp[ind][ans1]; if (ind == rating.size()) return 0; if (ans1 == 3) return 1; int fans = 0; for (int i = ind + 1; i < rating.size(); i++) { if (rating[i] > rating[ind]) { fans += solve(i, rating, ans1 + 1, dp); } } return dp[ind][ans1] = fans; } int solve2(int ind, vector& rating, int ans1, vector& dp2) { if (dp2[ind][ans1] != -1) return dp2[ind][ans1]; if (ind == rating.size()) return 0; if (ans1 == 3) return 1; int fans = 0; for (int i = ind + 1; i < rating.size(); i++) { if (rating[i] < rating[ind]) { fans += solve2(i, rating, ans1 + 1, dp2); } } return dp2[ind][ans1] = fans; } int numTeams(vector& rating) { int n = rating.size(); vector dp(n, vector(4, -1)); vector dp2(n, vector(4, -1)); int fans = 0, fans2 = 0; for (int i = 0; i < rating.size(); i++) { fans += solve(i, rating, 1, dp); fans2 += solve2(i, rating, 1, dp2); } return fans + fans2; } };memoization code

[@sauravchandra10]

Second approach code in Pyhon: class Solution: def numTeams(self, rating: List[int]) -> int: ans = 0 for mid in range(1, len(rating)-1): i, j = 0, mid+1 greaterLeft, smallerLeft, greaterRight, smallerRight = 0, 0, 0, 0 while i < mid: if rating[i] < rating[mid]: smallerLeft += 1 else: greaterLeft += 1 i += 1 while j < len(rating): if rating[mid] < rating[j]: greaterRight += 1 else: smallerRight += 1 j += 1 ans += greaterLeft*smallerRight + smallerLeft*greaterRight return ans

[@pardeepgill2586]

class Solution { public: int result = 0; unordered_map memoInc; unordered_map memoDec; int solveDec(int n, vector& rating, int i, int element) { if (element == 3) { return 1; } if (i >= n - 1) { return 0; } string key = to_string(i) + "-" + to_string(element); if (memoDec.find(key) != memoDec.end()) { return memoDec[key]; } int count = 0; for (int j = i + 1; j < n; ++j) { if (rating[j] < rating[i]) { count += solveDec(n, rating, j, element + 1); } } memoDec[key] = count; return count; } int solveInc(int n, vector& rating, int i, int element) { if (element == 3) { return 1; } if (i >= n - 1) { return 0; } string key = to_string(i) + "-" + to_string(element); if (memoInc.find(key) != memoInc.end()) { return memoInc[key]; } int count = 0; for (int j = i + 1; j < n; ++j) { if (rating[j] > rating[i]) { count += solveInc(n, rating, j, element + 1); } } memoInc[key] = count; return count; } int numTeams(vector& rating) { int n = rating.size(); for (int i = 0; i < n - 2; ++i) { result += solveInc(n, rating, i, 1); result += solveDec(n, rating, i, 1); } return result; } };

[@sauravchandra10]

Recursion + Memoization code in Python: class Solution: def numTeams(self, rating: List[int]) -> int: dp = {} def findLIS(pind, ind, size, asc): if ind == len(rating): return size == 3 if (pind, ind, size, asc) in dp: return dp[(pind, ind, size, asc)] ans = 0 if asc and ((pind == -1) or (rating[pind] < rating[ind] and size < 3)): ans += findLIS(ind, ind+1, size+1, asc) elif not asc and ((pind == -1) or (rating[pind] > rating[ind] and size < 3)): ans += findLIS(ind, ind+1, size+1, asc) ans += findLIS(pind, ind+1, size, asc) dp[(pind, ind, size, asc)] = ans return ans return findLIS(-1, 0, 0, True) + findLIS(-1, 0, 0, False)

[@HarmanSingh-nw6ix]

class Solution { public: int numTeams(vector& rating) { int count=0; int n = rating.size(); for(int i=0;i

[@rohitsonar8858]

I just count the lis from front and from reverse and then calculate using combination method lisC3 for both front and reverse order

[@vanshikakumari5744]

can you provide the code here?

[@keshavgarg381]

class Solution { public: vector memo; // Initialize the memoization table void initMemo(int n) { memo = vector(n, vector(n + 1, vector(4, -1))); } // Function to count increasing or decreasing sequences int countSequences(vector& rating, int curr, int prev, int count, bool increasing) { if (count == 3) { return 1; } if (curr == rating.size()) { return 0; } if (memo[curr][prev + 1][count] != -1) { return memo[curr][prev + 1][count]; } int ans = 0; if (prev == -1 || (increasing && rating[curr] > rating[prev]) || (!increasing && rating[curr] < rating[prev])) { ans += countSequences(rating, curr + 1, curr, count + 1, increasing); } ans += countSequences(rating, curr + 1, prev, count, increasing); memo[curr][prev + 1][count] = ans; return ans; } int numTeams(vector& rating) { int n = rating.size(); initMemo(n); // Count increasing sequences int ans1 = countSequences(rating, 0, -1, 0, true); // Re-initialize memoization table for decreasing sequences initMemo(n); // Count decreasing sequences int ans2 = countSequences(rating, 0, -1, 0, false); return ans1 + ans2; } }; 3 Test Cases showing tle

[@thefinalfit]

Paused in the middle and coded. Seems easy now

[@mohdaqibkhan2135]

class Solution { public: int solve(int i,int n,int prv,vector& rating, int cnt,bool increasing) { if(i==n ) return 0; if(cnt==3) return 1; int notpick=solve(i+1,n,prv,rating,cnt,increasing); int pick=0; if (prv == -1 || (increasing && rating[i] > rating[prv]) || (!increasing && rating[i] < rating[prv])) pick = solve(i + 1, n, i, rating, cnt + 1, increasing); return pick + notpick; } int numTeams(vector& rating) { int n=rating.size(); return solve(0,n,-1,rating,0,true) + solve(0,n,-1,rating,0,false); } } The code is giving wrong answer. Can anyone tell what am i doing wrong .

[@manishjoshi9737]

class Solution { public: int n; int t[1001][1001][4]; int solveIncr(int i, int prev, int cnt, vector&arr) { if(i >= n) { return (cnt == 3)?1:0; } if(cnt == 3) { return 1; } if(prev != -1 && t[i][prev][cnt] != -1) return t[i][prev][cnt]; int res = 0; if(cnt == 0 || arr[i] > arr[prev]) { res += solveIncr(i+1, i, cnt+1, arr); } res += solveIncr(i+1, prev, cnt, arr); if(prev != -1) { return t[i][prev][cnt] = res; } return res; } int solveDcr(int i, int prev, int cnt, vector&arr) { if(i >= n) { return (cnt == 3)?1:0; } if(cnt == 3) { return 1; } if(prev != -1 && t[i][prev][cnt] != -1) return t[i][prev][cnt]; int res = 0; if(cnt == 0 || arr[i] < arr[prev]) { res += solveDcr(i+1, i, cnt+1, arr); } res += solveDcr(i+1, prev, cnt, arr); if(prev != -1) { return t[i][prev][cnt] = res; } return res; } int numTeams(vector& arr) { n=arr.size(); memset(t, -1, sizeof(t)); int a = solveIncr(0, -1, 0, arr); cout

[@shubhamjaiswal7645]

class Solution { public: int dp[1000][1000][4][3]; int solve(vector&v, int i, int prev, int cnt, int c){ if(!cnt) return 1; if(i == v.size()) return 0; if(dp[i][prev + 1][cnt][c + 1] != -1) return dp[i][prev + 1][cnt][c + 1]; int c1 = 0, c2 = 0, c3 = 0; if(c == -1){ c1 = solve(v, i + 1, i, cnt - 1, 0); c2 = solve(v, i + 1, i, cnt - 1, 1); } else if(c == 0 && v[prev] < v[i]){ c1 = solve(v, i + 1, i, cnt - 1, 0); } else if(c == 1 && v[prev] > v[i]){ c2 = solve(v, i + 1, i, cnt - 1, 1); } c3 = solve(v, i + 1, prev, cnt, c); return dp[i][prev + 1][cnt][c + 1] = c1 + c2 + c3; } int numTeams(vector&r){ memset(dp, -1, sizeof(dp)); return solve(r, 0, -1, 3, -1); } };

[@GK-ww3ym]

int numTeams(vector& rating) { int n = rating.size(); if (n < 3) return 0; // Not enough soldiers for a team int count = 0; // dp[i][j] will be the number of subsequences of length j ending at index i vector dp_inc(n, vector(3, 0)); // Increasing subsequences vector dp_dec(n, vector(3, 0)); // Decreasing subsequences // Initialize subsequences of length 1 for (int i = 0; i < n; ++i) { dp_inc[i][0] = 1; dp_dec[i][0] = 1; } // Build up the dp tables for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { if (rating[i] > rating[j]) { dp_inc[i][1] += dp_inc[j][0]; // Number of subsequences of length 2 ending at i dp_inc[i][2] += dp_inc[j][1]; // Number of subsequences of length 3 ending at i } if (rating[i] < rating[j]) { dp_dec[i][1] += dp_dec[j][0]; // Number of subsequences of length 2 ending at i dp_dec[i][2] += dp_dec[j][1]; // Number of subsequences of length 3 ending at i } } } // Count all valid subsequences of length 3 for (int i = 0; i < n; ++i) { count += dp_inc[i][2]; count += dp_dec[i][2]; } return count; }

[@kamranwarsi12b22]

bhai plz make a video for clearing oa's , much needed plzz....

[@Nofaltuguy1]

fr

[@vivekkaradbhajne1425]

what is oa's ?

[@kamranwarsi12b22]

@@vivekkaradbhajne1425 online assessment

[@Nofaltuguy1]

@@vivekkaradbhajne1425 online assessments which is a coding test for on campus placement

[@ZilaGhaziabad99]

please make video on "214. Shortest Palindrome" Leetcode | Hard

[@reppee4392]

if anyone is wondering for full space optimized DP approach int numTeams(vector& rating) { int n = rating.size(); vectorincCurr(n+1,vector(4,0)); vectorincAhead(n+1,vector(4,0)); vectordecCurr(n+1,vector(4,0)); vectordecAhead(n+1,vector(4,0)); for(int j=0;j=0;i--){ for(int prev=i;prev>=0;prev--){ for(int size=1;size rating[prev-1]){ takeI = incAhead[i+1][size-1]; } ntakeI = incAhead[prev][size]; incCurr[prev][size] = takeI+ntakeI; int takeD=0,ntakeD=0; if(prev==0 || rating[i] < rating[prev-1]){ takeD = decAhead[i+1][size-1]; } ntakeD = decAhead[prev][size]; decCurr[prev][size] = takeD+ntakeD; } } incAhead = incCurr; decAhead = decCurr; } return incCurr[0][3] + decCurr[0][3]; }

[@SumitRawat-du2mt]

Python Solution class Solution: def numTeams(self, rating: List[int]) -> int: def count(l,h,n): c=[0,0] for i in range(l,h+1): if rating[i]

[@nikhilkumarpradhan4276]

class Solution { public: int helper2(vector& nums, int lst, int ind, int s, vector& dp2) { if (s == 3) { return 1; } if (ind == nums.size()) { return 0; } if (dp2[lst + 1][ind][s] != -1) { return dp2[lst + 1][ind][s]; } int take = 0; if (lst == -1 || nums[lst] > nums[ind]) { take += helper2(nums, ind, ind + 1, s + 1, dp2); } take += helper2(nums, lst, ind + 1, s, dp2); return dp2[lst + 1][ind][s] = take; } int helper1(vector& nums, int lst, int ind, int s, vector& dp1) { if (s == 3) { return 1; } if (ind == nums.size()) { return 0; } if (dp1[lst + 1][ind][s] != -1) { return dp1[lst + 1][ind][s]; } int take = 0; if (lst == -1 || nums[lst] < nums[ind]) { take += helper1(nums, ind, ind + 1, s + 1, dp1); } take += helper1(nums, lst, ind + 1, s, dp1); return dp1[lst + 1][ind][s] = take; } int numTeams(vector& rating) { int n = rating.size(); vector dp1(n + 1, vector(n, vector(4, -1))); vector dp2(n + 1, vector(n, vector(4, -1))); return helper1(rating, -1, 0, 0, dp1) + helper2(rating, -1, 0, 0, dp2); } };

[@SHIVAMOJHA21]

RECURSION + MEMO [TLE] class Solution: def numTeams(self, rating: List[int]) -> int: length = len(rating) greater = self.solve(0 , length , rating , 1 , 0 , None , {}) smaller = self.solve(0 , length , rating , 0 , 0 , None , {}) return greater+smaller def solve(self , idx , length , rating , take_higher , count , prev , memo): if (idx , count , prev) in memo: return memo[(idx , count , prev)] if count == 3: return 1 if idx >= length: return count == 3 take = 0 skip = 0 if prev == None: take = self.solve(idx+1 , length , rating , take_higher , count+1 , rating[idx] , memo) elif take_higher and rating[idx] > prev: take = self.solve(idx+1 , length , rating , take_higher , count+1 , rating[idx] , memo) elif not(take_higher) and rating[idx] < prev: take = self.solve(idx+1 , length , rating , take_higher , count+1 , rating[idx] , memo) skip = self.solve(idx+1 , length , rating , take_higher , count , prev , memo) memo[(idx , count , prev)] = take+skip return memo[(idx , count , prev)]

[@RishabhChatterjee-fg2gz]

Bhaiya iska o(n) solution bhi ho sakta hai kya? If yes then please upload that solution also

[@AS-gf3ci]

Top-Down DP : class Solution { int increasing(vector &rating, int idx, int prev, int taken, vector &dp) { int n = rating.size(); if(taken == 3) return 1; if(idx >= n) return 0; if(dp[idx][prev + 1][taken] != -1) return dp[idx][prev + 1][taken]; //Include int include = 0; if((prev == -1) || (rating[idx] > rating[prev])) include += increasing(rating, (idx + 1), idx, (taken + 1), dp); int exclude = increasing(rating, (idx + 1), prev, taken, dp); return (dp[idx][prev + 1][taken] = include + exclude); } int decreasing(vector &rating, int idx, int prev, int taken, vector &dp) { int n = rating.size(); if(taken == 3) return 1; if(idx >= n) return 0; if(dp[idx][prev + 1][taken] != -1) return dp[idx][prev + 1][taken]; //Include int include = 0; if((prev == -1) || (rating[idx] < rating[prev])) include += decreasing(rating, (idx + 1), idx, (taken + 1), dp); int exclude = decreasing(rating, (idx + 1), prev, taken, dp); return (dp[idx][prev + 1][taken] = include + exclude); } public: int numTeams(vector& rating) { int n = rating.size(); vector dp1(n+1, vector(n+1, vector(4, -1))); vector dp2(n+1, vector(n+1, vector(4, -1))); int incr = increasing(rating, 0, -1, 0, dp1); int decr = decreasing(rating, 0, -1, 0, dp2); return (incr + decr); } }; But this code passes only 70/72 testcases & gives TLE for last 2 testcases.

[@keshavgarg381]

same my code works for 69 tc

[@RishabhDhiman-zf5wd]

class Solution { public int numTeams(int[] rating) { int ans = 0; int n = rating.length; for(int i=0;i

[@MrDoggo-nd1jv]

class Solution { public int solve1(int[] r,int cur,int last,int val,int[][][] dp){ if(val == 3) return 1; if(cur == r.length) return 0; if(dp[cur][last+1][val] != -1) return dp[cur][last+1][val]; int ans = 0; for(int i=cur;i

[@Arjun-Kumar-Pandey]

115. Distinct Subsequences (LEETCODE QUESTION) How Memorizing this code? class Solution { public int numDistinct(String s, String t) { int n=s.length(); StringBuilder str=new StringBuilder(); return solver(0,str,s,t); } int solver(int i,StringBuilder str,String s,String t){ if(i==s.length()){ return str.toString().equals(t) ? 1 : 0; } int take=0; if(str.length()

[@SHIVAMOJHA21]

can't we use , something like LIS

[@jewelchakraborty9717]

Yes, check my comment. We have to slightly modift LIS.

[@kartikforwork]

rescursive dp+memo=tle class Solution { public: int numTeams(vector& rating) { int n = rating.size(); vector memo(n, vector(n, vector(4, vector(2, -1)))); return countTeams(rating, 0, -1, 0, true, memo) + countTeams(rating, 0, -1, 0, false, memo); } private: int countTeams(vector& rating, int i, int prev, int count, bool isIncreasing, vector& memo) { if (count == 3) { return 1; } if (i == rating.size()) { return 0; } if (prev != -1 && memo[i][prev][count][isIncreasing] != -1) { return memo[i][prev][count][isIncreasing]; } int take = 0; if (prev == -1 || (isIncreasing && rating[prev] < rating[i]) || (!isIncreasing && rating[prev] > rating[i])) { take = countTeams(rating, i + 1, i, count + 1, isIncreasing, memo); } int notTake = countTeams(rating, i + 1, prev, count, isIncreasing, memo); if (prev != -1) { memo[i][prev][count][isIncreasing] = take + notTake; } return take + notTake; } };

[@siddharthmahato8356]

I was also trying a similar approach, got TLE on 69th test case. Were you able to resolve the issue?

[@examcracker2458]

can you please solve it in O(nlogn)

[@hemant_kumar_071]

DP - Memoization class Solution { public: int dp1[1001][1001][4]; int dp2[1001][1001][4]; // Increasing Sequence int solve(int prev,int curr,vector& rating,int cnt){ if(cnt == 3) return 1; if(curr >= rating.size()) return 0; if(prev != -1 && dp1[prev][curr][cnt] != -1) return dp1[prev][curr][cnt]; int take = 0; if(prev == -1 || rating[prev] < rating[curr]){ take = solve(curr,curr+1,rating,cnt+1); } int skip = solve(prev,curr+1,rating,cnt); if(prev == -1) return take + skip; return dp1[prev][curr][cnt] = take + skip; } // Decreasing Sequence int solve2(int prev,int curr,vector& rating,int cnt){ if(cnt == 3) return 1; if(curr >= rating.size()) return 0; if(prev != -1 && dp2[prev][curr][cnt] != -1) return dp2[prev][curr][cnt]; int take = 0; if(prev == -1 || rating[prev] > rating[curr]){ take = solve2(curr,curr+1,rating,cnt+1); } int skip = solve2(prev,curr+1,rating,cnt); if(prev == -1) return take + skip; return dp2[prev][curr][cnt] = take + skip; } int numTeams(vector& rating) { memset(dp1, -1, sizeof(dp1)); memset(dp2, -1, sizeof(dp2)); int inc_Seq = solve(-1,0,rating,0); int dec_Seq= solve2(-1,0,rating,0); return inc_Seq + dec_Seq; } };

[@upcoming_Engineer_]

Leetcode Contest Solution please...

[@Abhisheksingh-ve9yg]

RECURSION + MEMOIZATION SIMPLE SA TAKE-SKIP WITH THE CONDITION class Solution { public: int n; int dp[1001][1001][4]; int solve(vector& rating, int i, int pre, int count) { if (count == 3) { return 1; } if (i >= n) { return 0; } if (dp[i][pre + 1][count] != -1) { return dp[i][pre + 1][count]; } int take = 0; if (pre == -1 || rating[pre] < rating[i]) { take = solve(rating, i + 1, i, count + 1); } int skip = solve(rating, i + 1, pre, count); return dp[i][pre + 1][count] = take + skip; } int solve2(vector& rating, int i, int pre, int count) { if (count == 3) { return 1; } if (i >= n) { return 0; } if (dp[i][pre + 1][count] != -1) { return dp[i][pre + 1][count]; } int take = 0; if (pre == -1 || rating[pre] > rating[i]) { take = solve2(rating, i + 1, i, count + 1); } int skip = solve2(rating, i + 1, pre, count); return dp[i][pre + 1][count] = take + skip; } int numTeams(vector& rating) { n = rating.size(); memset(dp, -1, sizeof(dp)); int chota = solve(rating, 0, -1, 0); memset(dp, -1, sizeof(dp)); int bada = solve2(rating, 0, -1, 0); return chota + bada; } };

[@rahulsah5206]

Recursion Code + Memoization TLE at 70/72 class Solution { public: int memo[1000][1000][3]; int increasingSeqof3(int pi,int ci,int cnt,vector &nums){ if(cnt==3) return 1; int n=nums.size(); if(ci==n) return 0; if(memo[pi+1][ci][cnt]!=-1) return memo[pi+1][ci][cnt]; int res=0; if(pi==-1 || nums[pi]nums[ci]) res+=decreasingSeqof3(ci,ci+1,cnt+1,nums); res+=decreasingSeqof3(pi,ci+1,cnt,nums); return res; } int numTeams(vector& rating) { int incCnt,decCnt; memset(memo,-1,sizeof(memo)); incCnt=increasingSeqof3(-1,0,0,rating); memset(memo,-1,sizeof(memo)); decCnt=decreasingSeqof3(-1,0,0,rating); return incCnt+decCnt; } };

[@naikajsevak6090]

bhaiya fenwick tree series please

[@KishanSingh-vc3re]

class Solution { public: int n; int solve1(vector& rating, int i, vector& temp) { if (temp.size() == 3) return 1; if (i >= n) return 0; int pick = 0; if (temp.empty() || rating[i] > temp.back()) { temp.push_back(rating[i]); pick = solve1(rating, i + 1, temp); temp.pop_back(); } int notPick = solve1(rating, i + 1, temp); return pick + notPick; } int solve2(vector& rating, int i, vector& temp) { if (temp.size() == 3) return 1; if (i >= n) return 0; int pick = 0; if (temp.empty() || rating[i] < temp.back()) { temp.push_back(rating[i]); pick = solve2(rating, i + 1, temp); temp.pop_back(); } int notPick = solve2(rating, i + 1, temp); return pick + notPick; } int numTeams(vector& rating) { n = rating.size(); vector temp1; vector temp2; int ans = solve1(rating, 0, temp1) + solve2(rating, 0, temp2); return ans; } };

[@tusharnanda3885]

2 Approaches ******************************1***************************************** class Solution { public: int dp[1002][1002][4]; int cal(int i , int prev ,int taken , vector &arr) { if(taken > 3) return 0; if(i == arr.size()) { return taken == 3 ?1:0; } if(dp[i][prev][taken]!=-1) return dp[i][prev][taken]; int t = 0; if(prev == arr.size()+1 || arr[prev] < arr[i]) { t = cal(i+1 , i , taken +1 , arr); } int nt = cal(i+1 , prev , taken ,arr); return dp[i][prev][taken] = t + nt; } int cal2(int i , int prev ,int taken , vector &arr) { if(taken > 3) return 0; if(i == arr.size()) { return taken == 3 ?1:0; } if(dp[i][prev][taken]!=-1) return dp[i][prev][taken]; int t = 0; if(prev == arr.size()+1 || arr[prev] > arr[i]) { t = cal2(i+1 , i , taken +1 , arr); } int nt = cal2(i+1 , prev , taken ,arr); return dp[i][prev][taken] = t + nt; } int numTeams(vector& arr) { int n = arr.size(); memset(dp , -1 ,sizeof(dp)); int a = cal(0 , n+1 , 0 , arr); memset(dp , -1 ,sizeof(dp)); int b =cal2(0 , n+1 , 0 ,arr); return a+b; } }; ****************************************2***************************************** #include #include using namespace std; using namespace __gnu_pbds; typedef tree pbds; // find_by_order, order_of_key class Solution { public: int numTeams(vector& rat) { int n = rat.size(); pbds a , b; for(int i = 2 ; i < n ; i++) b.insert(rat[i]); a.insert(rat[0]); int ans = 0; for(int i = 1 ; i

[@jain_saiyam]

Sir solution of constest problems

[@raveenakumari6724]

bhaiya iska dp aur binary tree wala approach ki video bnaye

[@jewelchakraborty9717]

Check my comment for the dp solution.

[@nish0798]

@codestorywithMik bro please tell why this approach is failing basically i am finfding increasing and decreasing triplets sepatly and adding them class Solution { //was not able to sove initilly took 55 misn public int numTeams(int[] rating) { int increasing = countStrictlyIncreasing(rating); int decreasing = countStrictlyDecreasing(rating); return increasing + decreasing; } public int countStrictlyIncreasing(int[] rating) { int count = 0; for (int i = 0; i < rating.length - 2; i++) { int j = i + 1; int k = rating.length - 1; while (j < k) { if (rating[i] < rating[j] && rating[j] < rating[k]) { // Found a valid increasing triplet count++; j++; k--; } else if (rating[j] rating[j] && rating[j] > rating[k]) { // Found a valid decreasing triplet count++; j++; k--; } else if (rating[j] >= rating[i]) { // Move j forward to find a lower middle element j++; } else { // Move k backward to find a higher right element k--; } } } return count; } } please reply

[@adityaraj-zm7zk]

#codestorywithMIK bhai k = j+1 se kaise start hpga batana

[@GauravDuseja-t6q]

Bhaiya kal ke contest ka 3rd problem please bhaiya

[@purushottamkumar6554]

bhaiya iss question ka video banayiye. 1260. Shift 2D Grid .

[@monsteri2417]

class Solution { public: int solve(int i,int prev,vector&rating,int k){ if(k==0)return 1; if(irating[prev]){ left = solve(i-1,i,rating,k-1); } right=solve(i-1,prev,rating,k); return left+right; } int numTeams(vector& rating) { int n=rating.size(); int ans= solve(n-1,-1,rating,3); reverse(rating.begin(),rating.end()); ans+=solve(n-1,-1,rating,3); return ans; } }; This is the basic recursion code i have wrote run 66/72 test case and when i try to memoize it with map of string it will run 60 test case btw your explanation is too good !!

[@manasdeora4601]

Beautiful

[@18_comp_b_shashankmishra87]

how did u came with this soln smallest left and largest righ ..mere dimak mai kyu nhi aya yeh

[@molyoxide8358]

With time everything will start happening

[@newglobal7271]

DP DP DP ..... Bhaiya dekho na iss dp( LIS ) solution me kya gadbadi hai 2 example test case pass ho raha hai first wala nehi ho raha hai btw uppke dp ka playlist is 🧡🧡 class Solution { public: int solveUsingRe(int prev, int i, vector& rating, int count, bool isIncreasing, vector& dp) { if (count == 3) return 1; if (i >= rating.size()) return 0; if (dp[i][count][isIncreasing] != -1) { return dp[i][count][isIncreasing]; } int include = 0; if (prev == -1 || (isIncreasing && prev < rating[i]) || (!isIncreasing && prev > rating[i])) { include = solveUsingRe(rating[i], i + 1, rating, count + 1, isIncreasing, dp); } int exclude = solveUsingRe(prev, i + 1, rating, count, isIncreasing, dp); return dp[i][count][isIncreasing] = include + exclude; } int numTeams(vector& rating) { int n = rating.size(); vector dp(n, vector(4, vector(2, -1))); return solveUsingRe(-1, 0, rating, 0, true, dp) + solveUsingRe(-1, 0, rating, 0, false, dp); } };

[@harshgarg9768]

memoize prev also

[@newglobal2056]

Bro runtime error dekha Raha hai prev ka size kya lu??​@@harshgarg9768

[@gui-codes]

4 variables are changing in your approach. you need to have 4D dp I think 4 D memoization k bina bhi kar sakte hain. See the code below from leetcode. class Solution { public: int numTeams(vector& rating) { int n = rating.size(); int teams = 0; vector increasingCache(n, vector(4, -1)); vector decreasingCache(n, vector(4, -1)); // Calculate total teams by considering each soldier as a starting point for (int startIndex = 0; startIndex < n; startIndex++) { teams += countIncreasingTeams(rating, startIndex, 1, increasingCache) + countDecreasingTeams(rating, startIndex, 1, decreasingCache); } return teams; } private: int countIncreasingTeams(const vector& rating, int currentIndex, int teamSize, vector& increasingCache) { int n = rating.size(); // Base case: reached end of array if (currentIndex == n) return 0; // Base case: found a valid team of size 3 if (teamSize == 3) return 1; // Return cached result if available if (increasingCache[currentIndex][teamSize] != -1) { return increasingCache[currentIndex][teamSize]; } int validTeams = 0; // Recursively count teams with increasing ratings for (int nextIndex = currentIndex + 1; nextIndex < n; nextIndex++) { if (rating[nextIndex] > rating[currentIndex]) { validTeams += countIncreasingTeams( rating, nextIndex, teamSize + 1, increasingCache); } } // Cache and return the result return increasingCache[currentIndex][teamSize] = validTeams; } int countDecreasingTeams(const vector& rating, int currentIndex, int teamSize, vector& decreasingCache) { int n = rating.size(); // Base case: reached end of array if (currentIndex == n) return 0; // Base case: found a valid team of size 3 if (teamSize == 3) return 1; // Return cached result if available if (decreasingCache[currentIndex][teamSize] != -1) { return decreasingCache[currentIndex][teamSize]; } int validTeams = 0; // Recursively count teams with decreasing ratings for (int nextIndex = currentIndex + 1; nextIndex < n; nextIndex++) { if (rating[nextIndex] < rating[currentIndex]) { validTeams += countDecreasingTeams( rating, nextIndex, teamSize + 1, decreasingCache); } } // Cache and return the result return decreasingCache[currentIndex][teamSize] = validTeams; } };

[@vishalkurve93]

// Ran perfectly fine for 66 test cases then it gave TLE. // Can anyone tell it how to memoize it. int solve(int i, int prev, vector& arr, int count, bool flag) { if (i >= arr.size()) { if (count == 3) { return 1; } return 0; } if (count == 3) { return 1; } int take = 0, ntake = 0; if (arr[i] > prev) { if (!flag) { take += solve(i + 1, arr[i], arr, count + 1, flag); } } else { if (flag == 1 || count == 1) take += solve(i + 1, arr[i], arr, count + 1, 1); } ntake += solve(i + 1, prev, arr, count, flag); return take + ntake; } int numTeams(vector& rating) { // subsequence problem return solve(0, -1, rating, 0, 0); }

[@priyak-vo7uu]

class Solution { public: int solve(vector& rating, vector& temp, int i) { if(temp.size() == 3) { if((temp[0] < temp[1] && temp[1] < temp[2]) || (temp[0] > temp[1] && temp[1] > temp[2])) { return 1; } return 0; } if (i >= rating.size()) { return 0; } temp.push_back(rating[i]); int include = solve(rating, temp, i + 1); temp.pop_back(); int exclude = solve(rating, temp, i + 1); return include + exclude; } int numTeams(vector& rating) { vector temp; return solve(rating, temp, 0); } };

[@nehagautam3492]

bhaiya OA nikalwao....., OA hi nhi clear ho rha

[@anonymoustrolls7952]

IT EVEN ACCEPETD O(N^3) using 3 forloops here is sol in O(N^2) tq for video int numTeams(vector& r) { int s = 0; int n = r.size(); //increasing for(int j=1;j

[@kartikforwork]

chatgpt unknown method- pls someone explain class Solution { public: int numTeams(vector& rating) { int n = rating.size(); if (n < 3) return 0; int inc_teams = 0; int dec_teams = 0; vector inc_dp(n, 0); vector dec_dp(n, 0); // Count all increasing and decreasing subsequences of length 3 for (int j = 0; j < n; ++j) { for (int i = 0; i < j; ++i) { if (rating[i] < rating[j]) { inc_dp[j]++; inc_teams += inc_dp[i]; // every valid increasing subsequence of length 2 ending at i extends to length 3 } else if (rating[i] > rating[j]) { dec_dp[j]++; dec_teams += dec_dp[i]; // every valid decreasing subsequence of length 2 ending at i extends to length 3 } } } return inc_teams + dec_teams; } };

[@shinjomoxuba8779]

ye galt kyu dera hai 10th test case ke baad class Solution { public: int ans = 0; void solve(vector& rating, int i, vector &maxi, vector &mini) { if(maxi.size() == 3) { ans++; return; } if(mini.size() == 3) { ans++; return; } if(i >= rating.size()) { return; } if( maxi.size()== 0 || maxi[maxi.size()-1] < rating[i]) { maxi.push_back(rating[i]); solve(rating, i+1, maxi,mini); maxi.pop_back(); } if( mini.size()== 0 || mini[mini.size()-1] > rating[i]) { mini.push_back(rating[i]); solve(rating, i+1, maxi,mini); mini.pop_back(); } //return solve(rating, i+1, maxi, mini); return; } int numTeams(vector& rating) { vector maxi; vector mini; solve(rating, 0,maxi,mini); return ans; } };

[@internetworking345]

Itna hype and time waste ,… Life is bigger bro to enjoy