Simple Python


  • 13

    First build all increasing subsequences regardless of length, then filter out the too short ones.

    def findSubsequences(self, nums):
        subs = {()}
        for num in nums:
            subs |= {sub + (num,)
                     for sub in subs
                     if not sub or sub[-1] <= num}
        return [sub for sub in subs if len(sub) >= 2]

  • 0
    Z

    @StefanPochmann Nice, is there a clean way to generate the permutation without using set? To handling duplicates is a little tricky. Thanks


  • 0

    @zhongyuan9817 I have a post without vector hasher in C++ if you are interested. It just needs to decompose previous results into sections contributed from different array entries, so we can tell if we can append current entry to a previous result without duplication. Actually, handling of duplicates is the primary challenge, in my opinion.


  • 0
    Z

    @zzg_zzm Thanks a lot! I have bookmarked the link, will read later!


  • 0
    H

    @StefanPochmann That's an elegant solution. I am just wondering what would be the time complexity of this?


  • 1

    @harshaneel said in Simple Python:

    @StefanPochmann That's an elegant solution. I am just wondering what would be the time complexity of this?

    I am only speaking in terms of C++ since I am not familiar with Python.

    Without consideration of the time complexity of array hasher (not sure how Python handles it by default; C++ coder needs to define their own), the time complexity should be O(2^N) in worst case (when given array nums itself is increasing without duplicates).

    Note that the final result sub of num[i=1:N] is constructed from the previous result based on nums[i=1:N-1], so each additional new subsequences while looping through for num in nums are

    1. [nums[1]]
    2. [nums[2]], [nums[1], nums[2]]
    3. [nums[3]], [nums[1], nums[3]], [nums[2], nums[3]], [nums[1], nums[2], nums[3]]
      ...

    So there are maximum possible sub[k-1].size+1 new subsequences added when processing nums[k], where sub[k-1].size is the number of subsequences previously found. Therefore, the overall number of subsequences is O(2^N).

    Since duplicated sequences are not allowed, in my opinion, it might not be trivial for hash set of array to compute hash values. Again, I am not sure how Python handles it. But theoretically, the overall time complexity should be O(2^N*hasher(N)), where hasher(N) is the hash function on arrays with maximum size N.

    Therefore, I think the challenging point of this problem is how to handle duplicates of big size data (e.g., arrays). So choice of programming languages could provide convenience here.


  • 0
    This post is deleted!

  • 0

    @zzg_zzm Apparently hashing takes linear time, as doubling the size doubles the time:

    >>> from timeit import timeit
    >>> for e in range(15, 25):
    	seq = tuple(range(2**e))
    	print timeit(lambda: hash(seq), number=100)
    
    0.0127717597061
    0.0276374918723
    0.0563326366445
    0.160355203111
    0.262955346616
    0.516837713979
    1.08255762105
    2.06604952219
    4.24153727445
    8.48543233365
    

    But you only counted "substrings". The number of subsequences is exponential, O(2^N).


  • 0

    @StefanPochmann Thanks for the hasher testing. Intuitively, I think it's also O(N) which is the size of array.

    I have corrected the sequence count in my post. I don't know why I counted as O(N^2) before...


  • 0
    H

    @StefanPochmann said in Simple Python:

    return [sub for sub in subs if len(sub) >= 2]

    In the last line, sub is a tuple, in my opinion, this should return [(...), (...)],
    but actually it turns out to be right format: return [[...], [....]], but why??


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.