Remove Duplicates From Sorted Array
Easy About 10 min Free, no account needed
Deduplicate a sorted array without forgetting that it is sorted.
The brief
Given an integer array nums sorted in ascending order, return a new array
containing each distinct value once, in order.
The obvious approach ignores the sort: for each element it scans its growing result list to ask "have I added this already?", O(n2). The hidden test has 200,000 distinct values, the worst case for that scan, so the quadratic version is too slow. The input is already sorted, and you will need to use that fact to run in close to O(n).
Starter code
using System;
public class Solution
{
// TODO: return each distinct value once, in ascending order.
public int[] RemoveDuplicates(int[] nums)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Two pointers
- Walk a sorted or symmetric sequence from both ends, or fast and slow, instead of checking every pair.
Related katas
- Happy Number Easy Free Does repeatedly summing squared digits reach 1 - and how do you KNOW it will not?
- Merge Sorted Arrays Easy Free Merge two sorted arrays into one - without destroying what makes them special.
- Move Zeroes Easy Free Push all zeros to the end while keeping the other values in order.
- Two Sum II (Sorted Input) Easy Free Two Sum again - but the array is sorted, and that changes everything.