3
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ The method name, and return types are incompatible.... findPair(...) returns a single int... but, that int is a total, that is computed in a funny way. You need to make your code's description clearer, at the moment it is odd. \$\endgroup\$ – rolfl May 4 '15 at 18:50
  • \$\begingroup\$ Convert the list to an array first. How many numbers will the inner loop go through on average? And within what range are those numbers? \$\endgroup\$ – SpiderPig May 4 '15 at 18:50
  • \$\begingroup\$ @SpiderPig I updated the question. \$\endgroup\$ – Nilzone- May 4 '15 at 18:56
  • \$\begingroup\$ Sounds like a neat problem and I'd like to try it myself, can you provide a link to it? \$\endgroup\$ – Stefan Pochmann May 5 '15 at 0:51
  • \$\begingroup\$ @StefanPochmann hackerrank.com/challenges/jim-and-the-skyscrapers \$\endgroup\$ – Nilzone- May 5 '15 at 5:18
6
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Thank you for this! :) But I get the wrong answer on a larger test case where N = 300.000. Is there a logical error somewhere? \$\endgroup\$ – Nilzone- May 4 '15 at 21:29
  • \$\begingroup\$ @Nilzone- I'll look into it. \$\endgroup\$ – Paul Boddington May 4 '15 at 21:34
  • \$\begingroup\$ Never mind. On the larger test cases, long was needed instead of int \$\endgroup\$ – Nilzone- May 5 '15 at 15:37
4
\$\begingroup\$

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 = ...

\$\endgroup\$
  • \$\begingroup\$ considering a potentially big array size N. Would recursion be a better choice of nested loops? \$\endgroup\$ – Nilzone- May 4 '15 at 19:04
  • 1
    \$\begingroup\$ @Nilzone- in my opinion no, not in Java at least. Loops are more easily understood and faster than recursion 90-95% of the times. \$\endgroup\$ – Caridorc May 4 '15 at 19:06
  • \$\begingroup\$ Am I also better off changing total += (arr[i] == arr[j]) ? 1 : 0; to a normal if? \$\endgroup\$ – Nilzone- May 4 '15 at 19:15
  • \$\begingroup\$ @Nilzone- maybe it will be a bit more evident, but it will take 3 lines instead of one, it is subjective \$\endgroup\$ – Caridorc May 4 '15 at 19:25
  • \$\begingroup\$ I could easily write it like this: if(arr[i] == arr[j]) total++; I was just wondering compile wise if it's smarter to drop the if check whenever possible in loops. \$\endgroup\$ – Nilzone- May 4 '15 at 19:30
4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ The ringbuffer is a great idea. However, the binary search is unnecessary and causes this solution to be O(N log N) when it could be O(N) instead. If you use a linear search in the ringbuffer, the runtime will be guaranteed to be O(N). You might think the search would be slower, but remember that each item you search past will be deleted from the ringbuffer. Exactly N items will be ever be inserted into the ringbuffer, and each item will be searched past exactly once. So the total search time for all searches will be O(N). \$\endgroup\$ – JS1 May 5 '15 at 18:07
  • \$\begingroup\$ You are right, but I have to admit that I don't actually need a ringbuffer since I never add or remove from the end. I really only need a stack. \$\endgroup\$ – SpiderPig May 5 '15 at 20:15
  • \$\begingroup\$ Yes, I noticed that. Take a look at my answer that builds on yours. \$\endgroup\$ – JS1 May 5 '15 at 20:20
3
\$\begingroup\$

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;
}
\$\endgroup\$

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.