Longest Well-Performing Interval
Hard About 30 min Free, no account needed
Longest stretch of days with more tiring days than easy ones.
The brief
Given hours, the hours worked each day, a day is tiring when it has
more than 8 hours. Return the length of the longest interval of
consecutive days in which tiring days strictly outnumber non-tiring days.
The obvious approach tallies every interval from every start, O(n2), far too slow on the hidden 100,000-day test where the whole input qualifies. You will need a solution that runs in O(n).
Starter code
using System;
public class Solution
{
// TODO: return the length of the longest interval where days with more than 8 hours strictly outnumber the rest.
public int LongestWPI(int[] hours)
{
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
- Prefix sums
- Carry running totals or prefix state so any range question becomes a lookup.
- Hash maps and sets
- Trade memory for constant-time lookups, membership tests and frequency counts.
Do these first
Related katas
- Subarray Sum Equals K Medium Free Count contiguous subarrays whose elements sum to a target k.
- Count Bounded Range Sums Hard Free Count signed subarray totals inside an inclusive band without enumerating quadratic pairs.
- First Missing Positive Hard Free Find the smallest positive integer that does not appear in the array.
- Minimum Window Substring (Length) Hard Free Length of the shortest window of text covering every required character.