Find duplicates in List where all the numbers in between is <= than the duplicates

Question

My function is supposed to go through a given List<Integer> and find integers of same value, but only count them if the integers between them is <= the the integers that are equal:

public static int findPairs(List<Integer> arr) {
        int total = 0;

        for(int i = 0; i < arr.size(); i++) {
            for(int j = i+1; j < arr.size(); j++) {
                total += (arr.get(i) == arr.get(j)) ? 1 : 0;
                j = (arr.get(j) > arr.get(i)) ? arr.size() : j;
            }
        }
        return total;
    }

The array size can be between \$1 \le N \le 3 *10^5\$.

The numbers in the array can be between \$1 \le N \le 10^6\$.

This works, but is there any way to achieve the same thing, only a better solution performance-wise?

Answer 1

Firstly, note that you should use .equals not == to compare two Integer values. Also, setting j to equal arr.size() is an odd way of doing a break.

However the main problem with your algorithm is that it has worst case performance O(n^2). If you run it on a descending List like [1000000, 999999, 999998, ..., 0], it is very slow because j is never set to be arr.size().

However, for random Lists (i.e. Lists where every item is chosen using random.nextInt(1000000) for example), it is in general very quick. This is because j generally doesn't have to get very far before we break out of the j loop, so it essentially has O(n) performance for random Lists.

The fact that the performance can vary so drastically depending on the nature of the List makes it very difficult to compare two algorithms. However, for many cases the following algorithm is quicker. It only traverses the List once, keeping track of the occurrences of the numbers found. Because it uses a TreeMap I think the worst case performance is O(n log n).

private static int countPairs(List<Integer> list) {
    int total = 0;
    NavigableMap<Integer, Integer> map = new TreeMap<>();
    for (int a : list) {
        map.headMap(a).clear();
        Integer m = map.get(a);
        if (m == null)
            map.put(a, 1);
        else {
            map.put(a, m + 1);
            total += m;
        }
    }
    return total;
}

Answer 2

Square brackets for arrays

It is convention to get items using square brackets, such as:

total += (arr[i] == arr[j]) ? 1 : 0;
j = (arr[j] > arr[i]) ? arr.size() : j;

Breaking out of this

Setting j to arr.size() ends the loop so I would write:

if  (arr.get(j) > arr.get(i)) {
    break;
}

instead of j = ...

Answer 3

If your numbers are random then the probability for any number to be larger than it's predecessor is about 50%. In that case your original solution is already pretty much as fast as possible as long as you replace the list with an array. However if the numbers are not random and you might have long sequences of numbers that are all smaller than their predecessors, it get's trickier.

In that case this can be done efficiently with a sorted ring buffer. You just go through the list of numbers once and each time you do a binary search on your buffer to see if the number is already in there. Then you remove all the numbers from the buffer that are smaller than your current one and add it at the front if it's not there already. That way the ring buffer will always store a sorted list of all those numbers for which you haven't come across a larger one yet i.e. all those numbers you might still find a partner for. The big advantage of a ring buffer here is that you can remove x elements from the start in constant time and are still able to do an efficient search in it.

example:

class RingBuffer {
  private final int[] buffer;
  private int start = 0, size = 0;
  RingBuffer(int maxSize) {
    buffer = new int[maxSize];
  }
  int get(int n) {
    return buffer[(start + n)%buffer.length];
  }
  int getFirst() {
    return buffer[start];
  }
  void addFirst(int n) {
    if(size >= buffer.length) throw new IndexOutOfBoundsException();
    start--;
    size++;
    if(start < 0) start = buffer.length - 1;
    buffer[start] = n;
  }
  void removeFirst(int n) {
    if(n > size) throw new IndexOutOfBoundsException();
    start = (start + n) % buffer.length;
    size -= n;
  }
  int binSearch(int n) {
    int low = 0,
        high = size;
    while(high > low) {
      int mid = (low + high)/2;
      int value = get(mid);
      if(value > n) high = mid;
      else if(value < n) low = mid + 1;
      else return mid;
    }
    return low;
  }
  @Override
  public String toString() {
    String s = "[";
    if(size > 0) s += get(0);
    for(int i = 1; i < size; i++) {
      s += ", " + get(i);
    }
    s += "]";
    return s;
  }
}

public class Test {
  static int findPairs(int[] arr) {
    int total = 0;
    RingBuffer rb = new RingBuffer(arr.length);

    for(int i = 0; i < arr.length; i++) {
      int value = arr[i];
      int idx = rb.binSearch(value);
      rb.removeFirst(idx);
      if(rb.getFirst() == value) total++;
      else {
        rb.addFirst(value);
      }
    }

    return total;
  }

  public static void main(String[] args) {
    int[] arr = {1, 2, 3, 4, 5, 4, 3, 2, 4, 5, 1, 2, 5};
    System.out.println(findPairs(arr));
  }
}

Of course you can make this even faster by removing the bounds checks and instead of using a RingBuffer class putting the code in the RingBuffer methods directly into the findPairs methods.

Answer 4

Can be done in linear time

I just wanted to demonstrate that this problem can be solved in O(N) time. I started with SpiderPig's idea of a RingBuffer. But actually, the buffer doesn't need to wrap around. It can start at the end and grow backwards, meaning it acts like a stack. Also, instead of binary searching the stack to find the insertion point, you can search it linearly.

Although it might seem like a linear search would be slower, it actually makes the worst case time O(N). Each item in the original list is inserted into the stack once. And each item will only need to be searched past once because once it is search past, it will be deleted. So the total of all the searches will only search past each item once.

The worst case for a binary search is if we always need to push to the head of the stack. That case takes O(N log N) time total.

The code

Here is the O(N) time solution. Here is a short explanation:

Buffer is the sorted stack of possible numbers to be paired. Start is where the stack starts. If it is at size, then the stack is empty.

Counts is an array of how many times we have seen each starting point in buffer. I needed this because in a list such as:

  1 1 1 1 1

there are multiple pairings every time we reach a matching endpoint. This example should have 10 possible pairings. If the question were reworded such that the numbers in between had to be < instead of <=, then I wouldn't need the counts array.

private static long countPairs(List<Integer> list) {
    int    size   = list.size();
    int [] buffer = new int[size];
    int [] counts = new int[size];
    int    start  = size;
    long   total  = 0;

    for (int num : list) {
        int i;
        boolean found = false;
        for (i = start; i < size; i++) {
            if (buffer[i] >= num) {
                if (buffer[i] == num) {
                    // Found a match.
                    total += counts[i]++;
                    found = true;
                    start = i;
                }
                break;
            }
        }
        if (!found) {
            // Did not find it, insert it before i.
            start = i-1;
            buffer[start] = num;
            counts[start] = 1;
        }
    }
    return total;
}