D
DevExCode

LeetCode 1124: Longest Well-Performing Interval Solution

Master LeetCode problem 1124 (Longest Well-Performing Interval), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1124. Longest Well-Performing Interval

Medium
ArrayHash TableStackMonotonic StackPrefix Sum

Problem Explanation

Explanation

To solve this problem, we can use a hashmap to keep track of the cumulative difference between tiring and non-tiring days. We iterate through the given hours array, keeping track of the cumulative sum and the first occurrence of each cumulative sum in the hashmap. If at any point the current cumulative sum is greater than a previous cumulative sum by at least 1, that means we have found a well-performing interval. We then update the result with the maximum length of such intervals.

Algorithm:

  1. Initialize a hashmap to store cumulative sums and their indices.
  2. Initialize a variable result to store the maximum length of well-performing intervals.
  3. Initialize a variable cumulative to keep track of the cumulative difference.
  4. Iterate through the given hours array.
    • Increment cumulative by 1 if the current hour is greater than 8, otherwise decrement by 1.
    • If cumulative is greater than 0, update result to current index + 1.
    • If cumulative is not present in the hashmap, store its index.
  5. Return the result.

Time Complexity:

The time complexity of this solution is O(n), where n is the number of elements in the hours array.

Space Complexity:

The space complexity is O(n) for the hashmap.

Solution Code

class Solution {
    public int longestWPI(int[] hours) {
        int result = 0;
        int cumulative = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < hours.length; i++) {
            cumulative += hours[i] > 8 ? 1 : -1;
            if (cumulative > 0) {
                result = i + 1;
            }
            map.putIfAbsent(cumulative, i);
            if (map.containsKey(cumulative - 1)) {
                result = Math.max(result, i - map.get(cumulative - 1));
            }
        }
        return result;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1124 (Longest Well-Performing Interval)?

This page provides optimized solutions for LeetCode problem 1124 (Longest Well-Performing Interval) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1124 (Longest Well-Performing Interval)?

The time complexity for LeetCode 1124 (Longest Well-Performing Interval) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1124 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1124 in Java, C++, or Python.

Back to LeetCode Solutions