Find the Duplicate Number
Medium About 25 min Free, no account needed
Find the one repeated value in an array of n+1 numbers from 1..n, without allocating a set to do it.
The brief
Given an array nums of n + 1 integers where each value is in the range
1..n, exactly one value is repeated (it may appear more than twice).
Return that repeated value.
- Do not modify the input array.
The obvious approach compares every pair of elements, O(n²). The hidden test uses 200,001 numbers whose duplicate sits far from the start, so that is too slow.
The obvious fix, remembering every value in a HashSet<int>, is fast but
allocates megabytes of buckets and entries. The hidden test
also measures the bytes your code allocates and fails anything over a strict
16 KB budget, so a set, a bool[] of seen flags, or a sorted copy all blow
it. The values being confined to 1..n is the lever: it lets you find the
repeat in O(n) time with a fixed handful of variables, and the input left
untouched.
Starter code
using System;
public class Solution
{
// TODO: return the value that appears more than once in nums.
public int FindDuplicate(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.
Do these first
Related katas
- Boats to Save People Medium Free Pair people into two-person boats under a weight limit, using as few boats as possible.
- Container With Most Water Medium Free Pick two lines that, with the x-axis, hold the most water.
- Longest Palindromic Substring (Length) Medium Free How long is the longest palindrome hiding in the string?
- Sort Colors Medium Free Sort an array of 0s, 1s and 2s in a single pass.