This is the best solution i found for this problem. many thanks. I just added few lines to Avoid TLE in Same Code. class Solution { public List countSmaller(int[] nums) { List res = new ArrayList(); if(nums == null || nums.length == 0) return res;
// TRICK TO AVOID TLE STARTS ------------------------------------------- boolean isAscendingArrray = true; for(int i = 0; i < nums.length-1; i++) { if(nums[i] > nums[i+1]) { isAscendingArrray = false; break; } } if(isAscendingArrray) { List list = new ArrayList(); for(int i = 0; i < nums.length; i++) { list.add(0); } return list; }
boolean isdecendingArrray = true; for(int i = 0; i < nums.length-1; i++) { if(!(nums[i] >= nums[i+1])) { isdecendingArrray = false; break; } } int diffCount = 0; int repeatCount = 0; if(isdecendingArrray) { List list = new ArrayList(); list.add(0); for(int i = nums.length-2; i >= 0 ; i--) { if(nums[i] > nums[i+1]) { diffCount += repeatCount; list.add(++diffCount); repeatCount = 0; } else { list.add(diffCount); repeatCount++; } } Collections.reverse(list); return list; } // TRICK TO AVOID TLE ENDS -------------------------------------------------
TreeNode root = new TreeNode(nums[nums.length - 1]); res.add(0); for(int i = nums.length - 2; i >= 0; i--) { int count = insertNode(root, nums[i]); res.add(count); } Collections.reverse(res); return res; } public int insertNode(TreeNode root, int val) { int smaller = 0; TreeNode temp = new TreeNode(val); boolean isConnected = false; while(!isConnected) { if(temp.data
This is also a brute force, N^2 time complexity (TLE). In worst case, like (1 2 3 4 5 6 7), all nums have 0 count of smaller values, and in the iteration, we will go to the left most sub tree. To be clear, the tree is not a balanced tree, so we cannot ahieve N * log N time. I would say it even have more space complexity than nested for-loop solution (O(1) space).
@@codebix1096 your code is showing TLE on leetcode what other logic can be added to make it sufficient..I don't want to use segment trees..please suggest some logic in binary search tree only..
![เขามัทรี - เอ็กซ์ ศุภกฤต - จอนนี่มิวสิค [ Official MV ]](http://i.ytimg.com/vi/AS9ufKuQIVs/mqdefault.jpg)
Bhai algorithm bta ke kya fayeda... intution bta or waise ye o(n^2) approach hai
you are a fabulous teacher.
This is the best solution i found for this problem. many thanks. I just added few lines to Avoid TLE in Same Code.
class Solution {
public List countSmaller(int[] nums) {
List res = new ArrayList();
if(nums == null || nums.length == 0) return res;
// TRICK TO AVOID TLE STARTS -------------------------------------------
boolean isAscendingArrray = true;
for(int i = 0; i < nums.length-1; i++) {
if(nums[i] > nums[i+1]) {
isAscendingArrray = false;
break;
}
}
if(isAscendingArrray) {
List list = new ArrayList();
for(int i = 0; i < nums.length; i++) {
list.add(0);
}
return list;
}
boolean isdecendingArrray = true;
for(int i = 0; i < nums.length-1; i++) {
if(!(nums[i] >= nums[i+1])) {
isdecendingArrray = false;
break;
}
}
int diffCount = 0;
int repeatCount = 0;
if(isdecendingArrray) {
List list = new ArrayList();
list.add(0);
for(int i = nums.length-2; i >= 0 ; i--) {
if(nums[i] > nums[i+1]) {
diffCount += repeatCount;
list.add(++diffCount);
repeatCount = 0;
} else {
list.add(diffCount);
repeatCount++;
}
}
Collections.reverse(list);
return list;
}
// TRICK TO AVOID TLE ENDS -------------------------------------------------
TreeNode root = new TreeNode(nums[nums.length - 1]);
res.add(0);
for(int i = nums.length - 2; i >= 0; i--) {
int count = insertNode(root, nums[i]);
res.add(count);
}
Collections.reverse(res);
return res;
}
public int insertNode(TreeNode root, int val) {
int smaller = 0;
TreeNode temp = new TreeNode(val);
boolean isConnected = false;
while(!isConnected) {
if(temp.data
This is also a brute force, N^2 time complexity (TLE). In worst case, like (1 2 3 4 5 6 7), all nums have 0 count of smaller values, and in the iteration, we will go to the left most sub tree. To be clear, the tree is not a balanced tree, so we cannot ahieve N * log N time. I would say it even have more space complexity than nested for-loop solution (O(1) space).
Agreed!
Isin't the worst-case complexity of this still O(n^2) only as what is the BST tree is one sided (skewed) to insert itself it will take O(n^2)
You can use avl tree instead of bst
it is not acceptable in leet code. it gives TLE Error
this solution is time limit exceeded on leetcode.
Next time plz explain with gesture bcz audio is very high my ear can't listen
Audio was low but really good explanation. Thanks for the upload. :)
Thanks Shashi 😄
Audio issue is fixed now check my new videos
You can subscribe to this channel for more such content 😁
join this facebook group to get updates of upcoming videos and discussions
facebook.com/groups/258049468776636/about
Why will be the count variable of node 1 be 1 if it represents the number of values less that self?
Here is only 8 line code
vector countSmaller(vector& nums) {
vectorv;
int n=nums.size();
vectorres(n);
if(n==0)
return res;
res[n-1]=0;
v.push_back(nums[n-1]);
for(int i=n-2;i>=0;i--)
{
v.insert(lower_bound(v.begin(),v.end(),nums[i]),nums[i]);
res[i]=lower_bound(v.begin(),v.end(),nums[i])-v.begin();
}
return res;
}
please tell the time complexity this solution??
What software, hardware did you use to write on mac and annotate live code at the same time?
Can't it be done with stack.
we get O(N^2) time complexity
what about 2 elements are both smaller than a previous element? e.g. [2, 3, 18] and [3, 2, 18]. They form the same BST, but the answer is different.
they dont form the same bst. our root is the last element. for the first example it is a skewed bst, the other one isnt skewed
Giving TLE on leetcode
Nice
Yeah I have followed you're FB page
join this facebook group to get updates of upcoming videos and discussions
facebook.com/groups/258049468776636/about
@@codebix1096 I have joined it I am rithik Agarwal
will this logic work when we have repeatition? like in the case of [-1,-1]?
yes it will work
github.com/luckykumardev/leetcode-solution/blob/master/count_of_smaller_number_after_self.java try this code on leetcode
join this facebook group to get updates of upcoming videos and discussions
facebook.com/groups/258049468776636/about
@@codebix1096 your code is showing TLE on leetcode what other logic can be added to make it sufficient..I don't want to use segment trees..please suggest some logic in binary search tree only..
1:00
Low audio
Hmm yes I also just noticed 😬
Maybe the is some issue with my mic.i will fix it soon. Sorry till then Please try some other headphones
1:00 When he add two