my Solution using dp. public int largestSqurtStreak(int[]nums){ int n=nums.length; int[]dp=new int[100001]; int max=0; for(int num:nums){ max=Math.max(max,num); dp[num]=1; } int ans=-1; for(int i=(int)Math.sqrt (max);i>=2;i--){ if(dp[i]==0) continue; if(dp[i*i]==0) continue; dp[i]=1+dp[i*i]; ans=Math.max(ans,dp[i]); } return ans; } 🎉❤
using unordered set : class Solution { public: int longestSquareStreak(vector& nums) { unordered_setset(nums.begin(),nums.end()); int ans=0; for(auto num : nums){ int count=0; long long temp=num; while(set.find(temp)!=set.end()){ count++; temp = temp * temp; if(temp > INT_MAX || temp < 0)break; } ans=max(ans,count); } return (ans==1) ? -1 : ans ; } };
My solution without sorting and using set : Hope it will help others public int betterSolution(int[] nums) { int n = nums.length; HashSet set = new HashSet(); for (int i : nums) { set.add((long)i); } int ans = -1, count = 0; for (int i : nums) { long ele = i; while (set.contains(ele)) { count++; ele *= ele; } ans = Math.max(ans, count); count = 0; } return ans >= 2 ? ans : -1; }
My Approach: class Solution { public: int longestSquareStreak(vector& nums) { int n = nums.size(); unordered_set st; for(int it : nums){ st.insert(it); } int maxi = *max_element(nums.begin(),nums.end()); int maxCnt = -1; for(int i=0;i
class Solution { public: int longestSquareStreak(vector& nums) { unordered_set st(begin(nums), end(nums)); int maxStreak = 0; for(int &num : nums) { int streak = 0; long long curr = num; long long root=sqrt(curr);
if(root*root==curr && st.find(sqrt(curr))!=st.end())continue; // 1e5) { break; } curr = curr*curr; } maxStreak = max(maxStreak, streak); } return maxStreak < 2 ? -1 : maxStreak; } }; We could void few unnecessary checks from here!!
Bhaiya mere dimag mein bhi pehle backtracking aaya tha subsequence word ko dekh kar, par tle aa sakta hai kiyuki constraints high hai to aur koi approach nehi aaya, isiliye video dekh ne k baad hi solve hua
In my first look to this problem the approach came to my mind is solving using (Recursive + Memoization) but failed to solved it's giving memory limit exceed.... How to increase memory thinking in such a way so that we can also think in first approach as you solved in your video... Any guidance for all of us who were at the same level as me in approaching problems....
Actually i noticed many people thought of solving it using Recursion, backtracking etc. Glad to know you are thinking about other ways to solve it. Actually, if I honestly describe how I identify backtracking : If the problem involves exploring multiple choices or paths, especially when aiming to find combinations, permutations, or subsets under specific constraints. It’s effective for recursive solutions that require "backing out" of invalid paths, making it ideal for constraint satisfaction (e.g., N-Queens or Sudoku) and finding optimal paths. If a problem asks to explore or find paths in trees or graphs, or when exhaustive search with pruning is feasible, backtracking can be a good approach to navigate solutions efficiently. But you can definitely solve this problem using recursion (not backtracking to be specific) if you wish : class Solution { public: void solve(long long start, int length, const set& numSet, int& maxLength) { if (length >= 2) { maxLength = max(maxLength, length); } long long nextNum = start * start; if (start * start > 1e5) return; if (nextNum > 0 && numSet.count(nextNum)) { solve(nextNum, length + 1, numSet, maxLength); } } int longestSquareStreak(vector& nums) { sort(nums.begin(), nums.end()); set numSet(nums.begin(), nums.end()); int maxLength = -1; for (int num : nums) { solve(num, 1, numSet, maxLength); } return maxLength; } }; Also see the pinned comment , it has bottom up dp approach which is also fine.
Hey MIK, I have solved it myself but still posting my classical LIS template solution, although it is giving TLE but it will give more confidence to those who are currently doing your DP concept playlist, to make them realise that why your DP playlist is best: Approach -1 : Recursion + Memoization ( it is almost same as Leetcode-1027) class Solution { public: int dp[100001]; int solve(vector& nums,int j){ if(dp[j] != -1) return dp[j]; int result=0; for(int idx=j+1;idx
Will the time complexity of the approach below can be considered O(n) or is it O(n*log(maxNumber)). Can someone pls clarify? n = len(nums) s = set(nums) maxi = 0 for i in range(n): num = nums[i] cnt = 1 if sqrt(num) not in s: while num*num in s: cnt+=1 num = num*num maxi = max(maxi,cnt) return maxi if maxi>1 else -1
I directly came up with binary search approach first and when it got AC, that feeling was great. Thanks for your teachings class Solution { public: int longestSquareStreak(vector& nums) {
int mx = -1e9; sort(nums.begin(),nums.end()); for(int i=0;i
bro why didnt you think of backtracking meaning how did you think of this approach instead of backtracking shouldnt by seeing subsequence you should have gone for it first? please explain i am getting confused on recursion very much
Glad to know you are thinking about other ways to solve it. Actually, if I honestly describe how I identify backtracking : If the problem involves exploring multiple choices or paths, especially when aiming to find combinations, permutations, or subsets under specific constraints. It’s effective for recursive solutions that require "backing out" of invalid paths, making it ideal for constraint satisfaction (e.g., N-Queens or Sudoku) and finding optimal paths. If a problem asks to explore or find paths in trees or graphs, or when exhaustive search with pruning is feasible, backtracking can be a good approach to navigate solutions efficiently. But you can definitely solve this problem using recursion (not backtracking to be specific) if you wish : class Solution { public: void solve(long long start, int length, const set& numSet, int& maxLength) { if (length >= 2) { maxLength = max(maxLength, length); } long long nextNum = start * start; if (start * start > 1e5) return; if (nextNum > 0 && numSet.count(nextNum)) { solve(nextNum, length + 1, numSet, maxLength); } } int longestSquareStreak(vector& nums) { sort(nums.begin(), nums.end()); set numSet(nums.begin(), nums.end()); int maxLength = -1; for (int num : nums) { solve(num, 1, numSet, maxLength); } return maxLength; } };
In this problem, generating all subsequences would be inefficient because most subsequences would not meet the requirement that each element in the sorted subsequence is a square of the previous element. Why Not Use Backtracking Here? Specific Requirement: The problem specifies that a valid subsequence must consist of numbers that are squares of the previous numbers. Therefore, we don’t need to consider all possible subsequences (e.g., sequences like [1, 2, 3] would be irrelevant). Direct Calculation: By focusing only on sequences where each element is a square of the previous, we can check each number and build a sequence directly, without generating all subsequences first. This allows us to use efficient techniques like sorting and binary search to find the valid square streaks. When to Use Backtracking for Subsequences Backtracking or recursion is ideal for generating all subsequences when: 1. No specific pattern exists in the subsequence structure. 2. The problem requires us to consider every combination without a defined relationship between elements (e.g., all subsets, all paths). 3. There’s no shortcut to eliminate certain sequences upfront based on a specific rule.
Brother look at the constraints, it is 10^5. We can only apply backtracking if the constraints are very very low i.e for eg below 12 length. Hope it will help you
Ways I identify backtracking is 1) The constraint is below 15 or 20 2) Keywords are "generate", "all" 3) Your own observation, here generating all subsequences is already worthless given constraints and also the fact that you'll have many useless subsequences as well If you identified LIS here, then you did well because in first glance it looks like a LIS variant. However, if you try to simplify the LIS you'll realise it can be solved without going the DP route and just using Binary Search and set to track who has been processed (makes sense because let's say 2 4 16 is the sequence, why would you check 4 again anyway you'll always get smaller length now). Once you finish Binary Search approach here, you should realise that set can be used purely because inherently it also uses BS to search in the set and you optimise it further. Map is also a valid approach here, essentially a hashing approach is the main crux of this question
i tried doing it using priority queue but tle😂: class Solution { public: int longestSquareStreak(vector& nums) { sort(nums.begin(),nums.end()); int sz = INT_MIN; for(int i = 0;i= 2 ? sz : -1; } };
@codestorywithMIK bro please reply why this code not working i AM using STACK class Solution { public int longestSquareStreak(int[] nums) { Arrays.sort(nums); Stack st=new Stack(); st.push(nums[0]); for(int i=1;i
first i solved like knapsack problem but it gave me TLE class Solution { public: int solve(vector& nums,map&mp,int i,map &dp){ if(i>=nums.size()){ return 0; } // take if(dp.find({mp,i})!=dp.end()){ return dp[{mp,i}]; } int left=0; int right=0; if(mp.empty()){ mp[nums[i]]++; left=1+solve(nums,mp,i+1,dp); mp.erase(nums[i]); } else{ if(mp.find(nums[i])==mp.end()){ double x=sqrt(nums[i]); // cout
![ทุกครั้งที่หลับตา (Lucid Dream) - AYLA's [ Official MV ]](http://i.ytimg.com/vi/4i1OBAQyv58/mqdefault.jpg)
my Solution using dp.
public int largestSqurtStreak(int[]nums){
int n=nums.length;
int[]dp=new int[100001];
int max=0;
for(int num:nums){
max=Math.max(max,num);
dp[num]=1;
}
int ans=-1;
for(int i=(int)Math.sqrt (max);i>=2;i--){
if(dp[i]==0) continue;
if(dp[i*i]==0) continue;
dp[i]=1+dp[i*i];
ans=Math.max(ans,dp[i]);
}
return ans;
}
🎉❤
very nice.
I have pinned you solution. I like this and hope others will find it useful😇
Its Amazing bro🙌
nice one! , i used a unordered_set and a var mx which stores the max elem , when num * num > mx it breaks
using unordered set :
class Solution {
public:
int longestSquareStreak(vector& nums) {
unordered_setset(nums.begin(),nums.end());
int ans=0;
for(auto num : nums){
int count=0;
long long temp=num;
while(set.find(temp)!=set.end()){
count++;
temp = temp * temp;
if(temp > INT_MAX || temp < 0)break;
}
ans=max(ans,count);
}
return (ans==1) ? -1 : ans ;
}
};
My solution without sorting and using set : Hope it will help others
public int betterSolution(int[] nums) {
int n = nums.length;
HashSet set = new HashSet();
for (int i : nums) {
set.add((long)i);
}
int ans = -1, count = 0;
for (int i : nums) {
long ele = i;
while (set.contains(ele)) {
count++;
ele *= ele;
}
ans = Math.max(ans, count);
count = 0;
}
return ans >= 2 ? ans : -1;
}
That observation in last >>>
I thought it would be somewhere O(n^2) but then Sir MIK is arrived
superb sir
i solved this using set
and here i learned a new approach to solve this problem
I was able to solve this using set but always here to watch your video as there's always somethings to learn ❤
Done and easy one today 😇
Here to support you MIK
awesome explanation of sir 🥰
Sir , sieve of eratosthenes, segmented sieve par video 👍
Gfg se dekhle bhai aasan h
My Approach:
class Solution {
public:
int longestSquareStreak(vector& nums) {
int n = nums.size();
unordered_set st;
for(int it : nums){
st.insert(it);
}
int maxi = *max_element(nums.begin(),nums.end());
int maxCnt = -1;
for(int i=0;i
class Solution {
public:
int longestSquareStreak(vector& nums) {
unordered_set st(begin(nums), end(nums));
int maxStreak = 0;
for(int &num : nums) {
int streak = 0;
long long curr = num;
long long root=sqrt(curr);
if(root*root==curr && st.find(sqrt(curr))!=st.end())continue; // 1e5) {
break;
}
curr = curr*curr;
}
maxStreak = max(maxStreak, streak);
}
return maxStreak < 2 ? -1 : maxStreak;
}
};
We could void few unnecessary checks from here!!
EG
[2,4,6,8]
This code will check for only and skip for rest
Nice,thanks.
Bhaiya mere dimag mein bhi pehle backtracking aaya tha subsequence word ko dekh kar, par tle aa sakta hai kiyuki constraints high hai to aur koi approach nehi aaya, isiliye video dekh ne k baad hi solve hua
In my first look to this problem the approach came to my mind is solving using (Recursive + Memoization) but failed to solved it's giving memory limit exceed.... How to increase memory thinking in such a way so that we can also think in first approach as you solved in your video... Any guidance for all of us who were at the same level as me in approaching problems....
Actually i noticed many people thought of solving it using Recursion, backtracking etc.
Glad to know you are thinking about other ways to solve it. Actually, if I honestly describe how I identify backtracking :
If the problem involves exploring multiple choices or paths, especially when aiming to find combinations, permutations, or subsets under specific constraints. It’s effective for recursive solutions that require "backing out" of invalid paths, making it ideal for constraint satisfaction (e.g., N-Queens or Sudoku) and finding optimal paths. If a problem asks to explore or find paths in trees or graphs, or when exhaustive search with pruning is feasible, backtracking can be a good approach to navigate solutions efficiently.
But you can definitely solve this problem using recursion (not backtracking to be specific) if you wish :
class Solution {
public:
void solve(long long start, int length, const set& numSet, int& maxLength) {
if (length >= 2) {
maxLength = max(maxLength, length);
}
long long nextNum = start * start;
if (start * start > 1e5)
return;
if (nextNum > 0 && numSet.count(nextNum)) {
solve(nextNum, length + 1, numSet, maxLength);
}
}
int longestSquareStreak(vector& nums) {
sort(nums.begin(), nums.end());
set numSet(nums.begin(), nums.end());
int maxLength = -1;
for (int num : nums) {
solve(num, 1, numSet, maxLength);
}
return maxLength;
}
};
Also see the pinned comment , it has bottom up dp approach which is also fine.
class Solution {
private:
int check(vector&nums,int ind,int next,int &s,vector&v){
if(next==nums.size())return s;
if(v[ind]!=-1)return v[ind];
if((long long)nums[ind]*nums[ind]>1e5)return s;
if((long long)nums[next]==(long long)nums[ind]*nums[ind]){
s++;
check(nums,next,next+1,s,v);
}
else check(nums,ind,next+1,s,v);
return v[ind]=s;
}
public:
int longestSquareStreak(vector& nums) {
sort(nums.begin(),nums.end());
vectorv(nums.size(),-1);
int n=nums.size();
int maxi=0;
for(int i=0;i
Hey MIK, I have solved it myself but still posting my classical LIS template solution, although it is giving TLE but it will give more confidence to those who are currently doing your DP concept playlist, to make them realise that why your DP playlist is best:
Approach -1 : Recursion + Memoization ( it is almost same as Leetcode-1027)
class Solution {
public:
int dp[100001];
int solve(vector& nums,int j){
if(dp[j] != -1)
return dp[j];
int result=0;
for(int idx=j+1;idx
I am so happy to see someone did LIS template for this. I also had this in my mind.
Great job ♥️🙌
@@codestorywithMIK 😍😍
Hey MIK, I am thinking to do some beginner certification in cybersecurity. Can you guide which course to go for?
But sir, while calculating Time Complexity, we should also consider the TC for st.find(), right?
The average time complexity of find() in an unordered_set in C++ is O(1),
class Solution {
public:
int longestSquareStreak(vector& nums) {
sort(nums.begin(),nums.end());
int n = nums.size();
vectordp(n,1);
for(int i = 1;i < n; i++){
int sr = sqrt(nums[i]);
if(1LL*sr*sr == nums[i]){
int ind = lower_bound(nums.begin(),nums.end(),sr) - nums.begin();
if(ind < n && nums[ind] == sr) dp[i] = 1 + dp[ind];
else dp[i] = 1;
}
else dp[i] = 1;
}
int maxi = *max_element(dp.begin(),dp.end());
return maxi == 1 ? -1 : maxi;
}
};
Binary search code
Awesome
Nice one buddy. How did you get that logic?
Bro by the constraints and then observing the examples@@arnabsarkar5245
Bhaiya, aagr ham 10 ^ 5 wala constraint na de, phir TC : O(n^2) hoga kaya?
Solution with binary Search
class Solution {
public:
bool isPresent(int val,vector&nums)
{
int i=0;
int j=nums.size()-1;
while(ival)
{
j=mid-1;
}
else
i=mid+1;
}
return false;
}
int longestSquareStreak(vector& nums) {
sort(nums.begin(),nums.end());
unordered_setump;
int n=nums.size();
for(int i=0;i
bhaiya where we used auto and int please clarify this in the case of for each loop i am very confused @codestorywithMIK
You can use auto in places where you are either not sure about the data type or you don’t want to type the data type .
To be honest first intuition was to go for LIS...But unfortunately it is giving TLE.
Indeed it occurred to me as well
Also see the pinned comment, for bottom up clean code
thank you sir
Will the time complexity of the approach below can be considered O(n) or is it O(n*log(maxNumber)). Can someone pls clarify?
n = len(nums)
s = set(nums)
maxi = 0
for i in range(n):
num = nums[i]
cnt = 1
if sqrt(num) not in s:
while num*num in s:
cnt+=1
num = num*num
maxi = max(maxi,cnt)
return maxi if maxi>1 else -1
I use the DP + SORTING but got TLE😅
Test case no 66/91 ig😅
@@vinay9786 😂
@@psychologyfact2320 haha even i used the same approach and got tle:(
Similar to LIS
@@VIJAY-rq4ky exactly😅
I directly came up with binary search approach first and when it got AC, that feeling was great. Thanks for your teachings
class Solution {
public:
int longestSquareStreak(vector& nums) {
int mx = -1e9;
sort(nums.begin(),nums.end());
for(int i=0;i
solve by itself:
class Solution {
public:
int m, square, next;
int solve(int i, unordered_map& mp, vector& nums) {
if(mp.find(nums[i]) != mp.end()) {
return mp[nums[i]];
}
if(nums[i]>317) {
return 1;
}
square = nums[i] * nums[i];
auto it = std::find(nums.begin(), nums.end(), square);
next = 0;
if(it!=nums.end()) {
next = solve(it-nums.begin(), mp, nums);
}
if(next+1>m) m=next+1;
return mp[nums[i]] = 1 + next;
}
int longestSquareStreak(vector& nums) {
int n = nums.size();
m=-1;
unordered_map mp;
for(int i=0; i
First 🎉❤
bro why didnt you think of backtracking meaning how did you think of this approach instead of backtracking shouldnt by seeing subsequence you should have gone for it first?
please explain i am getting confused on recursion very much
Glad to know you are thinking about other ways to solve it. Actually, if I honestly describe how I identify backtracking :
If the problem involves exploring multiple choices or paths, especially when aiming to find combinations, permutations, or subsets under specific constraints. It’s effective for recursive solutions that require "backing out" of invalid paths, making it ideal for constraint satisfaction (e.g., N-Queens or Sudoku) and finding optimal paths. If a problem asks to explore or find paths in trees or graphs, or when exhaustive search with pruning is feasible, backtracking can be a good approach to navigate solutions efficiently.
But you can definitely solve this problem using recursion (not backtracking to be specific) if you wish :
class Solution {
public:
void solve(long long start, int length, const set& numSet, int& maxLength) {
if (length >= 2) {
maxLength = max(maxLength, length);
}
long long nextNum = start * start;
if (start * start > 1e5)
return;
if (nextNum > 0 && numSet.count(nextNum)) {
solve(nextNum, length + 1, numSet, maxLength);
}
}
int longestSquareStreak(vector& nums) {
sort(nums.begin(), nums.end());
set numSet(nums.begin(), nums.end());
int maxLength = -1;
for (int num : nums) {
solve(num, 1, numSet, maxLength);
}
return maxLength;
}
};
In this problem, generating all subsequences would be inefficient because most subsequences would not meet the requirement that each element in the sorted subsequence is a square of the previous element.
Why Not Use Backtracking Here?
Specific Requirement: The problem specifies that a valid subsequence must consist of numbers that are squares of the previous numbers. Therefore, we don’t need to consider all possible subsequences (e.g., sequences like [1, 2, 3] would be irrelevant).
Direct Calculation: By focusing only on sequences where each element is a square of the previous, we can check each number and build a sequence directly, without generating all subsequences first. This allows us to use efficient techniques like sorting and binary search to find the valid square streaks.
When to Use Backtracking for Subsequences
Backtracking or recursion is ideal for generating all subsequences when:
1. No specific pattern exists in the subsequence structure.
2. The problem requires us to consider every combination without a defined relationship between elements (e.g., all subsets, all paths).
3. There’s no shortcut to eliminate certain sequences upfront based on a specific rule.
Brother look at the constraints, it is 10^5. We can only apply backtracking if the constraints are very very low i.e for eg below 12 length. Hope it will help you
Ways I identify backtracking is
1) The constraint is below 15 or 20
2) Keywords are "generate", "all"
3) Your own observation, here generating all subsequences is already worthless given constraints and also the fact that you'll have many useless subsequences as well
If you identified LIS here, then you did well because in first glance it looks like a LIS variant. However, if you try to simplify the LIS you'll realise it can be solved without going the DP route and just using Binary Search and set to track who has been processed (makes sense because let's say 2 4 16 is the sequence, why would you check 4 again anyway you'll always get smaller length now).
Once you finish Binary Search approach here, you should realise that set can be used purely because inherently it also uses BS to search in the set and you optimise it further. Map is also a valid approach here, essentially a hashing approach is the main crux of this question
@@codestorywithMIK thanks
i tried doing it using priority queue but tle😂:
class Solution {
public:
int longestSquareStreak(vector& nums) {
sort(nums.begin(),nums.end());
int sz = INT_MIN;
for(int i = 0;i= 2 ? sz : -1;
}
};
3rd 🎉
@codestorywithMIK bro please reply why this code not working i AM using STACK
class Solution {
public int longestSquareStreak(int[] nums) {
Arrays.sort(nums);
Stack st=new Stack();
st.push(nums[0]);
for(int i=1;i
first i solved like knapsack problem but it gave me TLE
class Solution {
public:
int solve(vector& nums,map&mp,int i,map &dp){
if(i>=nums.size()){
return 0;
}
// take
if(dp.find({mp,i})!=dp.end()){
return dp[{mp,i}];
}
int left=0;
int right=0;
if(mp.empty()){
mp[nums[i]]++;
left=1+solve(nums,mp,i+1,dp);
mp.erase(nums[i]);
}
else{
if(mp.find(nums[i])==mp.end()){
double x=sqrt(nums[i]);
// cout
Second 🎉
khandani dp + memoo gave TLE 😞
Thank you sir