Finding consecutive occurrences of a value in an array

Question

Given an array, return True if the array contains consecutive occurrences of a specified value:

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

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

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

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

• Gareth Rees: Good use of the pairwise recipe there.

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

Answer 3

By searching from front and back, you do save time for cases like [1, 2] * 1000 + [2], but you make other cases slower. Unless you know that your data is such that you benefit from it, it's probably a bad idea.

I'd just use a forward iterator, keep trying to find another 2 and checking whether the next value is 2 as well:

def has22(nums):
 it = iter(nums)
 while 2 in it:
 if next(it, None) == 2:
 return True
 return False

If you were willing to use itertools, it would be super simple:

from itertools import pairwise
def has22(nums):
 return (2, 2) in pairwise(nums)

With just built-ins, you could still do it this way:

def has22(nums):
 it = iter(nums)
 next(it)
 return (2, 2) in zip(nums, it)

Or if your array only contains ints from 0 to 255:

def has22(nums):
 return bytes((2, 2)) in bytes(nums)