6
\$\begingroup\$
public class ArrayUtil {

    /**
     * Field INPUT_LESS_THAN_TWO. (value is 2)
     */
    private static final int INPUT_LESS_THAN_TWO = 2;

    /**
     * Method removeDuplicateElement. Given a sorted array of integers, this
     * method removes the duplicate elements. Input array is sorted array and
     * can have only negative values, only positive value or a mix of both.
     * 
     * @param inputArray
     *            int[]
     * 
     * @return int[]
     * @throws IllegalArgumentException
     */
    public int[] removeDuplicateElement(final int[] inputArray)
            throws IllegalArgumentException {

        int j = 0; // Marks the begining of the array
        int i = 1; // Points toward the second element in the array

        if (null == inputArray || 0 == inputArray.length) {
            throw new IllegalArgumentException(
                    "Input Array is either null or of zero length");
        } // end of null and 0 length check

        // Return if the input array has only one item
        if (inputArray.length < INPUT_LESS_THAN_TWO) {
            return inputArray;
        } // end of check for length less than 2
        while (i < inputArray.length) {
            if (inputArray[i] == inputArray[j]) {
                i++;
            } else {
                inputArray[++j] = inputArray[i++];
            }
        } // end of while loop

        // copy and return the array
        final int[] outputArray = new int[j + 1];
        for (int k = 0; k < outputArray.length; k++) {
            outputArray[k] = inputArray[k];
        }

        return outputArray;
    }

}

I believe that the time complexity of this algorithm is \$O(N)\$.

\$\endgroup\$
  • \$\begingroup\$ A quick suggestion, I am leaving as a comment instead of an answer because it's not very in depth, but I would suggest no including comments at the end of code blocks like end of while loop, especially on such a small block that you can easily tell where it begins and ends. It just adds clutter and makes readability worse. Conversely, things like copy and return the array are more okay in my opinion because it says something that may not be immediately obvious. So long as your indentation is correct, you shouldn't need to worry about adding comments saying that the } is closing. \$\endgroup\$ – Captain Man May 5 '15 at 17:27
5
\$\begingroup\$

Style

Comments

I stated this in a comment (pun unintended but a happy side effect) that I think comments like this are unneeded and make the code harder to read.

if (null == inputArray || 0 == inputArray.length) {
    throw new IllegalArgumentException(
            "Input Array is either null or of zero length");
} // end of null and 0 length check

// Return if the input array has only one item
if (inputArray.length < INPUT_LESS_THAN_TWO) {
    return inputArray;
} // end of check for length less than 2

Compare that to this

if (null == inputArray || 0 == inputArray.length) {
    throw new IllegalArgumentException(
            "Input Array is either null or of zero length");
}

// Return if the input array has only one item
if (inputArray.length < INPUT_LESS_THAN_TWO) {
    return inputArray;
}

Because everything is properly indented I just know by looking that the if-block if over.

Lastly, the comments for i and j are poor. You state what they are originally pointing to but not what they're used for throughout the method which would be more useful. Something like this,

int j = 0; // Marks the end of the sorted subarray to return
int i = 0; // Points to the element being checked

(It may be better to switch the names of i and j because i is usually used for the outer most "loop" meaning it moves less.)

Doc Comments

Adding javadoc comments is good practice and it's good to see you do this. The only issue I see with it is it starts by saying it's a method and it gives the name. This is redundant. The name is beneath the doc comment and if you view the javadoc as html it is still clear what the name is. Just remove "Method removeDuplicateElement."

Throws IllegalArgumentException

See this if you do not know the difference between checked and unchecked exceptions. IllegalArgumentException extends RuntimeException. Because of this it is an unchecked exception.

The throws clause of a method is to alert the compiler that it can possibly throw the exception. Because this is an unchecked exception though the compiler doesn't care if the caller handles/throws it or not, and because of that it is redundant. I suggest either removing this or making your own exception that doesn't extend RuntimeException if you really want to make the called handle/throw the error. (I think this is a bad idea.)

Note: I did not say there was an issue with throw new IllegalArgumentException( ... ); when the array is invalid for your method, this is fine. However, one could argue that because the point of the method is to remove duplicate elements that a null/empty array has the elements removes and you could simply return the null/empty array instead of throwing the error. In fact, I think I like that better. It's best to throw little and handle quietly when it comes to exceptions.

Utility Class

