0
$\begingroup$

I'm working on the LeetCode problem "The Number of Beautiful Subsets".

I came up with a solution that runs in O(n^2 * 2^n). It's a very simple and obviously naive solution.

I use bitmasks, and define the forbidden couples of integers like so:

forbidden: set[int] = set()
for i in range(n):
    for j in range(i + 1, n):
        if abs(nums[j] - nums[i]) == k:
            forbidden.add((2**i) + (2**j))

and then I look at all the possible bitsets and check if they "conflict" with one of the at most n^2 elements of forbidden:

ans: int = 0
for i in range(1, 2**n):
    for forbidden_couple in forbidden:
        if (i & forbidden_couple) == forbidden_couple:
            break
    else:
        ans += 1

My solution runs in 1 second.

There is another solution with a time complexity of O(n * 2^n). This should be about n times faster than mine. I implemented it both recursively and iteratively. Here is the iterative version I used: https://pastebin.com/7KYye7f3. That iterative solution takes 9.7 seconds, and the recursive version takes 11 seconds, which is about 10 times slower than my naive solution.

I'm not putting too many details on that solution because there is a O(2^n) solution that is, too, slower (4 seconds instead of 1) than my O(n^2 * 2^n) solution. Even though it should be n^2 faster. It uses a hashmap and recursion, similarly to algorithms trying to find the longest path in a graph.

class Solution:
    def beautifulSubsets(self, nums, k):
        
        def beautifulSubsetsRec(idx, count):
            if idx == len(nums):
                return 1
            
            res = beautifulSubsetsRec(idx + 1, count)
            if not count[nums[idx] + k] and not count[nums[idx] - k]:
                count[nums[idx]] += 1
                res += beautifulSubsetsRec(idx + 1, count)
                count[nums[idx]] -= 1
        
            return res
    
        return beautifulSubsetsRec(0, Counter()) - 1  # -1 to remove the empty set

PS: I'm not trying to understand how to achieve an O(n log n) solution (which is possible), but just trying to make sense of the inconsistency in the theory of complexity.

$\endgroup$
4
  • $\begingroup$ Two comments: 1) Your solution's run time can be more tightly bounded by $O(|F|2^n)$, where $F$ is the set of forbidden pairs; this is at most $\Theta(n^2)$ but it could easily be smaller. 2) I presume you've tested the output of your solution? Because perhaps it's a (computer) language barrier, but the else in your bitset check seems like it would bind to the if and therefore be inside the for loop, not the "If we get all the way through the forbidden without finding anything, count it as an answer" I would've expected. $\endgroup$ Commented May 23 at 20:01
  • 1
    $\begingroup$ (@StevenStadnicki: the else in your bitset check seems like it would bind to the if …if the language wasn't Python, which is used as a language tag for that code block. (Python is not the only programming language allowing an else-clause with loops…)) $\endgroup$
    – greybeard
    Commented May 23 at 20:46
  • $\begingroup$ @greybeard That would be the language barrier I mentioned. :-) Thank you! $\endgroup$ Commented May 23 at 22:48
  • $\begingroup$ @StevenStadnicki Both codes output the exact same results on every test case I tried. I agree with your analysis but I'd argue since F is at most O(n^2) (and it's easy to reach that), I don't see why it would be faster. $\endgroup$ Commented May 24 at 6:14

2 Answers 2

1
$\begingroup$

Turns out Leetcode tests are just weak. I could find test cases such that the O(n^2 * 2^n) solution takes ages compared to the other two (nums = [1, 2]*10, k = 1).

$\endgroup$
1
$\begingroup$

Big-O doesn’t take constant factors into account. Modern computers can do 64 bit operations at a time, that’s a factor n if n <= 64. And if the time is O(n 2^n) then I bet n <= 64. So one algorithm can run faster even if it does more operations.

Also, Big-O is often an upper bound. If you search for a solution, you may be able to show that you find it either within n^2 2^n steps, or within n 2^n steps, but in specific cases the first algorithm might find a solution a lot quicker.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.