Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/1124.html


Algorithm

Code

  • 
    
    
  • // OJ: https://leetcode.com/problems/longest-well-performing-interval/
    // Time: O(NlogN)
    // Space: O(N)
    class Solution {
    public:
        int longestWPI(vector<int>& A) {
            int N = A.size(), ans = 0;
            for (int &n : A) n = n > 8 ? 1 : -1;
            vector<int> prefix(N + 1), s{0};
            for (int i = 0; i < N; ++i) prefix[i + 1] = prefix[i] + A[i];
            for (int i = 1; i <= N; ++i) {
                if (prefix[i] == prefix[s.back()]) continue;
                else if (prefix[i] < prefix[s.back()]) s.push_back(i);
                else {
                    auto it = upper_bound(begin(s), end(s), prefix[i], [&](int a, int b) { return prefix[b] < a; });
                    ans = max(ans, i - *it);
                }
            }
            return ans;
        }
    };
    
  • class Solution:
        def longestWPI(self, hours: List[int]) -> int:
            ans = s = 0
            seen = {}
            for i, h in enumerate(hours):
                s += 1 if h > 8 else -1
                if s > 0:
                    ans = i + 1
                else:
                    if s not in seen:
                        seen[s] = i
                    if s - 1 in seen:
                        ans = max(ans, i - seen[s - 1])
            return ans
    
    ############
    
    # 1124. Longest Well-Performing Interval
    # https://leetcode.com/problems/longest-well-performing-interval/
    
    class Solution:
        def longestWPI(self, hours: List[int]) -> int:
            n = len(hours)
            seen = {}
            res = v = 0
            
            for i, h in enumerate(hours):
                v = v + 1 if h > 8 else v - 1
                            
                if v > 0:
                    res = i + 1
                    
                seen.setdefault(v, i)
    
                if v - 1 in seen:
                    res = max(res, i - seen[v - 1])
            
            return res
    
    
  • func longestWPI(hours []int) (ans int) {
    	s := 0
    	pos := map[int]int{}
    	for i, x := range hours {
    		if x > 8 {
    			s++
    		} else {
    			s--
    		}
    		if s > 0 {
    			ans = i + 1
    		} else if j, ok := pos[s-1]; ok {
    			ans = max(ans, i-j)
    		}
    		if _, ok := pos[s]; !ok {
    			pos[s] = i
    		}
    	}
    	return
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    

All Problems

All Solutions