0
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ Thanks, that's much clearer. So why can't you use the method I suggested to count the number of contiguous triples for each integer that appears in the array and store the answers in a new array, say $B$. Then, use $B$ to determine the answer for each $(L,R)$ query. $\endgroup$ – David Richerby Apr 10 '17 at 13:45
  • $\begingroup$ @DavidRicherby It's not about the method. It's about how to differentiate multiple instances of contiguous occurrences of an integer. It would be great if you could help me with my code to differentiate them. $\endgroup$ – S.H. Apr 10 '17 at 14:09
  • 2
    $\begingroup$ I'm voting to close this question as off-topic because this is not about computer science, at best this should go to the codereview site. $\endgroup$ – gnasher729 Jul 12 '17 at 7:57
  • $\begingroup$ Find the triplets, sort them, use binary search to get the answer for each (l, r). For m requests, O (n log n + m log n). $\endgroup$ – gnasher729 Jul 12 '17 at 8:00
1
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Shouldn't the triplet be $(1,1,1)$ instead of (1,1,1,1) ? $\endgroup$ – S.H. Apr 10 '17 at 13:24
  • $\begingroup$ (1,1,1,1) was the set (L,R) the triplets are to be found inside. You can view it as: ([1,1,1],1) and (1,[1,1,1]) and count two triplets inside the set. $\endgroup$ – Nathan Apr 10 '17 at 13:28
  • $\begingroup$ Thanks,I got it now ! Can this logic be applied to the modified code too ? $\endgroup$ – S.H. Apr 10 '17 at 13:31
  • $\begingroup$ This code answers your original question. I haven't looked at your modifications. It's not pleasant to have to give a new answer because the question was changed after it was answered. $\endgroup$ – Nathan Apr 10 '17 at 13:39
  • 1
    $\begingroup$ @Paparazzi yes, I started that in my answer, when he originally asked the question he wasn't clear on it $\endgroup$ – Nathan Aug 12 '17 at 13:15
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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);
$\endgroup$
  • 1
    $\begingroup$ "sudo" code must be very powerful, indeed. ;-) $\endgroup$ – Ben I. Jun 10 '17 at 20:38
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
-1
$\begingroup$
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++ 
$\endgroup$
  • $\begingroup$ This doesn't work. On 1,1,1,2,1,1,1 it returns 2 rather than 1. $\endgroup$ – Yuval Filmus Aug 12 '17 at 13:39
  • $\begingroup$ @YuvalFilmus Then question is not clear $\endgroup$ – paparazzo Aug 12 '17 at 13:51
  • $\begingroup$ Why is this down voted? The stated question is any. "How do I treat any element that starts again" $\endgroup$ – paparazzo Aug 12 '17 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.