Contains Duplicate
Easy About 8 min Free, no account needed
Decide whether an array contains any repeated value.
The brief
Given an integer array nums, return true if any value appears at least
twice, and false if every element is distinct.
The obvious approach compares every pair, O(n²). The hidden test feeds in
400,000 distinct values, which makes the quadratic scan do the maximum amount
of work, so it's too slow. HasDuplicate needs an approach that scales better
than checking every pair.
Reaching for a built-in does not rescue it: asking Array.IndexOf (or
List.Contains) once per element is still O(n²), just with a faster inner
loop. The fix has to change the algorithm, not the spelling.
Starter code
using System;
public class Solution
{
// TODO: return true when any value appears more than once in nums.
public bool HasDuplicate(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.
Related guides
What it practices
- Hash maps and sets
- Trade memory for constant-time lookups, membership tests and frequency counts.
Related katas
- Count Distinct Letters Easy Free How many different letters appear? A 26-slot array already knows.
- Count Pairs With Difference K Easy Free Count the pairs of indices whose values differ by exactly k.
- Isomorphic Strings Easy Free Can one string be turned into the other by a consistent character substitution?
- Majority Element Easy Free Find the element that appears more than half the time.