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?

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.