First Missing Positive
Hard About 30 min Free, no account needed
Find the smallest positive integer that does not appear in the array.
The brief
Given an integer array nums (any values, any order), return the smallest
positive integer (1, 2, 3, ...) that is not present.
The obvious approach tries 1, then 2, then 3, ... scanning the whole array for each
candidate, O(n2) when the answer is large. The hidden test contains the
values 1..200000, so the answer is 200001 and the scan-per-candidate
approach performs twenty billion comparisons. Note that for an array of length
n the answer is always in 1..n+1, so a linear-time solution is possible.
Starter code
using System;
public class Solution
{
// TODO: return the smallest positive integer absent from nums.
public int FirstMissingPositive(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
- Hash maps and sets
- Trade memory for constant-time lookups, membership tests and frequency counts.
Related katas
- Longest Well-Performing Interval Hard Free Longest stretch of days with more tiring days than easy ones.
- Minimum Window Substring (Length) Hard Free Length of the shortest window of text covering every required character.
- Contiguous Array Medium Free Longest subarray holding as many zeros as ones.
- Degree of an Array Medium Free Find the shortest contiguous slice whose most-frequent-element count matches the whole array.