Remove duplicates in-place from unsorted array

Q: Remove duplicates in-place from unsorted array

This question evaluates understanding of in-place array manipulation, duplicate removal, and algorithmic analysis under strict extra-space constraints. It is commonly asked in Coding & Algorithms interviews to assess reasoning about time-space trade-offs and algorithmic complexity, emphasizing practical application and implementation-level skills rather than purely conceptual knowledge.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

Problem

You are given an array nums of unsorted integers.

Write a method that removes duplicates in-place (i.e., without using any additional data structure such as a hash set/map/boolean array). The method should return the number of unique elements k and modify nums so that the first k positions contain the unique values.

Requirements

Extra space: O(1) (ignore call stack).
The input array is unsorted .
You may reorder the array elements unless otherwise stated.

Follow-up

Is an O(n) time solution possible under these constraints? If yes, state the needed assumptions; if not, explain why.

Examples

Input: [3, 1, 3, 2, 1] → Output k = 3 , first k elements are some permutation of {1, 2, 3} .
Input: [] → Output k = 0 .

Constraints

0 ≤ n ≤ 10^5
Integers fit in 32-bit signed range.