Solving a 2 Year Old Problem on Leetcode

Hey folks! Today I encounted a problem which I tried solving 2 years back (2023)

Question Link →

1498. Number of Subsequences That Satisfy the Given Sum Condition

So, looking at my 2 year old attempt, I wanted to challenge myself to solve it this time (DEVELOPER EGO!!)

Basically the problem demands us to get total number of possible pairs whose min and max (can be same number) is either less or equal to the given target.

My first throught: LET’S BRUTE FORCE!

So I wrote this (a solution containing 2 for loops giving us not so good time complexity)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        '''
            nums, target
            3 5 6 7

            3 + 6 = 9
                3, 6
                3, 5, 6

            Intunion: Starting with a digit how far can I go?

            2 ^ (n - 1)

        '''

        MOD = 10 ** 9 + 7

        # Sort the array
        nums.sort()

        l = len(nums)

        total = 0
        fenceIndex = l
        for i, e in enumerate(nums):

            # Not possible
            if e + e > target:
                break

            temp = 1

            for j in range(i + 1, fenceIndex):
                # print("Checking with", nums[j])
                if e + nums[j] <= target:
                    temp += 1
                else:
                    fenceIndex = j
                    break

            total += 2 ** (temp -1)

            # print("Result ", e, temp)

        return total % MOD

And you guessed it right! It failed due to time limit. 😕

My next idea was to bring down the time complexity, honestly speaking it took time to the time 😅 - Not sooo much but an hour for SURE ⏳

Then it CLICKED! Using two variables (pointers) for the rescue!⛑️

This is quite common method when you want to find some paris, it is used in sorted arrays so that we know when to move the pointers. My idea is to have two pointers a and b.

a will start the very begining (index = 0)

b will start at the very end (index = length - 1)

This gives us opportunity to try out all the possible options for the ranges that falls under our solutions bucket!

So start with a = 0, we decrese pointer b’s value until nums[a] + nums[b] <= target

Once we get a range which statisfies this, we find the difference (b - a) this gives us length of the range

now using this range, diff = b - a : we get the possible solutions which start with a

eg. 2 ^^ diff

(Think of this as switch for all the numbers in between we can either on or off so 2 possible values) and exponent to diff which gives us all the various combinations!

FINAL SOLUTION!

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        '''
           Slinding window
           How many can be formed with "a" as start
           Move "b" until valid range           
        '''

        MOD = 10 ** 9 + 7

        # Sort the array
        nums.sort()

        l = len(nums)

        a = 0
        b = l - 1

        total = 0
        while a <= b:
            s = nums[a] + nums[b]
            if s <= target:
                diff = b - a
                total += 2 ** diff
                a += 1
            else:
                b -= 1


        return total % MOD

And (Drumrollss 🥁🥁🥁🥁🥁🥁……..)

It worked! Mission Passed ✅ 😎

Time to be Self Critical! 😅

Looking at my previous submission from 2023. I can prodly say I did make it more complicated that it is. I don’t know what the hell I was trying to achieve.

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        # Handler for length 1
        if len(nums) == 0:
            if nums[0] <= target:
                return 1
            return 0

        a = 0
        b = 0
        nums.sort()
        ans = 0
        ib = False
        c = 0

        print("check", nums)

        increaseA = False
        while a < len(nums) and b < len(nums):

            minVal = nums[a]
            maxVal = nums[b]

            s = minVal + maxVal
            print(minVal, maxVal, s)
            if s <= target:
                ans += 1
                c += 1      
            else:
                increaseA = True            

            if increaseA or b == len(nums) - 1:
                print("NEW A", c)

                if c >= 2:
                    x = c - 2
                    if x >= 2:            
                        ans += math.factorial(x)

                    ans += x

                a += 1
                b = a
                increaseA = False
                c = 0
            else:
                b += 1                        
        return ans

Problems:

• Too many variables

• Naming convention?

  • “ib” = guess what’s that? 😅

• Wrong message on logs (Just to confuse them😜)

  • print("NEW A", c)

Honestly speaking I don’t know what’s going on here? Getting hard time looking at my code. Ofcouse it did make sense at that time. But not for today😄 Eventhough it does feel good to see the improvement.

“The more you know, the more you know you don’t know” - Aristotle

Even today’s code is not so great - so yeah let’s wait until leetcode spins the timewheel and we optimize it futher! ⏳👍