# One element only subarray max length

You are given a list and an item, find the length of the longest consecutive subsequence of the list containing only the item.

Testcases

[1, 1, 2, 3] 1 -> 2
[1, 0, 0, 2, 3, 0, 4, 0, 0, 0, 6] 0 -> 3


This code is pretty readable in my opinion but I fear that the $O(N^2)$ time complexity is sub-optimal.

def subsequences(arr)
((0...arr.length).to_a)
.repeated_permutation(2)
.select {|start, finish| finish >= start}
.collect {|start, finish| arr[start..finish] }
end

def longest_item_only_subsequence_len(arr, item)
subsequences(arr)
.select {|seq| seq.all? {|i| i == item} }
.max_by(&:length)
.length
end

p subsequences([1, 2, 3])
p longest_item_only_subsequence_len([1, 0, 0, 2, 3, 0, 4, 0, 0, 0, 6], 0)


Yes, chunk is the way to go. I'd write it differently, though, using a list-comphehension approach (in Ruby: map+if+compact. Or with a custom method.) and taking in account the edge case (no elements item in the array):

def longest_item_only_subsequence_len(xs, item)
xs.chunk(&:itself).map { |y, ys| ys.size if y == item }.compact.max || 0
end

• ys.size if y == item equals y == item ? ys.size : nil right? – Caridorc Aug 23 '15 at 7:59
• Right. In fact, I like it with ? better because it looks more like an expression, but the other looks more like a list-comprehension. Take your pick. – tokland Aug 23 '15 at 8:01
• As a minor comment, which spacing style is reccomended in Ruby? All on one line or each method call on its own line? – Caridorc Aug 23 '15 at 8:08
• IMO: if it fits in one line, one line. If I think it's too long, I give it a name and use it in another line. – tokland Aug 23 '15 at 8:09
• To me separate lines help for chronological order, top before, then bottom. It is subjective though. – Caridorc Aug 23 '15 at 8:11

After some more thinking, I realized that Array.chunk is O(N) and what I was looking for:

 def longest_item_only_subsequence_len(arr, item)
return 0 if ! arr.include?(item)
arr
.chunk(&:itself)
.select{|kind, _| kind == item}
.collect {|_, subseq| subseq}
.max_by(&:length)
.length
end

• This last length probably fails when arr has no item in it. – tokland Aug 23 '15 at 8:00
• @tokland I may just add a check at the start of the function, but maybe it should fail. Not finding a subsequence is exceptional. (An empty subsequence counts in your opinion?) – Caridorc Aug 23 '15 at 8:06
• Yes, I think the code should just work (return 0) if there is no item item in the sequence. – tokland Aug 23 '15 at 8:08