Remove Repeated Values from a Sorted Array
Solve this Problem
Given an array
nums sorted in non-decreasing order, return a new array containing only its unique values, keeping their original relative order.
The array being sorted is the key hint here — it means every duplicate of a value sits right next to it, so you never need to search back through everything you've already collected.
Test Case 1:
Input:nums = [1, 1, 2, 3, 3, 3, 5]
Output:[1, 2, 3, 5]
Explanation:Every run of equal values collapses down to a single occurrence.
Test Case 2:
Input:nums = [4, 4, 4, 4]
Output:[4]
Explanation:One value repeated the whole way through leaves just itself.
Test Case 3:
Input:nums = [2, 5, 9]
Output:[2, 5, 9]
Explanation:No repeats at all, so nothing changes.
Constraints
- ◆
1 ≤ nums.length ≤ 10⁵ - ◆
-10⁹ ≤ nums[i] ≤ 10⁹ - ◆
nums is sorted in non-decreasing order
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public int[] removeDuplicates(int[] nums) { |
| 3 | List<Integer> result = new ArrayList<>(); |
| 4 | for (int num : nums) { |
| 5 | if (result.isEmpty() || result.get(result.size() - 1) != num) { |
| 6 | result.add(num); |
| 7 | } |
| 8 | } |
| 9 | int[] out = new int[result.size()]; |
| 10 | for (int i = 0; i < out.length; i++) out[i] = result.get(i); |
| 11 | return out; |
| 12 | } |
| 13 | } |
| 14 |
Array
1
1
2
2
3
0
1
2
3
4
↑i
Array
_
_
_
_
_
0
1
2
3
4
Variables
result
[]INITIALIZE
Start scanning from the first element with an empty result list.
Step 1 / 10
Approach & Solutions
Brute Force — Build a Seen List
BruteWalk the array and, for each value, scan the result built so far to check whether it's already there. Only append it if it isn't. This works even on an unsorted array, but the repeated scanning of the growing result list is unnecessary busywork here.
Time
O(n²)Space
O(n)Java
1class Solution {
2 public int[] removeDuplicates(int[] nums) {
3 List<Integer> result = new ArrayList<>();
4 for (int num : nums) {
5 boolean alreadyThere = false;
6 for (int existing : result) {
7 if (existing == num) { alreadyThere = true; break; }
8 }
9 if (!alreadyThere) result.add(num);
10 }
11 int[] out = new int[result.size()];
12 for (int i = 0; i < out.length; i++) out[i] = result.get(i);
13 return out;
14 }
15}Optimal — Exploit the Sorted Order
OptimalBecause the array is sorted, every group of equal values sits right next to each other. So you only ever need to compare each element to the last one you kept — if it's different, keep it too; if it matches, it's a duplicate and can be skipped. One pass, no lookups.
Time
O(n)Space
O(n)Java
1class Solution {
2 public int[] removeDuplicates(int[] nums) {
3 List<Integer> result = new ArrayList<>();
4 for (int num : nums) {
5 if (result.isEmpty() || result.get(result.size() - 1) != num) {
6 result.add(num);
7 }
8 }
9 int[] out = new int[result.size()];
10 for (int i = 0; i < out.length; i++) out[i] = result.get(i);
11 return out;
12 }
13}