4:28 The time complexity was not really reduced from O(n2) to O(n), the new algorithm will run n + (n-1) + (n-2) + ... + 1 worst case, consider this example: nums = [0, 0, 0, ....., 10] k = 10 in this case, it will go through all the numbers in the first loop, then go through all the numbers except the first one and so on, so the time complexity is effectively still O(n2) but it is definitely more efficient than the original brute-force solution. Nice explanation by the way! this shows the importance of recognizing patterns in problems.
it is O(n), in your example the left pointer won't shrink until the right pointer reaches 10, at the end both pointers would point at same location , worst case each pointer traverses n elements, so complexity is n + n O(2n) = O(n)
@@NeetCodeIO I am talking about the input array `nums`, when you mentioned that we don't care to do redundant work 4:28 . The worst time complexity in that case (not the final solution which is O(n)) is O(n2) I believe, let me know if I misunderstood something please
Ah sorry, I was mistaken, when we find a special sub-array, we only move the left pointer to the right without also resetting the right pointer to the left pointer.
This might not be much of a performance improvement, but we can do range(len(bin(n) - 2) as a replacement for range(32) when setting bits in the bits array.
i did have the right idea and most optimal solution first try, but this one was a little difficult to code up, that's the hard thing about bit manipulation problems
class Solution: def minimumSubarrayLength(self, nums: List[int], k: int) -> int: res = float("inf") bits = [0] * 32 def bits_update(bits, n, diff): for i in range(32): if n & (1
min_length = float('inf') prev = {} # Maps OR value to minimal length for num in nums: curr = {} curr[num] = 1 for prev_or, prev_len in prev.items(): new_or = prev_or | num new_len = prev_len + 1 if new_or not in curr or curr[new_or] > new_len: curr[new_or] = new_len for or_val, length in curr.items(): if or_val >= k: min_length = min(min_length, length) prev = curr return min_length if min_length != float('inf') else -1
class Solution { fun minimumSubarrayLength(nums: IntArray, k: Int): Int { val n = nums.size var minLength = Int.MAX_VALUE var currentOR = 0 var start = 0 for (end in 0 until n) { currentOR = currentOR or nums[end] while (start = k) { minLength = minOf(minLength, end - start + 1) currentOR = currentOR and (currentOR.inv() or nums[start].inv()) start++ } } return if (minLength == Int.MAX_VALUE) -1 else minLength } } I was thinking what is wrong in this solution until I watch this video.
i coded the bruteforce soln..like in 2 min....but the optimized one is very hard to analyze...I understood the approach...but the "bit" thing is little wacky...shifting part ...removal
@@11csepratikshaargulewar71 brute force won't work on leetcode mine is here in java let me know if there is a mistake class Solution { public int minimumSubarrayLength(int[] nums, int k) { int n = nums.length; int sol = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { int count = 0; for (int j = i; j < n; j++) { count |= nums[j]; if (count >= k) { sol = Math.min(sol, j - i + 1); break; } } } return sol == Integer.MAX_VALUE ? -1 : sol; } }
@@11csepratikshaargulewar71 class Solution: def minimumSubarrayLength(self, nums: List[int], k: int) -> int: res = float("inf") l = 0 curr = 0 for r in range(len(nums)): curr |= nums[r] while curr >= k and l int: ans = 0 for num in nums: ans |= num return ans This was my "brute force approach" though it isn't exactly bruteforce since it doesnt check every single subarray, but it does recalculate the current bitwise or value for the subarray everytime it needs to shrink the window
from typing import List class Solution: def minimumSubarrayLength(self, nums: List[int], k: int) -> int: if k==0: return 1 ans = float('inf') for i in range(len(nums)): val = 0 right = i while val < k and right < len(nums): val |= nums[right] right += 1 if val >= k: ans = min(ans, right - i) return ans if ans != float('inf') else -1 this is direct approach...starting from each index move to possible sub arrays starting at index until the val >=k : once val is >=k the min subarray fro that index is got..so just break and go for next index..... this wll work for small test cases....but will get runtime erroor for large cases
i think it's easy but don't know why my 490th case is not clearing -- class Solution { public: int minimumSubarrayLength(vector& nums, int k) { int i = 0; int n = nums.size(); int total = 0; int ans = n+1; for(int j = 0 ; j=k && i
I was exaggerating a bit, since there are several components to this problem, maybe it's not 'easy'. But this problem falls into a very cookie cutter category of problems, that can easily be solved just be optimizing the brute force solution.
@@Shivam-gh2mq No. You must be a super fan. There is no point in saying that it's pretty efficient when it's worse than 75%. Just don't say anything at all or say that you think that it's random (which is a lie).
It is slow because of inefficient bit manipulation. One can improve it by avoiding bit shifts in a loop and also by avoiding computing cur_or from scratch every time. Otherwise the idea behind the solution is not bad.
@@NeetCodeIO Input size is always a factor. An accusation of not thinking critically is an ad hominem attack. There's no denying the original comment that the run shown in this video is worse than 75%. This is an objective truth. There's no need to gaslight.
4:28 The time complexity was not really reduced from O(n2) to O(n), the new algorithm will run n + (n-1) + (n-2) + ... + 1 worst case, consider this example:
nums = [0, 0, 0, ....., 10]
k = 10
in this case, it will go through all the numbers in the first loop, then go through all the numbers except the first one and so on, so the time complexity is effectively still O(n2) but it is definitely more efficient than the original brute-force solution.
Nice explanation by the way! this shows the importance of recognizing patterns in problems.
it is O(n), in your example the left pointer won't shrink until the right pointer reaches 10, at the end both pointers would point at same location , worst case each pointer traverses n elements, so complexity is n + n O(2n) = O(n)
@omdave1008 for each time we increase the left pointer we will have to traverse the full array to the right of the left pointer, so it is not O(2n)
Are you talking about the bits array? It's of constant size. The time complexity is definitely o(n)
@@NeetCodeIO I am talking about the input array `nums`, when you mentioned that we don't care to do redundant work 4:28 . The worst time complexity in that case (not the final solution which is O(n)) is O(n2) I believe, let me know if I misunderstood something please
Ah sorry, I was mistaken, when we find a special sub-array, we only move the left pointer to the right without also resetting the right pointer to the left pointer.
How do you guys solve bit manipulation problems? They tortured me all week.
ya bit manipulation is pain in the ass, only way is to practice from somewhere from to basics until you get start seeing the patterns
Always keep the binaries of numbers opened so that you can visualise what’s happening with the bits
Excellent video, really un-stucked me. I misunderstood the problem and spent an hour solving another version, until I saw this video.
This might not be much of a performance improvement, but we can do range(len(bin(n) - 2) as a replacement for range(32) when setting bits in the bits array.
For those that got confused on how OR'ing was done, res += (1
Most honorable guy in UA-cam
Love from Bangladesh
i did have the right idea and most optimal solution first try, but this one was a little difficult to code up, that's the hard thing about bit manipulation problems
Amazing thanks for the explanation!
class Solution:
def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
res = float("inf")
bits = [0] * 32
def bits_update(bits, n, diff):
for i in range(32):
if n & (1
Best explanation ever. other explanations demand Ph.D to understand what they explaining
so the array stores the reversed binary representation of the current or integer?
yea
why does xoring with nums[l] not work in this case?
Very good explanation
(1
min_length = float('inf')
prev = {} # Maps OR value to minimal length
for num in nums:
curr = {}
curr[num] = 1
for prev_or, prev_len in prev.items():
new_or = prev_or | num
new_len = prev_len + 1
if new_or not in curr or curr[new_or] > new_len:
curr[new_or] = new_len
for or_val, length in curr.items():
if or_val >= k:
min_length = min(min_length, length)
prev = curr
return min_length if min_length != float('inf') else -1
Subarray generate is n^3 ?
Yeah I guess to build each subarray, but to get the OR of each subarray is O(n^2) if done correctly
It can be done in n^2 too
Just Awesome
class Solution {
fun minimumSubarrayLength(nums: IntArray, k: Int): Int {
val n = nums.size
var minLength = Int.MAX_VALUE
var currentOR = 0
var start = 0
for (end in 0 until n) {
currentOR = currentOR or nums[end]
while (start = k) {
minLength = minOf(minLength, end - start + 1)
currentOR = currentOR and (currentOR.inv() or nums[start].inv())
start++
}
}
return if (minLength == Int.MAX_VALUE) -1 else minLength
}
}
I was thinking what is wrong in this solution until I watch this video.
i coded the bruteforce soln..like in 2 min....but the optimized one is very hard to analyze...I understood the approach...but the "bit" thing is little wacky...shifting part ...removal
Could you share your brute force approach?
@@11csepratikshaargulewar71 brute force won't work on leetcode mine is here in java let me know if there is a mistake
class Solution {
public int minimumSubarrayLength(int[] nums, int k) {
int n = nums.length;
int sol = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = i; j < n; j++) {
count |= nums[j];
if (count >= k) {
sol = Math.min(sol, j - i + 1);
break;
}
}
}
return sol == Integer.MAX_VALUE ? -1 : sol;
}
}
@@11csepratikshaargulewar71
class Solution:
def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
res = float("inf")
l = 0
curr = 0
for r in range(len(nums)):
curr |= nums[r]
while curr >= k and l int:
ans = 0
for num in nums:
ans |= num
return ans
This was my "brute force approach" though it isn't exactly bruteforce since it doesnt check every single subarray, but it does recalculate the current bitwise or value for the subarray everytime it needs to shrink the window
Please share your approach
from typing import List
class Solution:
def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
if k==0:
return 1
ans = float('inf')
for i in range(len(nums)):
val = 0
right = i
while val < k and right < len(nums):
val |= nums[right]
right += 1
if val >= k:
ans = min(ans, right - i)
return ans if ans != float('inf') else -1
this is direct approach...starting from each index move to possible sub arrays starting at index until the val >=k : once val is >=k the min subarray fro that index is got..so just break and go for next index.....
this wll work for small test cases....but will get runtime erroor for large cases
it's easy??
i think it's easy but don't know why my 490th case is not clearing -- class Solution {
public:
int minimumSubarrayLength(vector& nums, int k) {
int i = 0;
int n = nums.size();
int total = 0;
int ans = n+1;
for(int j = 0 ; j=k && i
@@Flux-e4y your logic for removing elements from the window isn't correct ig. total &= ~nums[i]
I was exaggerating a bit, since there are several components to this problem, maybe it's not 'easy'. But this problem falls into a very cookie cutter category of problems, that can easily be solved just be optimizing the brute force solution.
@@arkodasgupta0412 bu then how all 489 cases passed?
@@NeetCodeIO 714 test case pass , then TLE is coming
i was actually unbelievably close and just gave up yikes
thanks :)
Sorry but what is the name of the site in the video ? is that leet code ?!,,, and thank you for your great effort to simplify things
neetcode.io
correct
I am not getting it, skipping for now.
Yo neetcode, should I invest time into watching all of one piece, or would that time be better spent grinding leetcode?
5th comment
The problem is easy, but optimizing it is not.
Hey,
Why the same algorithm doesn't work in Java?
Worse than 75% is "pretty efficient"?
you must be new to this
@@Shivam-gh2mq No. You must be a super fan. There is no point in saying that it's pretty efficient when it's worse than 75%. Just don't say anything at all or say that you think that it's random (which is a lie).
It is slow because of inefficient bit manipulation. One can improve it by avoiding bit shifts in a loop and also by avoiding computing cur_or from scratch every time.
Otherwise the idea behind the solution is not bad.
Efficiency is relative to input size. Leetcode runtimes are not always relevant. Please think more critically
@@NeetCodeIO Input size is always a factor. An accusation of not thinking critically is an ad hominem attack. There's no denying the original comment that the run shown in this video is worse than 75%. This is an objective truth. There's no need to gaslight.