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].

 
Constraints:

1 <= hours.length <= 10000
0 <= hours[i] <= 16

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Range queries

Starter code: class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        

Solutions:
class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		(ans, count, seen) = (0, 0, {})
		for (i, hour) in enumerate(hours):
			count = count + 1 if hour > 8 else count - 1
			if count > 0:
				ans = i + 1
			else:
				if count not in seen:
					seen[count] = i
				if count - 1 in seen:
					ans = max(ans, i - seen[count - 1])
		return ans


class Solution:

	def findslavedays(self, hours):
		a = 0
		b = 0
		slave = 0
		nonslave = 0
		slavedays = 0
		while b < len(hours):
			if slave > nonslave:
				slavedays = max(slavedays, b - a + slave - nonslave - 1)
			if a == b:
				if hours[a] <= 8:
					nonslave += 1
				else:
					slave += 1
				b += 1
				continue
			if slave < nonslave:
				if hours[a] <= 8:
					nonslave -= 1
				else:
					slave -= 1
				a += 1
			elif slave >= nonslave:
				if hours[b] <= 8:
					nonslave += 1
				else:
					slave += 1
				b += 1
			if slave > nonslave:
				slavedays = max(slavedays, b - a + slave - nonslave - 1)
		print(a, b)
		while a > 0:
			a -= 1
			if hours[a] <= 8:
				nonslave += 1
			else:
				slave += 1
			if slave > nonslave:
				slavedays = max(slavedays, b - a + slave - nonslave - 1)
		if slave > nonslave:
			slavedays = max(slavedays, b - a + slave - nonslave - 1)
		return slavedays

	def longestWPI(self, hours: List[int]) -> int:
		isslave = [-1] * len(hours)
		sumslave = 0
		for i in range(len(isslave)):
			if hours[i] > 8:
				isslave[i] = 1
		dic = {}
		maxslavedays = 0
		print(isslave)
		for i in range(len(isslave)):
			sumslave = isslave[i] + sumslave
			if sumslave > 0:
				maxslavedays = max(maxslavedays, i + 1)
			if sumslave not in dic:
				dic[sumslave] = i
			if sumslave - 1 in dic:
				maxslavedays = max(maxslavedays, i - dic[sumslave - 1])
		print(dic)
		return maxslavedays
		print(isslave, sumslave)
		a = -1
		b = 0
		dic = {}
		dic[0] = -1
		for i in range(len(isslave)):
			if sumslave[i] > 0:
				b = i
				maxslavedays = max(maxslavedays, b - a)
			if sumslave[i] <= 0:
				a = i
		return maxslavedays
		return 0
		slavelength1 = self.findslavedays(hours)
		slavelength2 = self.findslavedays(hours[::-1])
		return max(slavelength1, slavelength2)


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		score = 0
		dic = {}
		result = 0
		for (i, hour) in enumerate(hours):
			if hour > 8:
				score += 1
			else:
				score -= 1
			if score > 0:
				result = i + 1
			if score not in dic:
				dic[score] = i
			if score - 1 in dic:
				result = max(result, i - dic[score - 1])
		return result


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		res = score = 0
		seen = {}
		for i in range(len(hours)):
			h = hours[i]
			score = score + 1 if h > 8 else score - 1
			if score > 0:
				res = i + 1
			seen.setdefault(score, i)
			if score - 1 in seen:
				res = max(res, i - seen[score - 1])
		return res


import bisect

