Finding consecutive occurrences of a value in an array

Question

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)

Answer 1

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))

Answer 2

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