I seem to be linking back to my own answer a lot. For the same reasons as here I suggest you make this into a "utility class". Because everything about this class is always the same no matter how you make an instance of it, there's no point in having to make an instance of it. Quick summary,

  • make it a final class,
  • add a private constructor, and
  • make all methods static.

private static final fields

There is nothing wrong with these but in this case I don't think making INPUT_LESS_THAN_TWO into one makes sense. You'd return the array if it only had one element no matter what, there's not something that's likely to change down the line that would make this value different.

inputArray.length < 2 is simply more readable in this case, or better yet inputArray.length == 1 because earlier you already checked if it was 0 and it should never be below 0. (If it's ever below 0 the JVM is messing up and there's bigger issues! It's safe to assume it won't.)


Code choice

System.arraycopy

Edit: 200_success's suggestion of Arrays.copyOf is better than my suggestion here. System.arraycopy is better when you already have an array you want to put things in, Arrays.copyOf makes a new array for you. Better to do away with making outputArray altogether and simply doing return Arrays.copyOf(inputArray, j + 1);. System.arraycopy is still a good tool to know of so I will leave this section, bold italic text is text I added in this edit.

This is preferred to using a for-loop to make an array from an array specifically when you already have an array that you want to put the copied elements in.

for (int k = 0; k < outputArray.length; k++) {
    outputArray[k] = inputArray[k];
}

That becomes simply System.arraycopy(inputArray, 0, outputArray, 0, outputArray.length); (You may need to remove the final modifier for the output array, I am not entirely sure.)

Increment operators

This is simply my taste, no issue with your code, but I dislike inputArray[++j] = inputArray[i++]; because it's a little confusing. I prefer

j++;
inputArray[j] = inputArray[i];
i++;
\$\endgroup\$
5
\$\begingroup\$

Interface, JavaDoc, and behaviour

This function should be static, since it is a utility function that does not rely on any object state. Then, you can call it as ArrayUtil.removeDuplicateElement() instead of new ArrayUtil().removeDuplicateElement().

I suggest renaming the function to removeConsecutiveDuplicates to emphasize the fact that it only examines duplication in immediately neighbouring elements. Then you can discard the long-winded story about how the input needs to be a sorted array of nonzero values, because none of that is relevant.

The parameter can just be named input; inputArray is just a verbose kind of Hungarian notation.

I am not convinced that a zero-length input should be considered illegal input. Deduplicating a zero-length array should result a zero-length array, right? Checking for a null input is probably unnecessary as well, since letting it naturally crash with a NullPointerException would be the conventional behaviour.

This function trashes the contents of the input array, and does so without any explicit warning in the JavaDoc. I consider that to be unacceptable behaviour. Furthermore, your length-one special case is invalid — sometimes returning the same inputArray, sometimes returning an independent copy will cause grief for the caller. In my opinion, the only desirable design is to never trash the input array, and always return a copy (unless the input is zero-length, in which case it's OK to return inputArray since a zero-length array is immutable).

If you aren't going to say anything about the parameter, return value, or the exception in the JavaDoc, then just omit them.

Implementation

The comments are more noisy than helpful. For example, // Marks the beginning of the array is uninformative; // Output index would have been much more helpful. The end-of-block comments also add unnecessary clutter.

As mentioned above, inputArray and outputArray should be shortened to just input and output. Instead of i and j, I suggest using i and o as the indexes, since they serve as mnemonics for input and output.

The while loop would be better written as a for loop, especially since it just increments i on each iteration.

To copy an array, just call Arrays.copyOf().

import java.util.Arrays;

public class ArrayUtil {

    /**
     * Produces a copy of the input array where consecutive duplicates elements
     * are replaced by just one element.
     */
    public static int[] removeConsecutiveDuplicates(int[] input) {
        if (0 == input.length) {
            return input;
        }

        int[] output = new int[input.length];
        int o = 0;      // Output index
        output[o++] = input[0];

        for (int i = 1; i < input.length; i++) {
            if (output[o - 1] != input[i]) {
                output[o++] = input[i];
            }
        }

        return (output.length == o) ? output : Arrays.copyOf(output, o);
    }

}
\$\endgroup\$
  • \$\begingroup\$ int[] output = new int[input.length]; will give you an output array with some zeros.Since the length of the output array and input array will differ.Another thing, I dont want to use anything from java.util package.. \$\endgroup\$ – Guest May 7 '15 at 6:14
  • \$\begingroup\$ @Guest That's why there is an Arrays.copyOf(). \$\endgroup\$ – 200_success May 7 '15 at 6:15

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.