class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		(r, l, l_idx) = ([], [], [])
		d = []
		for (i, x) in enumerate(hours):
			if i == 0:
				if x > 8:
					d.append(1)
				else:
					d.append(-1)
			elif x > 8:
				d.append(d[-1] + 1)
			else:
				d.append(d[-1] - 1)
		for (i, x) in enumerate(d):
			while len(r) > 0 and r[-1][0] <= x:
				r.pop()
			r.append((x, i))
			if len(l) == 0 or x < l[-1]:
				l.append(x)
				l_idx.append(i)
		ans = 0
		l.reverse()
		l_idx.reverse()
		for x in r:
			if x[0] > 0:
				ans = max(ans, x[1] + 1)
			else:
				idx = bisect.bisect_right(l, x[0] - 1)
				if idx >= 1:
					ans = max(ans, x[1] - l_idx[idx - 1])
		return ans


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		nums = []
		for hour in hours:
			if hour > 8:
				nums.append(1)
			else:
				nums.append(-1)
		(prevsum, sumv) = ([], 0)
		for num in nums:
			sumv += num
			prevsum.append(sumv)
		stack = []
		prevsum = [0] + prevsum
		for (i, val) in enumerate(prevsum):
			if not stack or prevsum[stack[-1]] > val:
				stack.append(i)
		(i, res) = (len(prevsum) - 1, 0)
		while i >= 0:
			while stack and prevsum[stack[-1]] < prevsum[i]:
				res = max(res, i - stack[-1])
				stack.pop()
			i -= 1
		return res


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		d = {}
		d[0] = -1
		res = 0
		for i in range(len(hours)):
			hours[i] = (1 if hours[i] > 8 else -1) + (0 if i == 0 else hours[i - 1])
			if hours[i] not in d:
				d[hours[i]] = i
			if hours[i] > 0:
				res = i + 1
			target = hours[i] - 1
			if target in d:
				res = max(res, i - d[target])
		print(hours)
		print(d)
		return res


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		hours = [1 if i > 8 else -1 for i in hours]
		hsh = {}
		vals = [0 for i in hours]
		sm = 0
		for i in range(len(hours) - 1, -1, -1):
			sm += hours[i]
			if sm > 0:
				vals[i] = max(vals[i], len(hours) - i)
			hours[i] = sm
			smo = hours[i] - 1
			if smo in hsh:
				v = hsh[smo]
				vals[i] = max(vals[i], v - i + vals[v])
			if hours[i] not in hsh:
				hsh[hours[i]] = i
		return max(vals)


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		d = {}
		P = [0]
		F = [0 for i in range(len(hours))]
		res = 0
		for i in range(len(hours)):
			P.append(P[-1] + (1 if hours[i] > 8 else -1))
			if P[-1] > 0:
				F[i] = i + 1
			else:
				s = d.get(P[-1] - 1, -1)
				if s >= 0:
					F[i] = max(F[i], i - s + F[s])
			if P[-1] not in d:
				d[P[-1]] = i
			res = max(res, F[i])
		return res


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		val = 0
		result = 0
		table = dict()
		for i in range(len(hours)):
			hour = hours[i]
			if hour > 8:
				val += 1
			else:
				val -= 1
			if val > 0:
				result = i + 1
			else:
				if val not in table:
					table[val] = i
				if val - 1 in table:
					dist = i - table[val - 1]
					if dist > result:
						result = dist
		return result


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		sum = 0
		ans = 0
		d = {}
		for i in range(len(hours)):
			sum = sum + 1 if hours[i] > 8 else sum - 1
			if sum > 0:
				ans = i + 1
			else:
				if sum not in d:
					d[sum] = i
				if sum - 1 in d:
					ans = max(ans, i - d[sum - 1])
		return ans


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		seen = {}
		(result, score) = (0, 0)
		for (i, num) in enumerate(hours):
			score += 1 if num > 8 else -1
			if score > 0:
				result = i + 1
			elif score - 1 in seen:
				result = max(result, i - seen[score - 1])
			seen.setdefault(score, i)
		return result


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		n = len(hours)
		hashmap = dict()
		total = 0
		res = 0
		for i in range(n):
			if hours[i] <= 8:
				total -= 1
			else:
				total += 1
			if total > 0:
				res = i + 1
				continue
			else:
				if total not in hashmap:
					hashmap[total] = i
				if total - 1 in hashmap:
					res = max(res, i - hashmap[total - 1])
		return res


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		bits = [1 if x > 8 else -1 for x in hours]
		pref = [0] * (len(bits) + 1)
		for i in range(1, len(bits) + 1):
			pref[i] = pref[i - 1] + bits[i - 1]
		ans = 0
		min_val = len(bits) + 1
		for y in sorted(enumerate(pref), key=lambda x: (x[1], -x[0])):
			min_val = min(min_val, y[0])
			ans = max(ans, y[0] - min_val)
		return ans


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		s = 0
		seen = {}
		ans = 0
		for (i, h) in enumerate(hours):
			if h > 8:
				s += 1
			else:
				s -= 1
			if s > 0:
				ans = i + 1
			seen.setdefault(s, i)
			if s - 1 in seen:
				ans = max(ans, i - seen[s - 1])
		return ans


