Longest Well-Performing Interval

Med

#1062Time: O(n), where n is the number of days. We iterate through the array once, and HashMap operations (put, get) take average O(1) time.Space: O(n) in the worst case, as the HashMap could potentially store a distinct prefix sum for each element. The range of possible sums is from `-n` to `n`.1 company

Patterns

Prefix Sum

Data structures

Array Hash Table Stack Monotonic Stack

Companies

Infosys

Prompt

We are given hours, a list of the number of hours worked per day for a given employee.

A day is considered to be a tiring day if and only if the number of hours worked is (strictly) greater than 8.

A well-performing interval is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days.

Return the length of the longest well-performing interval.

Example 1:

Input: hours = [9,9,6,0,6,6,9]
Output: 3
Explanation: The longest well-performing interval is [9,9,6].

Example 2:

Input: hours = [6,6,6]
Output: 0

Constraints:

1 <= hours.length <= 10⁴
0 <= hours[i] <= 16

Approaches

2 approaches with complexity analysis and trade-offs.

A more efficient solution uses the concept of prefix sums combined with a HashMap. As before, we convert tiring days to +1 and non-tiring days to -1. We then compute the prefix sum as we iterate through this new score array.

The problem is to find indices i and j (i <= j) that maximize j - i + 1, such that the sum of scores from i to j is positive. This sum can be expressed as prefixSum[j] - prefixSum[i-1] > 0, or prefixSum[j] > prefixSum[i-1].

We can iterate through the array with index j, calculating the current_sum (which is prefixSum[j]). For each j, we need to find the earliest index i-1 where the prefix sum was smaller than current_sum. A HashMap is used to store the first index at which each prefix sum value appeared. This allows us to find the required i-1 efficiently.

Algorithm

Transform the problem: represent tiring days as +1 and non-tiring days as -1. The goal is to find the longest subarray with a sum > 0.
This problem can be solved in a single pass using a HashMap and the concept of prefix sums.
Initialize sum = 0, maxLength = 0, and a HashMap map to store the first-seen index of each prefix sum. Add a base case map.put(0, -1) to handle intervals starting from index 0.
Iterate through the hours array from i = 0 to n-1: a. Update the running sum: sum += (hours[i] > 8) ? 1 : -1. b. If sum is not already in the map, store its first occurrence: map.put(sum, i). c. Check if the current prefix sum sum is positive. If sum > 0, it means the interval from the beginning [0, i] is well-performing. Its length is i + 1. Update maxLength = max(maxLength, i + 1). d. If sum <= 0, we look for a previous prefix sum prev_sum such that sum - prev_sum > 0, which simplifies to prev_sum < sum. To get the longest such interval ending at i, we need the earliest (smallest index) prev_sum. The best candidate for this is sum - 1, as it represents the smallest possible positive difference (1). We check if map.containsKey(sum - 1). If it exists, it means we found an interval [map.get(sum - 1) + 1, i] with a sum of 1. We update maxLength = max(maxLength, i - map.get(sum - 1)).
Return maxLength.

Walkthrough

We iterate through the array once, maintaining a running sum. We use a HashMap to keep track of the first time we encounter each sum value. The key is the sum, and the value is the index.

We initialize the map with {0: -1} to correctly handle cases where a well-performing interval starts at index 0.

For each day i, we update our sum.

If sum > 0, the entire interval from the start [0, i] is well-performing. This has length i+1, which is the longest possible interval ending at i. We update our max length accordingly.
If sum <= 0, a well-performing interval ending at i must start at some k > 0. We are looking for a previous prefix sum, prev_sum, that is less than the current sum. To maximize the interval length i - k, we need the smallest k. The condition sum - prev_sum > 0 is equivalent to prev_sum <= sum - 1. The key insight is that we only need to check for the existence of sum - 1 in our map. If map.containsKey(sum - 1), we have found an interval with a sum of at least 1, and map.get(sum - 1) gives us the end index of the prefix that we subtract. The length of this interval is i - map.get(sum - 1). We update our max length with this value if it's larger.

We only add a sum to the map if it's not already there. This ensures we always have the earliest index for any given sum, which is crucial for finding the longest interval.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int longestWPI(int[] hours) {6        int maxLength = 0;7        int sum = 0;8        // Map to store the first occurrence of a prefix sum9        Map<Integer, Integer> map = new HashMap<>();10        // Base case for intervals starting at index 011        map.put(0, -1);12 13        for (int i = 0; i < hours.length; i++) {14            sum += (hours[i] > 8) ? 1 : -1;15 16            // If the current sum is positive, the interval from the beginning is well-performing.17            // This is the longest possible interval ending at i.18            if (sum > 0) {19                maxLength = i + 1;20            } else {21                // If sum <= 0, we look for a previous prefix sum `sum - 1`.22                // This guarantees an interval sum of `sum - (sum - 1) = 1 > 0`.23                // We check for `sum - 1` because it gives the longest possible interval24                // for a subarray ending at `i` with a positive sum.25                if (map.containsKey(sum - 1)) {26                    maxLength = Math.max(maxLength, i - map.get(sum - 1));27                }28            }29            30            // Store the first time we see a particular sum.31            // If the sum is already in the map, we don't update it because we want the earliest index.32            map.putIfAbsent(sum, i);33        }34 35        return maxLength;36    }37}

