Introduction

In this blog post, we will explore how to solve the LeetCode problem "1124" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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]. Example 2: Input: hours = [6,6,6] Output: 0 Constraints: 1 <= hours.length <= 104 0 <= hours[i] <= 16

Explanation

Here's the approach to solve this problem:

• Transform the Input: Convert the input array hours into an array where tiring days are represented by 1 and non-tiring days by -1. This simplifies the problem to finding a subarray with a positive sum.
• Prefix Sum and Hash Map: Calculate the prefix sum of the transformed array. Use a hash map to store the first occurrence of each prefix sum. This helps in efficiently identifying the longest well-performing interval.

• Iterate and Maximize: Iterate through the prefix sums. If the current prefix sum is positive, the interval from the start to the current index is a well-performing interval. Otherwise, look for a previous index in the hash map where the prefix sum was one less than the current prefix sum. The difference between the current index and that previous index gives the length of a potential well-performing interval. Maximize this length.

• Runtime Complexity: O(n), Storage Complexity: O(n)

Code

    def longestWPI(hours):
    n = len(hours)
    prefix_sum = 0
    max_len = 0
    prefix_sum_map = {0: -1}  # Store first occurrence of each prefix sum

    for i in range(n):
        prefix_sum += 1 if hours[i] > 8 else -1

        if prefix_sum > 0:
            max_len = i + 1
        else:
            if prefix_sum - 1 in prefix_sum_map:
                max_len = max(max_len, i - prefix_sum_map[prefix_sum - 1])

            if prefix_sum not in prefix_sum_map:
                prefix_sum_map[prefix_sum] = i

    return max_len