class Solution:

	def longestWPI(self, hours):
		res = score = 0
		seen = {}
		for (i, h) in enumerate(hours):
			print((i, h))
			if h > 8:
				score += 1
			else:
				score -= 1
			if score > 0:
				res = i + 1
			seen.setdefault(score, i)
			if score - 1 in seen:
				res = max(res, i - seen[score - 1])
		return res


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		final = 0
		score = 0
		stack = {}
		for i in range(len(hours)):
			if hours[i] > 8:
				score += 1
			else:
				score -= 1
			stack.setdefault(score, i)
			if score > 0:
				final = i + 1
			if score - 1 in stack:
				final = max(final, i - stack[score - 1])
		return final


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		L = [1 if i > 8 else -1 for i in hours]
		K = [1 if i > 8 else -1 for i in hours]
		mp = {}
		for i in range(0, len(hours)):
			if i > 0:
				s = L[i] = L[i] + L[i - 1]
			else:
				s = L[i]
			if s not in mp:
				mp[s] = {i: True}
			else:
				mp[s][i] = True
		result = 0
		for (i, c) in enumerate(L):
			if L[-1] > L[i]:
				result = max(result, len(K) - i - 1)
			if 0 < L[i]:
				result = max(result, i + 1)
			if i > 0 and L[i - 1] + 1 in mp:
				s = mp[L[i - 1] + 1]
				result = max(result, max(s) - i + 1)
			if L[i] - 1 in mp:
				s = mp[L[i] - 1]
				result = max(result, i - min(s))
		return result

	def longestWPI(self, hours: List[int]) -> int:
		mp = {}
		accu = 0
		result = 0
		for (i, v) in enumerate(hours):
			accu += 1 if v > 8 else -1
			if accu > 0:
				result = max(result, i + 1)
				print((result, i))
			if accu - 1 in mp:
				result = max(result, i - mp[accu - 1])
				print((result, i))
			if accu not in mp:
				mp[accu] = i
		return result


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		ret = 0
		overall = 0
		totals = {}
		for (i, h) in enumerate(hours):
			if h > 8:
				overall += 1
			else:
				overall -= 1
			if overall > 0:
				ret = i + 1
			else:
				if overall - 1 in totals:
					length = i - totals[overall - 1]
					ret = max(ret, length)
				if overall not in totals:
					totals[overall] = i
		return ret


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		pre_sum = [0]
		for (i, v) in enumerate(hours):
			hours[i] = 1 if v > 8 else -1
			pre_sum.append(pre_sum[-1] + hours[i])
		dec_stack = []
		for (i, v) in enumerate(pre_sum):
			if len(dec_stack) == 0 or (len(dec_stack) > 0 and v < pre_sum[dec_stack[-1]]):
				dec_stack.append(i)
		max_r = -math.inf
		max_width = 0
		for r in range(len(pre_sum) - 1, -1, -1):
			n = pre_sum[r]
			if n < max_r:
				continue
			max_r = n
			while len(dec_stack) > 0:
				left_idx = dec_stack[-1]
				if pre_sum[left_idx] < n:
					dec_stack = dec_stack[0:-1]
					max_width = max(max_width, r - left_idx)
				else:
					break
			if len(dec_stack) == 0:
				break
		return max_width


