Elements belonging to the same duration

Question

Given a vector of a sorted timestamps in microseconds, I need to determine the size of elements belonging to the same duration (say second).

My idea is to iterate over the vector until the last element belonging to the same duration, do this for each element and return the size of the biggest sub-vector.

Is there a smarter idea (with low time complexity) ?

Answer 1

I expect those posting comments are suggesting something like the following. This is Ruby code, but I readers who do not know Ruby can view it as pseudo code and should have no difficulty following it, particularly because I've displayed the results of intermediated calculations.

Suppose

arr = [1, 1, 3, 5, 5, 6, 6, 6, 6, 8, 8, 9, 9, 9]

A "current index" will always point to the first value in a group. In this example it will take on values 0 (the first 1), 2 (the first 3), 3 (the first 5), 5 (the first 6), 9 (the first 8) and 11 (the first 9).

The method bsearch_index performs a binary search to return the index of the next higher value relative to a current index. If, for example, the current index is 3 (the first 5), bsearch_index will return 5 (the first 6). If there is no greater value than that at the current index (here when the current index is 11, pointing at the first 9), bsearch_index returns nil and there is an adjustment that can be seen in the code.

best = { :val=>nil, :len=>-Float::INFINITY }
curr_idx = 0
curr_val = arr[curr_idx]

arr.each do |x|
  puts
  puts "x = #{x}, curr_idx = #{curr_idx}, curr_val = #{curr_val}, best = #{best}"
  i = arr.bsearch_index { |x| x > curr_val }  
  i = arr.size if i.nil?
  puts "i from bsearch_idx = #{i}"

  diff = i - curr_idx
  puts "diff = #{diff}"

  if diff > best[:len]
    puts "best updated"
    best = { :val=>curr_val, :len=>diff }
  end

  break if i == arr.size
  curr_idx = i
  curr_val = arr[curr_idx]
end

puts
puts best

The following is displayed.

x = 1, curr_idx = 0, curr_val = 1, best = {:val=>nil, :len=>-Infinity}
i from bsearch_idx = 2
diff = 2
best updated

x = 1, curr_idx = 2, curr_val = 3, best = {:val=>1, :len=>2}
i from bsearch_idx = 3
diff = 1

x = 3, curr_idx = 3, curr_val = 5, best = {:val=>1, :len=>2}
i from bsearch_idx = 5
diff = 2

x = 5, curr_idx = 5, curr_val = 6, best = {:val=>1, :len=>2}
i from bsearch_idx = 9
diff = 4
best updated

x = 5, curr_idx = 9, curr_val = 8, best = {:val=>6, :len=>4}
i from bsearch_idx = 11
diff = 2

x = 6, curr_idx = 11, curr_val = 9, best = {:val=>6, :len=>4}
i from bsearch_idx = 14
diff = 3

{:val=>6, :len=>4}

The desired array, [6, 6, 6, 6] can be easily constructed from the final value of best.

A binary search works well when there are many instances of each value. On the other hand, if there are many different values and few instances of each it may be faster to simply enumerate the array, avoiding the overhead involved in performing a binary search.