1
\$\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\$
5
  • 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, 2016 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\$ Jun 15, 2016 at 13:40
  • 1
    \$\begingroup\$ itertools is part of the Python standard library, similar to xrange() in your code. \$\endgroup\$
    – syb0rg
    Jun 15, 2016 at 13:41
  • \$\begingroup\$ i believe xrange is built-in, but not itertools ?! \$\endgroup\$ Jun 15, 2016 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, 2016 at 14:01

2 Answers 2

5
\$\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, as you've written it, intends to look forwards and backwards, consequently, this causes the code to use more memory than needed. It also adds to the complexity of the code, thus making it harder 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))
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Good use of the pairwise recipe there. \$\endgroup\$ Jun 15, 2016 at 16:02
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
\$\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.