Removing Duplicates from Sorted Array in Java without using additional space?

Question

The problem states:

Do not allocate extra space for another array, you must do this in place with constant memory.

Isn't it true that the size of an Java array is fixed when you allocate it? How can the requirement of not allocating extra space for another array in place with constant memory be satisfied?

Comments

It seems that the Judge using the similar scenario for Java as for C++: using a separate integer (the value you returned in this problem) as the length of the array.

Answer 1

The requirement is to return the new length, not return a new array. So no new array allocation is needed.

Update: Sorry, my fault, the above answer is not complete.

• You don't need to re-size the array. After removing the duplicates, just leave the rest slots as they are.

  E.g., [1, 1, 2] becomes [1, 2, 2], and return 2.

• If you want to prevent loitering, you can set the rest to 0. But this is not necessary to pass the online judge.

Comments

I don't follow your answer.

The example was:

"Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2]."

The way I read your answer, you're saying the function would return 2 and A would be [1,1,2]. Or is there something simple I'm missing?

---

I think what @tuliren meant is the function would not return a new array. It returns 2 and A would be modified to [1,2].

---

I'm still not following what happens to the extra space that was passed in for A. Like I asked previously, isn't that modifying the input? I didn't think A could be resized, so do the unused values simply get set with null?

In otherwords, for the example, it would it be that :

A[0] = 1 A[1] = 2 A[2] = null Thanks for the clarification

---

I think @tuliren's answer is spot on. You will modify the original input and you don't need to care about the values on or after A[2].

---

Perfect! That's what I was looking for. Thanks 1337c0d3r and tuliren!! :)

---

You're welcome! Could you select @tuliren's answer as the best answer if this solution does help you?

---

Just did. Thanks again!

Answer 2

in place is the key word here. This requirement basically means that you have to modify the array that was passed in.

Not allocating any extra memory (or using constant memory) is a requirement for your algorithm, the input doesn't count to the space requirement.

Answer 3

I know the best answer has been found. Just want to explain the problem requirement more clearly, for someone's reference in future.

This problem is described in a somewhat ambiguous way.

According to the test case, this problem asks us to move all distinct elements (suppose n totally) to the first n entries of the original array and return the value n.

I guess the Judge will then truncate and test the first n entries from original array A[].