Skip to content

1124. Longest Well-Performing Interval 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int longestWPI(vector<int>& hours) {
    int ans = 0;
    int prefix = 0;
    unordered_map<int, int> map;

    for (int i = 0; i < hours.size(); ++i) {
      prefix += hours[i] > 8 ? 1 : -1;
      if (prefix > 0) {
        ans = i + 1;
      } else {
        if (!map.count(prefix))
          map[prefix] = i;
        if (const auto it = map.find(prefix - 1); it != map.cend())
          ans = max(ans, i - it->second);
      }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def longestWPI(self, hours: List[int]) -> int:
    ans = 0
    prefix = 0
    dict = {}

    for i in range(len(hours)):
      prefix += 1 if hours[i] > 8 else -1
      if prefix > 0:
        ans = i + 1
      else:
        if prefix not in dict:
          dict[prefix] = i
        if prefix - 1 in dict:
          ans = max(ans, i - dict[prefix - 1])

    return ans