Complexity

Time

O(n), where n is the number of days. We iterate through the array once, and HashMap operations (put, get) take average O(1) time.

Space

O(n) in the worst case, as the HashMap could potentially store a distinct prefix sum for each element. The range of possible sums is from `-n` to `n`.

Trade-offs

Pros

Highly efficient with linear time complexity.
Solves the problem in a single pass through the input array.

Cons

The logic can be less intuitive to derive compared to the brute-force approach.
Requires extra space for the HashMap.

A straightforward approach is to examine every possible contiguous interval of days and check if it's a well-performing one. To do this efficiently, we first transform the input hours array. We can represent a tiring day as +1 and a non-tiring day as -1. A well-performing interval is then an interval where the sum of these new values is positive.

We can use two nested loops to generate all possible intervals. The outer loop determines the start of the interval, and the inner loop determines the end. For each interval, we calculate the sum of our +1/-1 scores. If the sum is greater than zero, we compare its length with the maximum length found so far and update it if necessary.

Algorithm

First, we simplify the problem by converting the hours array into a binary score array. A tiring day (hours[i] > 8) is represented by +1, and a non-tiring day (hours[i] <= 8) is represented by -1.
The problem now is to find the longest subarray with a sum strictly greater than 0.
We can iterate through all possible start and end points of a subarray.
Initialize maxLength = 0.
Use a nested loop. The outer loop fixes the starting index i from 0 to n-1.
The inner loop iterates from the starting index i to the end of the array, j from i to n-1.
For each subarray [i, j], calculate its sum. We can maintain a running sum in the inner loop to do this in O(1) for each j.
If the currentSum of the subarray [i, j] is greater than 0, it represents a well-performing interval. We update maxLength = max(maxLength, j - i + 1).
After checking all subarrays, maxLength will hold the length of the longest well-performing interval.

Walkthrough

This method iterates through every possible subarray (interval) of the given hours array. For each subarray, it counts the number of tiring and non-tiring days to check if it's a well-performing interval. To optimize the counting process, we can pre-process the hours array into a score array where a tiring day is +1 and a non-tiring day is -1. Then, for each subarray, we just need to compute the sum. A positive sum indicates a well-performing interval.

1class Solution {2    public int longestWPI(int[] hours) {3        int maxLength = 0;4        int n = hours.length;5        for (int i = 0; i < n; i++) {6            int currentSum = 0;7            for (int j = i; j < n; j++) {8                // Add 1 for a tiring day, -1 for a non-tiring day9                currentSum += (hours[j] > 8) ? 1 : -1;10                // If the sum is positive, the interval is well-performing11                if (currentSum > 0) {12                    maxLength = Math.max(maxLength, j - i + 1);13                }14            }15        }16        return maxLength;17    }18}

Complexity

Time

O(n^2), where n is the number of days. We have two nested loops to check every possible interval.

Space

O(1) extra space, as we only need a few variables to keep track of the current sum and maximum length.

Trade-offs

Pros

Simple to understand and implement.
It uses constant extra space (if we don't count the score array, which can be avoided).

Cons

The time complexity is quadratic, which can be too slow for large inputs (e.g., n=10^4).

Solutions

Solution

1class Solution { public int longestWPI ( int [] hours ) { int ans = 0 , s = 0 ; Map < Integer , Integer > pos = new HashMap <>(); for ( int i = 0 ; i < hours . length ; ++ i ) { s += hours [ i ] > 8 ? 1 : - 1 ; if ( s > 0 ) { ans = i + 1 ; } else if ( pos . containsKey ( s - 1 )) { ans = Math . max ( ans , i - pos . get ( s - 1 )); } pos . putIfAbsent ( s , i ); } return ans ; } }

1class Solution { public: int longestWPI ( vector < int >& hours ) { int ans = 0 , s = 0 ; unordered_map < int , int > pos ; for ( int i = 0 ; i < hours . size (); ++ i ) { s += hours [ i ] > 8 ? 1 : - 1 ; if ( s > 0 ) { ans = i + 1 ; } else if ( pos . count ( s - 1 )) { ans = max ( ans , i - pos [ s - 1 ]); } if ( ! pos . count ( s )) { pos [ s ] = i ; } } return ans ; } };

1class Solution : def longestWPI ( self , hours : List [ int ]) -> int : ans = s = 0 pos = {} for i , x in enumerate ( hours ): s += 1 if x > 8 else - 1 if s > 0 : ans = i + 1 elif s - 1 in pos : ans = max ( ans , i - pos [ s - 1 ]) if s not in pos : pos [ s ] = i return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem