Leetcode 1498 - Number of Subsequences That Satisfy the Given Sum Condition - Python

Practicing with Pen and Paper can be helpful too! (affiliate)

0:00 - Conceptual
5:55 - Coding solution

#Coding #Programming #CodingInterview #leetcode #neetcode

[dsudharaka]

I have to tell you this man. I have seen lot of videos.. however your explanations always are the best. I hope you will keep doing this. Great work & Thank you.

[NeetCode]

What did you all think of this problem?

[ChiCity]

Where is the 2^2 coming from at 3:23? It's not very clear to me whats happening here. Can you explain the math behind that a bit more?

[raziahmed]

@NeetCode Can you please do a complexity analysis of this algorithm? If we are iterating through the sorted array to find how far the rightBound goes for each leftBound, isnt it O(N^2) time complexity?

[anshulgoel]

Good explanation. But could have included more use cases to understand all the use cases

[jiteshtokas]

thanks for great explanation.. i was totally confused in the contest xD...bro are you on linkedin?

[danielsun]

the execution time is over 8000ms. probably leads an TLE.
we can change 2 ** (r - i) to be (1<<(r - i)) in python. That gonna save a lot of time.
BTW, in python, x<<n means x * (2 ** n). x >> n means x / (2 ** n).
Also, we could use two ptrs to slove this problem, same idea with neetcode.

class Solution:
def numSubseq(self, nums: List[int], target: int) -> int:
# # 2 ptrs
# nums.sort()
# res = 0
# mod = int(10 ** 9 + 7)
# l, r = 0, len(nums) - 1
# while l <= r:
# if nums[l] + nums[r] > target:
# r -= 1
# else:
# res = (res + (1<<(r - l))) % mod
# l += 1
# return res

# neetcode
nums.sort()
res = 0
mod = (10 ** 9 + 7)
r = len(nums) - 1
for i, left in enumerate(nums):
while left + nums[r] > target and i <= r:
r -= 1
if i <= r:
res += 1<<(r - i)

return res % mod

[michaelliplaying]

two pointers - it is O(n) time complexity, right?

[infiniteloop]

A more efficient python solution

class Solution:
def numSubseq(self, nums: list[int], target: int) -> int:
nums.sort()
l, r = 0, len(nums) - 1
ans = 0
mod = 10**9 + 7
while l <= r:
if nums[l] + nums[r] > target:
r -= 1
else:
ans += pow(2, r - l, mod)
l += 1
return ans % mod

[emilmohaneriksson]

One thing I will never understand is how one comes up with these ideas🤣. Great video though!

[unnhao]

i use brute force to list all Subsequences, but answer is not right...

[Prince-olzk]

You seem to breeze through backtracking. Could you explain the purpose of backtracking? Like what is backtracking actually doing? I dont understand the 2^n stuff you did