CODEWITHSUNDEEP
rubyarraysperformancealgorithm
Jasdeep Singh
Jasdeep Singh

Reputation: 3326

count the number of consecutive integer elements in an array

Given I have an array such as follows: 

arr = [8, 13, 14, 10, 6, 7, 8, 14, 5, 3, 5, 2, 6, 7, 4]

I would like to count the number of consecutive number sequences. Eg in the above array the consecutive number sequences (or array-slices) are:

[13,14]
[6,7,8]
[6,7]

And hence we have 3 such slices. What is an efficient Algorithm to count this? I know how I can do it O(N^2) but I'm looking for something which is better than that.

Upvotes: 0

Views: 1922

Answers (4)

steenslag
steenslag

Reputation: 80065

arr = [8, 13, 14, 10, 6, 7, 8, 14, 5, 3, 5, 2, 6, 7, 4]
p arr.each_cons(2).chunk{|a,b| a.succ == b || nil}.count #=> 3

nilhas a special meaning to the chunk-method: it causes items to be dropped.

Upvotes: 4

Arup Rakshit
Arup Rakshit

Reputation: 118271

I would do as below using Enumerable#slice_before:

a = [8, 13, 14, 10, 6, 7, 8, 14, 5, 3, 5, 2, 6, 7, 4]
prev = a[0]
hash = Hash[a.slice_before do |e|
  prev, prev2 = e, prev
  prev2 + 1 != e
end.map{|e| [e,e.size] if e.size > 1}]
hash # => {[13, 14]=>2, [6, 7, 8]=>3, [6, 7]=>2}
hash.size # => 3

Upvotes: 1

Timothy
Timothy

Reputation: 4487

arr = [8, 13, 14, 10, 6, 7, 8, 14, 5, 3, 5, 2, 6, 7, 4]
result = []
stage = []
for i in arr:
    if len(stage) > 0 and i != stage[-1]+1:
        if len(stage) > 1:
            result.append(stage)
        stage = []
    stage.append(i)
print result

Output:

    [[13, 14], [6, 7, 8], [6, 7]]

The time complexity of this code is O(n). (There's only one for loop. And it's not hard to see that each iteration in the loop is O(1).)

Upvotes: 2

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

I think this can be done in O(N) time. If you just want the count,

  1. Iterate through the array. Initialize counter to 0.
  2. If next element is one more or one less than current element, increment the counter.
  3. Continue iterating till the next element is not one more or one less than current element.
  4. Repeat steps 2 and 3 until you reach the end.

If you want sections of continuously increasing consecutive elements (not clear from your question)

  1. Iterate through the array. Initialize counter to 0.
  2. If next element is one more than current element, increment the counter.
  3. Continue iterating till the next element is not one more than current element.
  4. Repeat steps 2 and 3 until you reach the end.

Upvotes: 0

Related Questions