3
\$\begingroup\$

I am new to python.

Got a question in Hackerrank.

Given an Array of bad numbers and a range of integers, how can I determine the longest segment of integers within that inclusive range that doesn't contain a bad number?

For example, you are given the lower limit l = 3 and the upper limit r = 48, The array badNumbers = [37,7,22,15,49,60]. Segments without bad numbers are [3,6], [8,14], [16,21], [23,36] and [38,48]. The longest segment is [23,36] and it is 14 elements long.

Problem : Function Description Complete the function goodStatement in the editor below. The function must return an integer denoting the length of the longest contiguous range of natural number in the range l to r, inclusive, which does not include any bad numbers.

goodSegment has the following parameter(s): badNumbers[badNumbers[0],...badNumbers[n-1]]: an array of integers l: an integer, the lower bound, inclusive r: an integer, the upper bound, inclusive

Constraints \$1 \le n \le 10^5\$, \$1 \le badNumbers[i] \le 10^9\$, badNumbers contains distinct elements

def goodSegment(badNumbers, l, r):
    ranges = []
    subrange = []
    large=0
    for i in range(l,r+1):
        if badNumbers.count(i)==0:
            if len(subrange)==0:
                subrange.append(i)
            else:
                if i==r:
                    subrange.append(i)
                    ranges.append(subrange)
                    if len(range(subrange[0],subrange[1]+1))>large:
                        large=len(range(subrange[0],subrange[1]+1))
        else:
            if len(subrange)==1:
                subrange.append(i-1)
                ranges.append(subrange)
                if len(range(subrange[0],subrange[1]+1))>large:
                    large=len(range(subrange[0],subrange[1]+1))
                subrange=[]
            else:
                subrange=[]
    
    return large

badNumbers=[5,4,2,15]
l=1
r=10
    
result = goodSegment(badNumbers, l, r)
print(result)

The code is working fine. But this is not getting executed in 10 seconds as per the hackerrank test cases. How can I optimize this for a faster execution?

\$\endgroup\$
1
  • 2
    \$\begingroup\$ The code does ranges.append(subrange) , but never uses ranges. That's a lot of extra work if n is large. \$\endgroup\$ – RootTwo Feb 3 at 18:38
7
\$\begingroup\$

PEP 8

The Style Guide for Python Code lists many recommendations:

  • variables & functions should be snake_case
  • commas should be followed by a space
  • binary operators should be surrounded by a space (eg, l == r instead of l==r, and r + 1 instead of r+1)

Some of the function/variable names may be dictated to you by the coding challenge, but for all others you should follow the PEP 8 conventions.

Optimizations

Loop range

for i in range(l, r + 1):

Assuming your range is 1 to \$10^9\$, this loop will take more than 10 seconds if the code inside the loop takes more than 10 nanoseconds per iteration. That's asking a lot for an interpreted language. You would do better if that loop can be removed.

More on this in a moment.

Counting -vs- existence

if badNumbers.count(i)==0:

You are searching the list of bad numbers counting the number occurrences of the value i in the list.

badNumbers contains distinct elements

Because badNumbers contains unique elements, the count will be either 0 or 1. More over, as soon as we find the first match, we can stop counting even if uniqueness was guarenteed, since we are testing the count against zero. What you really want is simply to ask if the value i is in badNumbers. You write that exactly how we said it:

if i in badNumbers:

This is still an \$O(n)\$ operation, but would be faster. As mentioned in another answer, turning badNumbers into a set would speed that up into an \$O(1)\$ operation. But let's investigate another option.

Reducing data

Your example badNumbers = [37, 7, 22, 15, 49, 60] with limits l=3 and r=48 reveals more inefficiency. The badNumbers contains numbers outside of the limits. Looking at those numbers over and over again (such as in badNumbers.count(i) == 0 or i in badNumbers) is wasted time.

We can filter out the "bad" bad numbers which end up just wasting time.

badNumbers = [number for number in badNumbers if l <= number <= r]

Organizing your data

You are looping over your candidate numbers, and then effectively searching to see if the candidate number is in the bad numbers list. If that list was sorted, you could just maintain an index to the next unmatched bad number, and increment it each time a match was found.

Combining that with the previous step:

badNumbers = sorted(x for x in badNumbers if l <= x <= r)

Now in your example, the badNumbers would be [7, 15, 22, 37]

Now, it = iter(badNumbers) would create an iterator which could walk over the list, in order, bad_number = next(it) could extract the next bad number from the list, and we've gotten rid of that pesky index I mentioned above, too.

