0

How to solve this

Input: 2
Array = [2,1,3,2,2,2,1,2,2]
Result : 3 (Max of count of seq of 2)

I just simply used the for loop, it works fine. But is there any other efficient way?

for i in array:
    if i == input:
        Cnt = Cnt + 1
        if Cnt > Result:
            Result = Cnt;
    else:
      Cnt = 0
idjaw
  • 25,487
  • 7
  • 64
  • 83
Siva Kumar
  • 164
  • 1
  • 2
  • 9
  • 2
    Possible duplicate of [Find and list duplicates in Python list](http://stackoverflow.com/questions/9835762/find-and-list-duplicates-in-python-list) – idjaw Oct 17 '16 at 17:15
  • Do you want the length of the longest sequence of the given input, or the number of sequences? – Patrick Haugh Oct 17 '16 at 17:20
  • The two questions seem very different to me. The other asks for any method, while this asks for a more efficient method. The other asks to find duplicates, this asks for the longest sequence of duplicates. And so on. The only similarities seem to be a list and duplicates. – Rory Daulton Oct 17 '16 at 17:24
  • For time and space complexity, it can't get more efficient than what you have. Likewise for code comprehension. – user1952500 Oct 17 '16 at 18:49

3 Answers3

1

You can use itertools.groupby for this:

from itertools import groupby
max(sum(1 for i in g) for k, g in groupby(array) if k == input)
Patrick Haugh
  • 59,226
  • 13
  • 88
  • 96
1

You could seriously abuse side effects in a comprehension :-) :

Input = 2
Array = [2,1,3,2,2,2,1,2,2]
r = []
Result = max([(r.append(1),len(r))[1] if x==Input else (r.clear(),0)[1] for x in Array])

.

That kind of rigamarole wouldn't be necessary if Python allowed assignments in expressions:

r = 0
Result = max([++r if x==Input else r=0 for x in Array])   # What we want, but NOT valid Python!

Note that a generator expression could be used instead of the list comprehension if you don't want to look at the intermediate result. For the toy Array it doesn't matter, but for an Array of hundreds of thousands of elements the generator saves memory.

Dave
  • 3,834
  • 2
  • 29
  • 44
0

What I think your're describing can be solved with run length encoding.

Essentially, you take a sequence of numbers (most often used with characters or simply unsigned bytes) and condense it down into a list of tuples where one value represents the value, and the other represents how many times in a row it occurs.

array = [2,1,3,2,2,2,1,2,2]
runs = []
count = 0

current = array[0] #setup first iteration
for i in array:
    if i == current: #continue sequence
        count += 1
    else:
        runs.append([count, current]) #start new sequence
        current = i
        count = 1
runs.append([count, current]) #complete last iteration

longest_Sequence = max(runs)
Aaron
  • 10,133
  • 1
  • 24
  • 40