class Solution:

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


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		days = [1 if hour > 8 else -1 for hour in hours]
		prefSums = days[:]
		for i in range(1, len(hours)):
			prefSums[i] = days[i] + prefSums[i - 1]
		result = 0
		prefixLookup = {}
		for i in range(len(hours)):
			sumToHere = prefSums[i]
			if sumToHere >= 1:
				result = max(result, i + 1)
			else:
				earlierPrefSumNeeded = sumToHere - 1
				if earlierPrefSumNeeded in prefixLookup:
					result = max(result, i - prefixLookup[earlierPrefSumNeeded])
			if sumToHere not in prefixLookup:
				prefixLookup[sumToHere] = i
		return result


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		lt = []
		for hour in hours:
			if hour > 8:
				lt.append(1)
			else:
				lt.append(-1)
		seen = {}
		s = 0
		mx = 0
		for (idx, ele) in enumerate(lt):
			s += ele
			print((s, idx, mx))
			if s > 0:
				mx = max(mx, idx + 1)
			elif s - 1 in seen:
				i = seen[s - 1]
				mx = max(mx, idx - i)
			if s not in seen:
				seen[s] = idx
		return mx


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		prefix = []
		for hour in hours:
			if hour > 8:
				prefix.append(1)
			else:
				prefix.append(-1)
		curr_sum = 0
		seen = {0: -1}
		res = 0
		for (i, num) in enumerate(prefix):
			curr_sum += num
			if curr_sum > 0:
				res = i + 1
			if curr_sum - 1 in seen:
				res = max(res, i - seen[curr_sum - 1])
			if curr_sum not in seen:
				seen[curr_sum] = i
		return res


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		cur = res = 0
		seen = {}
		for (i, h) in enumerate(hours):
			cur += 1 if h > 8 else -1
			if cur > 0:
				res = max(res, i + 1)
			elif cur - 1 in seen:
				res = max(res, i - seen[cur - 1])
			if cur not in seen:
				seen[cur] = i
		return res


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		n = len(hours)
		hours = [1 if x > 8 else -1 for x in hours]
		s = 0
		idx = {}
		ans = 0
		for i in range(len(hours)):
			s += hours[i]
			if s > 0:
				ans = i + 1
			if s not in idx:
				idx[s] = i
			if s - 1 in idx:
				ans = max(ans, i - idx[s - 1])
		return ans


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		seen = dict()
		cnt = 0
		res = 0
		for (idx, h) in enumerate(hours):
			if h > 8:
				cnt += 1
			else:
				cnt -= 1
			if cnt > 0:
				res = idx + 1
			elif cnt - 1 in seen:
				res = max(res, idx - seen[cnt - 1])
			if cnt not in seen:
				seen[cnt] = idx
		return res


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		(Sum, ans) = (0, 0)
		cache = {}
		for (i, n) in enumerate(hours):
			Sum = Sum + 1 if n > 8 else Sum - 1
			if Sum > 0:
				ans = i + 1
			if Sum - 1 in cache:
				ans = max(ans, i - cache[Sum - 1])
			cache.setdefault(Sum, i)
		return ans


class Solution:

	def longestWPI(self, h: List[int]) -> int:
		n = len(h)
		for i in range(n):
			if h[i] > 8:
				h[i] = 1
			else:
				h[i] = -1
		pre = [0] * n
		pre[0] = h[0]
		maxi = 0
		for i in range(1, n):
			pre[i] = pre[i - 1] + h[i]
		d = {}
		print(pre)
		for x in range(n):
			if pre[x] > 0:
				maxi = x + 1
			if d.get(pre[x] - 1, -1) != -1:
				maxi = max(maxi, x - d[pre[x] - 1])
			if d.get(pre[x], -1) == -1:
				d[pre[x]] = x
		return maxi


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		i = 0
		prefixSum = 0
		existed = {0: 0}
		res = 0
		while i <= len(hours) - 1:
			if hours[i] >= 9:
				prefixSum += 1
			else:
				prefixSum -= 1
			if prefixSum not in existed:
				existed[prefixSum] = i + 1
			if prefixSum - 1 in existed:
				res = max(res, i + 1 - existed[prefixSum - 1])
			if prefixSum >= 1:
				res = max(res, i + 1)
			i += 1
		return res


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		(score, longest) = (0, 0)
		index = {}
		for (i, n) in enumerate(hours):
			score += 1 if n > 8 else -1
			if score > 0:
				longest = max(longest, i + 1)
			index.setdefault(score, i)
			if score - 1 in index:
				longest = max(longest, i - index[score - 1])
		return longest


import bisect

