Counting frequencies of Element in an array

Question

Given an array of size $N$. I need to find the count of values in range $[L, R]$ which are repeated at least three times in successive positions (i.e., the value occurs contiguously three times).

For eg- \begin{align*} A&= 1,1,1,2,2,1,5,1,1,2,2,2,5,5 \\ L&=0,\ R=3\,, \end{align*} the answer would be 1 (1,1,1) and 2 (2,2,2).

I tried it by doing the following:

  answer = 0
  count[] = 0
  for i in {l..r}:
    count[array[i]]++
    if count[array[i]] == 3:
      answer++

But this will count frequencies all over the range and not just the contiguous ones. So the answer will include $5$ as well where as it shouldn't.

How do I treat any element that starts again after some other integers come in between to be different (like here I need to treat $5$'s count differently) and consider it again for it be $\geq 3$ ? Like can I hash them somehow?

Update :Logic being same, some modification in code. I shift the $L,R$ as the function is called multiple times and increase and decrease the count.

add(position):
  count[array[position]]++
  if count[array[position]] == 3:
    answer++

remove(position):
  count[array[position]]--
  if count[array[position]] == 2:
    answer--

currentL = 0
currentR = 0
answer = 0
count[] = 0
for given L,R
  // currentL should go to L, currentR should go to R
  while currentL < L:
    remove(currentL)
    currentL++
  while currentL > L:
    add(currentL)
    currentL--
  while currentR <= R:
    add(currentR)
    currentR++
  while currentR >R+1 :
    remove(currentR)
    currentR--
  output answer

I need to calculate for many pairs of L,R .So I need an efficient algorithm. The above algorithm seems to do so.

But How do I differentiate the contiguous triplets here ?

Answer 1

Maybe this:

answer = 0
lastVal = -1    //some value not inside [L,R]
count = 0
for i in {l..r}:
  if (array[i] != lastVal)
     count = 1
     lastVal = array[i]
  else
     count++
     if (count == 3)
        count = 0
        answer++

Edit: This code assumes that the set (1,1,1,1) is counted as one triplet not two. i.e.: (1,1,1) and (1), not (1,1,1) and (1,1,1)

Answer 2

In a language with good sequence facilities, such as Clojure, we can answer such questions directly:

(defn triples-in-range [low high coll]
  (->> coll
       (partition 3 1)
       (filter #(apply = %))
       (map first)
       (filter (set (range low (inc high))))))

For example,

(def data [1,1,1,2,2,1,5,1,1,2,2,2,5,5])

(triples-in-range 0 3 data)
;=> (1 2)

There are faster ways to do this. It's an example of a search that would benefit from something like the Knuth-Morris-Pratt algorithm.

The above is working code. You don't have to get the details to understand that the accurate and concise expression of an algorithm in terms of telling abstractions blows away oceans of speculation.

Answer 3

Here is a solution in sudo code.

set count =0;

get current element in array: x move to next element: y check if next element is equal to previous element: is x=y if true do count ++ if false reset count to 0. when count = 2: save that element in your result.

You can format your output the way you want. Here i put the output in a string result.

This is in Java

    int[] data  = new int[]{1,1,1,2,2,1,5,1,1,2,2,2,5,5,4,7,7,7};
    int count   = 0;
    int L       = 0;
    int R       = 3;

    String result="";

    for (int i = 0; i < data.length-1; i++)
    {
        if((data[i] == data[i+1]) && (data[i]>L && data[i]<R) )
        {
            count = count+1;
        }
        else
        {
            count =0;
        }

        if(count >= 2) //AT LEAST 3 times in successive positions
        {
            result = result +","+data[i]   ;
        }
    }

    if(result.length()>0)
    {
        result = result.substring(1);
    }
    else
    {
       result = "No values in the range are repeated!";
    }
    System.out.println(result);

Answer 4

If you need to execute multiple queries on this, you could do a mixture of what Nathaniel and David Richerby suggested. First preprocess the array and determine which elements are the last element of a triple. You could return a new array which if index $i$ is true, means element $i$ is the third element of a triple. This takes $O(n)$.

find-third-elements-in-triples(arr):

  thirds = new boolean array same length as arr, initialized all to false

  c = 1
  for i in {1 ... length(arr)}:
    if arr[i] != arr[i - 1]:
      c = 1
    else:
      c += 1
      if c >= 3:
        thirds[i] = true

  return thirds

A side note, for input [1,1,1,1], it would return [f,f,t,t], meaning this includes overlapping triples. It also can satisfy the "repeated at least three times" stipulation.

Now from their, each query is relatively simple to handle. Iterate from $l+2$ (the third element) to $r$ and see how many elements are the third element of a triple and this will tell you how many triples are in the segment $[l, r]$. This will take $O(r-l) = O(n)$ time.

query(arr, l, r):

  // You could keep the 'third-element' array as a single instance array of some sort
  if thirds == null:
    thirds = find-third-elements-in-triples(arr)

  count = 0
  // start at the third element
  for i in {l+2 ... r}:
    if thirds[i] and !thirds[i+1]:
      count += 1

  return count

Note: you can remove the and !thirds[i+1] code if you're treating overlapping triples as separate triples. Otherwise that check basically says, "we're not at the end of our contiguous sequence yet, so we're not ready to increase the count".

To get faster than $O(r-l)$ for each query, you could look into creating a Fenwick Tree out of the thirds array to make queries in $O(\log n)$. You would treat false as 0 and true as 1, then calculate interval sums to find out how many thirds are in your interval.

Answer 5

If you want to stick to array data-structure then following is a java code that I wrote using dataarray from TimeTrax's answer.I have provided comments for understanding and I hope you can implement it in your preferred programming language.

int[] data  = new int[]{1,1,1,1,1,1,1,2,2,1,5,5,5,3,1,1,2,2,2,5,5,4,7,7,7};  //creating an array
String result="";                         //creating a string for printing final output
for (int i=2;i<data.length;i++){          // loop over the array, start from the third element

    if(data[i-2]==data[i]){               //if the first element matches the third element
        if(data[i-1]==data[i]){           //and if the second element matches the third element
            result=result+data[i]+",";    //then append the third to the list of triplets which is the result string
            i=i+2;                        //and move the pointer to the sixth element for checking fourth,fifth and sixth element for possibility of next triplet and so on
        }
    }
}

System.out.print(result);                 // printing out result string

The Output is as follows

1,1,5,2,7,

Each number is a representation of a its triplet

The complexity of the above code however remains in O(n). I have made a little optimization so that the more triplets you have in comparison to the size of the array the lesser will be the running time of the loop.The best it can give is when you have all triplets in your array(i.e. The loop will run 1/3 rd times the size of your array).

If you think you want more optimization then consider @ryan's suggestion about Fenwick Tree

Answer 6

answer = 0
last = null    
count = 0
foreach value in array   
   if (last != null) 
       if (value == last) 
          count++
       else 
          if count >= 3 then answer++ 
          count = 0
   last = value
if count >= 3 then answer++