current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 4 down vote favorite

Array of size \$(n-m)\$ with numbers from \$1..n\$ with \$m\$ of them missing. Find all of the missing numbers. The array is sorted.

Example: If arr = [1,2,4,5,6,8], result should be 3 & 7.

Here is my code which I would like to get reviewed:

import java.util.*;

class FindMissingNumsArray {

    private List<Integer> missing = new ArrayList();

    private void findMissingNums(int[] array) {
        if(array == null)
            return;
        int length = array.length - 1;
        if(length <= 1)
            return;

        getMissings(array, 0, length);
    }

    private void getMissings(int[] array, int lIndex, int hIndex) {
        if(hIndex - lIndex == 2) {
            fillMissings(array, lIndex, lIndex, hIndex);
            return;
        }
        if(lIndex == hIndex)
            return;

        int i = lIndex;
        int j = hIndex;
        int mid = lIndex + (hIndex - lIndex) / 2;
        getMissings(array, i, mid);
        getMissings(array, mid + 1, j);
        fillMissings(array, i, mid, j);
    }

    private void fillMissings(int[] array, int lIndex, int mid, int hIndex){
        int i = lIndex;
        int j = mid;
        int k = hIndex;
        int diff;
        while(i < mid) {
            diff = array[i + 1] - array[i];
            for(int c = 1; diff > 1; diff--) {
                if(!missing.contains(array[i] + c))
                    missing.add(array[i] + c);
                c++;
            }
            i++;
        }
        while(j < k) {
            diff = array[j + 1] - array[j];
            for(int a = 1; diff > 1; diff--) {
                if(!missing.contains(array[j] + a))
                    missing.add(array[j] + a);
                a++;
            }
            j++;
        }
    }

    private void printMissingList() {
        for(int i: missing)
            System.out.print(i + " ");
    }

    public static void main(String[] args) {
        int[] array = {1, 4, 5, 6, 9, 10, 12, 15, 19};
        int[] array1 = {0, 5, 6, 9, 10};
        FindMissingNumsArray findMissings = new FindMissingNumsArray();
        findMissings.findMissingNums(array);

        System.out.print("Missing numbers in array are: ");
        findMissings.printMissingList();

        findMissings.missing = new ArrayList();
        findMissings.findMissingNums(array1);


        System.out.print("Missing numbers in array1 are: ");
        findMissings.printMissingList();
    }
}

I know there are ways to implement this better in terms of logic, run time, data structures, etc. It will be nice to know what I can do to improve the code.

share|improve this question
up vote 6 down vote accepted

Sometimes (actually, normally), simpler is better.

I'm going to present a different way of doing this that's really simple, if you understand the tricks, then I'm going to explain what makes it better. One of the reasons I am doing it this way is because your code is hard to follow.... simply because there's so much. I suspect that when you see a different way of doing things a penny will "drop".

Here's the alternative:

private static final int[] findMissing(int[] data) {
    if (data == null || data.length <= 1) {
        // nothing missing.
        return new int[0];
    }
    int first = data[0];
    int last = data[data.length - 1];
    int[] missing = new int[last - first - data.length + 1];
    int missingCursor = 0;
    int expect = first;
    for (int value : data) {
        while (expect < value) {
            missing[missingCursor] = expect;
            missingCursor++;
            expect++;
        }
        expect++;
    }
    return missing;
}

Is that it? Yes, and it is probably still too much. But, let's consider the problem...

  • for too-small inputs, we know that there's nothing missing.
  • for larger inputs, we know exactly how much is missing - the difference between the first and last data values, less the number of values we actually have, and, add 1 because the last-minus-first is actually 1 too small.
  • then, all we have to do is 'expect' certain values, and fill in the gaps until we get the values we expect.

So, that is what the code does, but, note the following:

  • there is no need for object-oriented programming - there is no object here to represent. A single static method works fine.
  • there is no need for an adjustable-size ArrayList<Integer>() because we know how much is missing. Also, that's converting int values to Integer members in a List, which is more work than needed.
  • the method assumes the inputs are valid - no error-handling or validation

Now, that's the way I would write that method, and why I think it is an improvement.

Having said that, I want to point out some other issues in the code:

  • When creating a collection like an ArrayList, you need to use the diamond operator <> on the right-hand side. The code:

    private List<Integer> missing = new ArrayList();

    should be:

    private List<Integer> missing = new ArrayList<>();

    On the other hand, I really like that you have made the left-side List, this shows an understanding of the Collections API

  • When I run your code, the order of the missing values in the first array is suspect. I get: 2 3 7 8 11 16 17 18 13 14 (yes, the 13 and 14 are at the end for some reason). There's a bug in there somewhere I can't find.

  • Your code should print a new line after each output. Currently it is all on one line. System.out.println() to do that.

See this running in Ideone

share|improve this answer
    
Thanks a lot for the review and a better alternate solution. It took me some time to understand but I think I got it. How did you come up with 'last - first - data.length + 1'? Also, I think your solution is O(n) or more. Is that correct? I was trying to do it in O(lg n) and hence tried using divide & conquer. Don't know if its logarithmic. Special thanks for pointing out the possible improvements. I know it will only help me code better :) – strider14 Jun 11 '15 at 21:33
1  
The last-first+1 is the fencepost problem. The solution is \$O(n)\$ but that's required because you have to insert all missing values somewhere, and visit all not-missing ones too. The code above visits each just once. – rolfl Jun 11 '15 at 21:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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