class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		starts = []
		startIndexes = []
		counts = [0] * len(hours)
		for i in range(len(hours)):
			if i > 0:
				counts[i] = counts[i - 1]
			if hours[i] > 8:
				counts[i] += 1
			else:
				counts[i] -= 1
		counts = [0] + counts
		for i in range(len(counts) - 1, -1, -1):
			numGood = counts[i]
			while starts and starts[-1] >= numGood:
				starts.pop()
				startIndexes.pop()
			starts.append(numGood)
			startIndexes.append(i)
		maxLen = 0
		for (i, c) in enumerate(counts):
			target = c - 1
			pos = bisect.bisect_right(starts, target)
			if pos == len(starts) or starts[pos] > target:
				pos -= 1
			if pos >= 0:
				lenHere = i - startIndexes[pos]
				maxLen = max(maxLen, lenHere)
		return maxLen


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		hoursLen = len(hours)
		tDay = []
		preSum = 0
		preSumDict = {0: -1}
		preSumKeys = [0]
		ans = 0

		def insertAt(x):
			l = 0
			r = len(preSumKeys) - 1
			if x < preSumKeys[l]:
				return 0
			if x > preSumKeys[r]:
				return r + 1
			while r > l:
				m = (r + l) // 2
				if preSumKeys[m] < x:
					l = m + 1
				else:
					r = m
			return l
		ans = 0
		for (i, hour) in enumerate(hours):
			if hour > 8:
				tDay.append(1)
				preSum += 1
			else:
				tDay.append(-1)
				preSum -= 1
			tempIndex = insertAt(preSum)
			if preSum not in preSumDict:
				preSumDict[preSum] = i
				preSumKeys.insert(tempIndex, preSum)
			if tempIndex > 0:
				preSumDict[preSumKeys[tempIndex]] = min(preSumDict[preSumKeys[tempIndex - 1]], preSumDict[preSumKeys[tempIndex]])
				ans = max(ans, i - preSumDict[preSumKeys[tempIndex - 1]])
		return ans


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		s = 0
		maxLen = 0
		seen = {}
		for (idx, hour) in enumerate(hours):
			if hour > 8:
				s += 1
			else:
				s -= 1
			if s > 0:
				res = idx + 1
				maxLen = max(maxLen, res)
			elif s - 1 in seen:
				res = idx - seen[s - 1]
				maxLen = max(maxLen, res)
			if s not in seen:
				seen[s] = idx
		return maxLen


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		(stack, res, first) = (0, 0, {})
		for (day, i) in enumerate(hours):
			stack = stack + 1 if i > 8 else stack - 1
			first.setdefault(stack, day)
			if stack > 0:
				res = day + 1
			elif stack - 1 in first:
				res = max(res, day - first[stack - 1])
		return res


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		stack = []
		ans = accu = 0
		for (i, h) in enumerate(hours):
			if h > 8:
				accu += 1
			else:
				accu -= 1
			if accu > 0:
				ans = i + 1
			else:
				(L, U) = (-1, len(stack))
				while L + 1 < U:
					m = (L + U) // 2
					if stack[m][1] < accu:
						U = m
					else:
						L = m
				if U < len(stack):
					ans = max(ans, i - stack[U][0])
			if not stack or stack[-1][1] > accu:
				stack.append((i, accu))
		return ans


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		total = res = 0
		index = {}
		for (i, h) in enumerate(hours):
			total += 1 if h > 8 else -1
			if total > 0:
				res = i + 1
			if total - 1 in index:
				res = max(res, i - index[total - 1])
			index.setdefault(total, i)
		return res


class Solution:

	def longestWPI(self, hours: List[int]) -> int:
		s = []
		for i in hours:
			if i > 8:
				s.append(1)
			else:
				s.append(-1)
		n = len(s)
		presum = [0] * (n + 1)
		for i in range(1, n + 1):
			presum[i] = presum[i - 1] + s[i - 1]
		stack = []
		n = len(presum)
		for i in range(n):
			if not stack or presum[stack[-1]] > presum[i]:
				stack.append(i)
		res = 0
		i = n - 1
		while i > res:
			while stack and presum[stack[-1]] < presum[i]:
				res = max(res, i - stack[-1])
				stack.pop()
			i -= 1
		return res