Remove duplicates in-place from unsorted array
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## 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.
Quick Answer: 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.