Welcome to Subscribe On Youtube

Question

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

Algorithm

Code

• Java
• C++
• Python
• Go

• // 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