But I'd really like to get rid of that first loop, so lets take a different approach.

Gap Length and End Posts

[7, 15, 22, 37]

In this array, we can immediately see there are 15-7-1 good numbers between the first two bad numbers, 22-15-1 between the next pair, and 37-22-1 between the last pair. This is almost all we need to get the longest run of good numbers!

What is missing is the good number runs at the beginning and end of the list. We can fix that by adding some "end posts", extra bad numbers one beyond the good range end points:

badNumbers = [l - 1] + sorted(x for x in badNumbers if l <= x <= r) + [r + 1]

With limits of l=3 and r=48, this creates badNumbers = [2, 7, 15, 22, 37, 49].

Now, every pair of numbers can be used to determine the length of a run of good numbers.

pairwise

Since we want to take the numbers in pairs, it makes sense to consult the Python itertools library for an appropriate function. It isn't built-in, but the pairwise recipe can be installed from more-itertools.

Take the numbers as pairs, computing the number of good values between the pair of bad values, and remember the maximum value. The "minus 1" from the internal calculation can be delayed till the end, for efficiency, since \$\max{(x_i-1)} == \max{(x_i)} - 1\$

from more_itertools import pairwise

def goodSegment(bad_numbers, l, r):
    bad_numbers = [l - 1] + sorted(x for x in bad_numbers if l <= x <= r) + [r + 1]
    gap_lengths = (b - a for a, b in pairwise(bad_numbers))
    return max(gap_lengths) - 1

badNumbers = [5, 4, 2, 15]
l = 1
r = 10
    
result = goodSegment(badNumbers, l, r)
print(result)

If more-itertools is not available, you can make something almost equivalent

def pairwise(numbers):
    return zip(numbers[:-1], numbers[1:])

It may even be faster, although it will use up to three times more memory.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Isn’t it possible for this to be slower depending on the size of bad_numbers and the range being checked? I started thinking of something like this but assumed it could be slower since the sorting is \$ O(n * log(n)) \$ \$\endgroup\$ – my_first_c_program Feb 4 at 1:20
  • 2
    \$\begingroup\$ @my_first_c_program I'm certain there are m,n ranges where this may be slower, since sorting is \$O(n \log n)\$, but with with n ranging up to 10^5, the log n factor is only 16, where as with m ranging to 10^9, or n*10^4, then m+n becomes 10001*n. There are other constant factors to consider, of course, but a back of the envelope comparison give a factor of 600 advantage to the sorting, with both m & n at there limits. Of course, profiling actual implementations is really required. \$\endgroup\$ – AJNeufeld Feb 4 at 3:40
4
\$\begingroup\$

It’s \$ O(n * m) \$ because of badNumbers.count(i), n and m being the lengths of badNumbers and the range from left to right. You could reduce this to \$ O(n + m) \$ if you cast badNumbers to a set and check if i is in the set.

You’re doing a lot of unnecessary things in the function. You only need to keep track of the current amount and the largest amount of numbers you’ve seen in a row which weren’t in badNumbers. You don’t need to use any lists.

Btw, in a couple places you could make your current code flatter by using elif instead of using else and nested if/else blocks. Specifically if i==r: and if len(subrange)==1:. Those could be changed to elif, and then the bottom else block could be unindented.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Note: To get \$O(n + m)\$ you must assume set creation is an \$O(n)\$ operation and that in is always an \$O(1)\$ operation. The former isn't documented and the latter is the 'average case' where the worst case is \$O(n)\$. I have had sets explode to what seems like \$O(n^2)\$ before. \$\endgroup\$ – Peilonrayz Feb 4 at 3:35
  • \$\begingroup\$ @Peilonrayz Can you show us such an explosion case you had? \$\endgroup\$ – Kelly Bundy Feb 4 at 11:49
  • \$\begingroup\$ @KellyBundy Unfortunately I don't remember which project I had that exploded like this. Since I changed from sets to a 'worse' algorithm (\$O(n\log n)\$) I probably wouldn't be able to find it now. :( \$\endgroup\$ – Peilonrayz Feb 4 at 12:37
  • \$\begingroup\$ @Peilonrayz Do you know of any other? And sounds like it wasn't intentional, which is rather hard to believe then. \$\endgroup\$ – Kelly Bundy Feb 4 at 13:05
  • \$\begingroup\$ @KellyBundy Sure you're entitled to think I'm a liar. \$\endgroup\$ – Peilonrayz Feb 4 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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