-1

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory.

I came up with below solution but this doesn't return correct output - I mean my input array still has duplicate values in it? Is there anything wrong I did?

public class Solution {
    public static void main(String[] args) {
        int[] input = new int[] { 1, 1, 3, 7, 7, 8, 9, 9, 9, 10 };
        int length = input.length;
        if (length == 0 || length == 1) {
            System.out.println(length);
            System.exit(0);
        }
        int i = 1;
        for (int j = 1; j < length; j++) {
            if (input[j] != input[j - 1]) {
                input[i] = input[j];
                i++;
            }
        }
        if (i < length) {
            input[i] = '\0';            
        }
        System.out.println(i);
        System.out.println(Arrays.toString(input));
    }
}

NOTE: This is not homework, just preparing for an interview.

user1950349
  • 4,738
  • 19
  • 67
  • 119
  • `println(input)` this is not how we print arrays. Take a look at http://stackoverflow.com/questions/8410294/why-does-printlnarray-have-strange-output-ljava-lang-string3e25a5 and http://stackoverflow.com/questions/29140402/how-do-i-print-my-java-object-without-getting-sometype2f92e0f4 – Pshemo May 17 '15 at 19:00
  • Also helper methods like `Arrays.toString()` will print all elements in arrays, based on array length so elements after `\0` will also be printed (Java is not C). To print only elements before `\0` you need to do it manually with loop which will stop when finding `\0`. – Pshemo May 17 '15 at 19:02
  • This looks like homework, and there may be a better way of doing this which is why I'm not providing a full answer for the time being, but personally I'd loop through the array twice. The first loop would contain another loop as well and would be responsible for replacing any duplicates with a null value (of course leaving the one value), and then you would need to go through the array again to shift all the values so that all the null indexes are at the end. – Andy May 17 '15 at 19:02
  • @Andy, there is no such thing as a null int. – RealSkeptic May 17 '15 at 19:05
  • @RealSkeptic It's been a long while since I programmed in Java so apologies, I need to refresh myself by the looks of things. My main aim was to help with the actual algorithm however and get across the principle. – Andy May 17 '15 at 19:08

2 Answers2

1

Java is not C. You don't mark the end of an array with a null pointer or zero character. Java arrays have a constant length and it never changes.

Your algorithm actually works well, but you probably want to put zero in all the array elements beyond i, to make it clear that those elements are unused. Use an actual 0, not '\0' which is a char value, which only happens to be assignment-compatible with int, but is not actually proper here.

Note also that the assignment expects you to return the length. This probably means that you have to write this as a method, which accepts the array as a parameter and returns the new length.

RealSkeptic
  • 33,993
  • 7
  • 53
  • 79
0

An array's length in Java cannot be altered after initialization, so you're forced to make a copy with the new size. Actually, the length parameter of a Java array is declared as final, so it cannot be changed once it's set.

Rao Ehsan
  • 778
  • 8
  • 15