1124. Longest Well-Performing Interval

📝 Problem Details

• Title: 1124. Longest Well-Performing Interval
• Link: https://leetcode.com/problems/longest-well-performing-interval/
• Difficulty: Medium
• Tags/Categories: Hashmap Arrays Prefix-Sum

💭What Were My Initial Thoughts?

- mind initially went to a sliding window approach but i dont think that would work well
- we need a way of indicating a day as "tiring" as we iterate through the array
	- we can flag and store tiring / not-tiring days in a separate data structure

🤔What Did I Struggle With?

💡 Explanation of Solution

1. input transformation
	- convert the input array hours into a sequence of +1 and -1 based on whether hours[i] > 8 or not 

2. use prefix sum
	- maintain a running sum to track the cumulative effective of transformed values

3. check well-performing conditions
	- if sum > 0, the interval [0....i] is already well-performing because the cumulative effect is positive
	- if the sum <= 0, check if sum - 1 exists in the earlier hashmap
		- if found, calculate the length of the subarray that starts after this index and ends at i

4. record earlier occurrences
	- for each prefix sum, if it hasn't been recorded in earlier, record the current index as the earliest occurence of this sum

5. output the result
	- the value of res keeps track of the longest well performing interval 

⌛ Complexity Analysis

Time Complexity: O(n), a single pass through of the hours array
Space Complexity: O(n), worst case of n indices being stored in our hashmap

💻 Implementation of Solution

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        int n = hours.size();
        int sum = 0;         // Running prefix sum
        int res = 0;         // Track longest well-performing interval length
        unordered_map<int,int> earliest; // Maps sum -> earliest index where sum was seen
 
        for(int i = 0; i < n; i++){
            // Step 1: transform hours[i] to +1 or -1
            if(hours[i] > 8) {
                sum += 1;
            } else {
                sum -= 1;
            }
 
            // Step 2: if sum > 0, subarray [0..i] is already well-performing
            if(sum > 0) {
                res = i + 1;  // i+1 = length from index 0 to i
            } 
            else {
                // Step 3: check if we have (sum - 1) in earliest map
                if(earliest.find(sum - 1) != earliest.end()) {
                    res = max(res, i - earliest[sum - 1]);
                }
            }
 
            // Step 4: record earliest occurrence of this sum
            if(!earliest.count(sum)) {
                earliest[sum] = i;
            }
        }
 
        return res;
    }
};