# Finding consecutive occurrences of a value in an array

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)

• 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? Commented Jun 15, 2016 at 13:32
• @syb0rg any occurrences would do. thanks for your suggestion on itertools. However am looking for an algorithm not using lib/tools Commented Jun 15, 2016 at 13:40
• itertools is part of the Python standard library, similar to xrange() in your code. Commented Jun 15, 2016 at 13:41
• i believe xrange is built-in, but not itertools ?! Commented Jun 15, 2016 at 13:47
• It is a standard library module. I've edited my answer for this exception in your question. Commented Jun 15, 2016 at 14:01

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


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

• Good use of the pairwise recipe there. Commented Jun 15, 2016 at 16:02

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