DSA-018 · Read/write compaction of sorted runs
Remove Duplicates from Sorted Array
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 6005 deterministic checks. Learner drafts are not executed.
Understand the problem
Compact a nondecreasing array so its distinct values occupy the beginning, and return the length of that valid prefix.
- nums is non-null and nondecreasing, with 0–100,000 signed int entries. Sortedness is a precondition; equal values therefore form contiguous runs.
- Return k, the number of distinct input values. Mutate nums[0..k) into those values in increasing order, preserving the array object. Empty input returns zero.
- The tail nums[k..n) is unspecified and must not be judged, serialized as the logical answer, or assumed to contain zeros. The logical result is k together with a copy/view of the valid prefix.
Examples
Input:
[0,0,1,1,2]
Output:k=3, prefix=[0,1,2]Only the first three positions are meaningful after compaction.
Input:
[7,7,7]
Output:k=1, prefix=[7]One representative survives from the run.
Before you start
- Array indexing and inclusive pointer bounds
- Loop invariants and Java value versus reference semantics
Recognize the structure
In sorted data the next distinct value differs from the last emitted value. A read pointer discovers runs; a write pointer names the next valid prefix slot. Output can safely reuse consumed storage.
Try before revealing
Hint 1
What is the smallest state needed to recognize a new sorted run?
Hint 2
Let write be the number of unique values emitted so far.
Hint 3
Append only when the current value differs from nums[write-1].
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Read from a protected copy
Clone the original, then copy a value when it starts a new run. For [1,1,2], copy[0] writes 1, copy[1] is skipped, and copy[2] writes 2, yielding k=2 and prefix [1,2]. The tail is irrelevant. This is O(n) time and O(n) extra space; separating input and output makes overwrite safety obvious.
Improve the baseline
Define write as prefix length
Initially write=0. The emitted prefix is empty and no value has been processed.
Recognize a new run
If write==0 or nums[read]!=nums[write-1], emit nums[read] at write and increment write. Otherwise the run is already represented.
Reuse earlier positions
write never exceeds read before an emission. A write therefore changes only an already consumed position or the current one; future unread values stay intact.
Why it is correct
Prefix invariant
Before each read, nums[0..write) contains exactly the distinct values from the original processed prefix, in sorted order; positions read and later still contain original unread values.
Preservation
A value equal to the last emitted value belongs to the same sorted run and adds nothing. A different value is the next distinct value, so appending it gives the extended distinct prefix. write≤read ensures no unread source is overwritten.
Return meaning
After every input position has been read, write equals the total number of distinct values. The invariant proves the prefix; no invariant or output requirement is imposed on the leftover tail.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
public final class Solution {
public static int removeDuplicates(int[] nums) {
int write = 0;
for (int read = 0; read < nums.length; read++) {
if (write == 0 || nums[read] != nums[write - 1]) nums[write++] = nums[read];
}
return write;
}
public static int baseline(int[] nums) {
int[] copy = nums.clone();
int write = 0;
for (int read = 0; read < copy.length; read++)
if (read == 0 || copy[read] != copy[read - 1]) nums[write++] = copy[read];
return write;
}
}
Read the meaningful blocks
Short-circuit the first value
write==0 prevents reading nums[-1] and handles empty input naturally.
Compare with the last output
nums[write-1] remains the last unique value even after earlier compaction writes.
Return write
The next write position is already the valid length; returning write+1 is an off-by-one error.
Complexity
O(n) time: each source occurrence is read once. O(1) auxiliary space and an in-place valid prefix of length k.
The copy baseline is O(n) time and O(n) storage. If a caller needs an independently sized array, copying the k-value prefix requires O(k) output space and should be counted separately.
Exact-state walkthroughs
Reveal normal and boundary traces
Compact three sorted runs
Input: [0,0,1,1,2] · Result: {"k":3,"prefix":[0,1,2]}
Step 1 of 7: Begin with an empty meaningful prefix.
write is the number of retained values from the processed original prefix.
Empty at this step.
- 0: 0
- 1: 0
- 2: 1
- 3: 1
- 4: 2
| Variable | Value |
|---|---|
| values | [0,0,1,1,2] |
| write | 0 |
| prefix | [] |
See the affected Java block
1 public final class Solution { 2 public static int removeDuplicates(int[] nums) { 3 int write = 0; 4 for (int read = 0; read < nums.length; read++) { 5 if (write == 0 || nums[read] != nums[write - 1]) nums[write++] = nums[read]; 6 } 7 return write; 8 } 9 public static int baseline(int[] nums) { 10 int[] copy = nums.clone(); 11 int write = 0; 12 for (int read = 0; read < copy.length; read++) 13 if (read == 0 || copy[read] != copy[read - 1]) nums[write++] = copy[read]; 14 return write; 15 } 16 } 17
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin with an empty meaningful prefix.
write is the number of retained values from the processed original prefix.
- values
[0,0,1,1,2]- write
0- prefix
[]
- Append this retained value.
The meaningful prefix equals the retained original subsequence; writes cannot reach beyond the current read index.
- values
[0,0,1,1,2]- read
0- value
0- kept
true- write
1- prefix
[0]
- Skip this occurrence.
The meaningful prefix equals the retained original subsequence; writes cannot reach beyond the current read index.
- values
[0,0,1,1,2]- read
1- value
0- kept
false- write
1- prefix
[0]
- Append this retained value.
The meaningful prefix equals the retained original subsequence; writes cannot reach beyond the current read index.
- values
[0,1,1,1,2]- read
2- value
1- kept
true- write
2- prefix
[0,1]
- Skip this occurrence.
The meaningful prefix equals the retained original subsequence; writes cannot reach beyond the current read index.
- values
[0,1,1,1,2]- read
3- value
1- kept
false- write
2- prefix
[0,1]
- Append this retained value.
The meaningful prefix equals the retained original subsequence; writes cannot reach beyond the current read index.
- values
[0,1,2,1,2]- read
4- value
2- kept
true- write
3- prefix
[0,1,2]
- Return k; display only the valid prefix.
The unspecified tail is deliberately excluded from the logical result.
- result
{"k":3,"prefix":[0,1,2]}
Empty prefix
Input: [] · Result: {"k":0,"prefix":[]}
Step 1 of 2: Begin with an empty meaningful prefix.
write is the number of retained values from the processed original prefix.
Empty at this step.
Empty at this step.
| Variable | Value |
|---|---|
| values | [] |
| write | 0 |
| prefix | [] |
See the affected Java block
1 public final class Solution { 2 public static int removeDuplicates(int[] nums) { 3 int write = 0; 4 for (int read = 0; read < nums.length; read++) { 5 if (write == 0 || nums[read] != nums[write - 1]) nums[write++] = nums[read]; 6 } 7 return write; 8 } 9 public static int baseline(int[] nums) { 10 int[] copy = nums.clone(); 11 int write = 0; 12 for (int read = 0; read < copy.length; read++) 13 if (read == 0 || copy[read] != copy[read - 1]) nums[write++] = copy[read]; 14 return write; 15 } 16 } 17
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin with an empty meaningful prefix.
write is the number of retained values from the processed original prefix.
- values
[]- write
0- prefix
[]
- Return k; display only the valid prefix.
The unspecified tail is deliberately excluded from the logical result.
- result
{"k":0,"prefix":[]}
Test the contract
Input:
[]
Output:k=0, prefix=[]No initialization read.
Input:
[5]
Output:k=1, prefix=[5]One run.
Input:
[-2,-2,0,3,3]
Output:k=3, prefix=[-2,0,3]Negative and repeated values.
Input:
[1,2,3]
Output:k=3, prefix=[1,2,3]Every value is new.
Common mistakes and counterexamples
Validate the entire mutated array
Counterexample: [1,1,2] may end as [1,2,2], which is correct for k=2.
Judge only k and nums[0..k).
Apply to unsorted input
Counterexample: [1,2,1] contains a repeated value in separate runs.
Require sortedness or use sorting/a set under a different contract.
Read the previous output before initialization
Counterexample: On the first element write=0.
Short-circuit with write==0.
Follow-ups
Allow at most two copies.
Emit when write<2 or nums[read]!=nums[write-2]. Sortedness makes comparison two output positions back sufficient; derive the invariant for general limit m.
Remove duplicates while preserving unsorted order.
Track seen values in a hash set and compact first occurrences. This keeps encounter order but uses O(k) extra storage rather than O(1).
Expose a safe result to a caller.
Return k and let the caller use only the prefix, or allocate Arrays.copyOf(nums,k). Do not present the unspecified tail as another sequence of meaningful answers.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 90/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.