0
\$\begingroup\$

Given an array, return True if the array contains consecutive values:

has22([1, 2, 2]) - True  
has22([1, 2, 1, 2]) -False  
has22([2, 1, 2]) - False

I do aware of a quick solution by iterating the list in a for loop and comparing current and next items for equality until it reaches the end, also using modules like itertools as pointed out by @syb0rg. However, I am asking this to learn algorithmic approach

Current Solution:

def has22(nums):
    total_occurrences = nums.count(2)

    if total_occurrences >= 2:

        forward_start = 0
        backward_start = 0
        reversed_nums = nums[::-1]
        last_item_index = len(nums) - 1

        for _ in xrange(total_occurrences/2 ):

            next_forward_occurrence = nums.index(2,forward_start)
            next_backward_occurrence=  last_item_index - reversed_nums.index(2, backward_start)

            if nums[next_forward_occurrence] == nums[next_forward_occurrence+1]:
                return True
            elif nums[next_backward_occurrence] == nums[next_backward_occurrence - 1]:
                return True

            forward_start = next_forward_occurrence
            backward_start = next_backward_occurrence

    return False

I would like to know if there is any other efficient algorithm (using only built-in methods, no modules/lib please)

\$\endgroup\$
  • 1
    \$\begingroup\$ Just to clarify, do we care about any number of consecutive occurrences for any value in an array, or just if there are two 2's next to each other? \$\endgroup\$ – syb0rg Jun 15 '16 at 13:32
  • \$\begingroup\$ @syb0rg any occurrences would do. thanks for your suggestion on itertools. However am looking for an algorithm not using lib/tools \$\endgroup\$ – user2390183 Jun 15 '16 at 13:40
  • 1
    \$\begingroup\$ itertools is part of the Python standard library, similar to xrange() in your code. \$\endgroup\$ – syb0rg Jun 15 '16 at 13:41
  • \$\begingroup\$ i believe xrange is built-in, but not itertools ?! \$\endgroup\$ – user2390183 Jun 15 '16 at 13:47
  • \$\begingroup\$ It is a standard library module. I've edited my answer for this exception in your question. \$\endgroup\$ – syb0rg Jun 15 '16 at 14:01
4
\$\begingroup\$

First off your code doesn't work as you want it too.

>>> has22([2, 1, 2, 2, 1, 2, 1])
False
>>> has22([2, 1, 2, 1, 2, 1, 2])
True

Your code also doesn't follow PEP8, and the name of your variables are, long, really long.

This code is kinda horrible as you intend to look forwards an backwards, and the way you've done this causes the code to use more memory than needed. And makes the code horrible to read. Instead if you make the code travel only one way, and change forward_start to prev_index and next_forward_occurrence to index, you can obtain:

def has22(nums):
    total_occurrences = nums.count(2)
    if total_occurrences >= 2:
        prev_index = 0
        for _ in xrange(total_occurrences - 1):
            index = nums.index(2, prev_index)
            if nums[index] == nums[index + 1]:
                return True
            prev_index = index + 1
    return False

I don't like the use of nums.count(2) as it causes the algorithm to become \$O(2n)\$. Instead I'd break upon index becoming -1.

def has22(nums):
    prev_index = 0
    while True:
        index = nums.index(2, prev_index)
        if index == -1:
            break
        if nums[index] == nums[index + 1]:
            return True
        prev_index = index + 1
    return False

But both of these are still, harder to read compared to the algorithm that you stated in the question.

I do aware of a quick solution by iterating the list in a for loop and comparing current and next items for equality until it reaches the end

Here is the algorithm you're talking about:

def has22(nums):
    nums = iter(nums)
    prev = next(nums, StopIteration)
    if prev is not StopIteration:
        for num in nums:
            if num == prev and num == 2:
                return True
            prev = num
    return False

Where a simpler approach would use any and zip, and a smarter approach would also use itertools.

def has22(nums):
    return any(num1 == num2 and num1 == 2 for num1, num2 in zip(nums, nums[1:]))

from itertools import tee, izip

def has22(nums):
    a, b = tee(nums)
    next(b, None)
    return any(num1 == num2 and num1 == 2 for num1, num2 in izip(a, b))
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Good use of the pairwise recipe there. \$\endgroup\$ – Gareth Rees Jun 15 '16 at 16:02
  • 1
    \$\begingroup\$ @user2390183 Your algorithm is slower than the any zip one which has a time complexity of \$O(n)\$ where yours was \$O(3n)\$. nums.count(2) is \$O(n)\$ and nums[::-1] is \$O(n)\$, so you go through the entire list twice before starting your 'fast' approach. And what about lists with 2, 2 in the middle? Your algorithm, if implemented correctly, would find them on the last loop. Your algorithm is not 'fast'. It's not slow (\$O(n^2)\$), but it's not fast. \$\endgroup\$ – Peilonrayz Jun 16 '16 at 9:01
  • \$\begingroup\$ Finally I got a good code review comment that was expecting. Thanks Joe Wallis. The reason for 2-way search : Searching 1 way would take N - 1 iteration to solve a really large list with only one occurrence at the end of the list. i.e [1,.....large list of items........2,2] . As I had concern about having to reverse the whole list and maintaining 2 copies of the list, I posted this. It is quicker but more memory as pointed out I agree. \$\endgroup\$ – user2390183 Jun 16 '16 at 9:02
  • \$\begingroup\$ @JoeWallis: \$O(3n)\$ is the same as \$O(n)\$ (because big-O notation ignores constant factors). When you're concerned with speed (rather than asymptotic efficiency) you need to compare timings. \$\endgroup\$ – Gareth Rees Jun 16 '16 at 9:04
  • \$\begingroup\$ @GarethRees Thank you, I'll stop saying \$O(3n)\$, as I just mean it'll do three \$O(n)\$ operations, should I instead say, "it performs three \$O(n)\$ operations", or should I just ignore them all together and leave it at just "it's \$O(n)\$" as big-O notation does (for future reference). \$\endgroup\$ – Peilonrayz Jun 16 '16 at 9:20
3
\$\begingroup\$

You could use itertools.groupby(), and then if there is a group greater than 1 output true. However, it's in a module, which you don't want . If you look at the link, it shows how the method is implemented (though I see no reason to reinvent the wheel).


Small example showing how groupby() works:

>>> import itertools
>>> l = [1, 1, 1, 4, 6]
>>> max(len(list(v)) for g,v in itertools.groupby(l))
3
| improve this answer | |
\$\endgroup\$

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.