What is the time complexity of Longest Well-Performing Interval?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Longest Well-Performing Interval?

This problem uses Array, Hash Table, Stack, Monotonic Stack, Prefix Sum. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Longest Well-Performing Interval?

Insight 1: Convert the problem to a prefix sum problem. Represent tiring days as +1 and non-tiring days as -1. A well-performing interval is then equivalent to a subarray with a positive sum. Insight 2: If the overall score (prefix sum) is positive at index 'i', then the interval [0, i] is a well-performing interval. This gives us a candidate for the longest well-performing interval.

Which companies ask LeetCode 1124. Longest Well-Performing Interval in interviews?

This problem is frequently asked at Infosys.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Longest Well-Performing Interval - LeetCode 1124 Solution

Longest Well-Performing Interval - Complete Solution Guide

Longest Well-Performing Interval is LeetCode problem 1124, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 interva

Detailed Explanation

The problem asks us to find the longest interval of days within a given list of working hours such that the number of tiring days (days with more than 8 hours worked) is strictly greater than the number of non-tiring days. We are given an array `hours` where each element represents the number of hours worked on a given day. The goal is to return the length of the longest such interval. If no such interval exists, we return 0.

Solution Approach

The provided solution uses a prefix sum approach combined with a hash map to store the first occurrence of each prefix sum. The `score` variable tracks the running sum of tiring days (+1) and non-tiring days (-1). The `seen_scores` hash map stores the first index where each score is seen. For each index `i`, we update the `score`. If the `score` is positive, the interval [0, i] is a candidate for the longest well-performing interval. Otherwise, we check if `score - 1` exists in `seen_scores`. If it does, it means there was a previous index 'k' where the score was `score - 1`. The interval (k, i] would then have a sum of `score - (score - 1) = 1`, making it a well-performing interval. We update `max_length` accordingly.

Step-by-Step Algorithm

Step 1: Initialize `score` to 0 and `max_length` to 0.
Step 2: Initialize a hash map `seen_scores` to store the first index of each score. Add the initial score of 0 at index -1 to handle edge cases.
Step 3: Iterate through the `hours` array from index 0 to n-1.
Step 4: For each day, update the `score`. If `hours[i] > 8`, increment `score` by 1. Otherwise, decrement `score` by 1.
Step 5: If `score > 0`, update `max_length` to `i + 1` because [0, i] is a well-performing interval.
Step 6: If `score <= 0`, check if `score - 1` is present in `seen_scores`. If it is, update `max_length` to `max(max_length, i - seen_scores[score - 1])`.
Step 7: If the current `score` is not already in `seen_scores`, add it to the `seen_scores` along with its index `i`.
Step 8: After iterating through all the days, return `max_length`.

Key Insights

Insight 1: Convert the problem to a prefix sum problem. Represent tiring days as +1 and non-tiring days as -1. A well-performing interval is then equivalent to a subarray with a positive sum.
Insight 2: If the overall score (prefix sum) is positive at index 'i', then the interval [0, i] is a well-performing interval. This gives us a candidate for the longest well-performing interval.
Insight 3: To find a well-performing interval ending at index 'i' when the prefix sum at 'i' is non-positive, look for a previous index 'k' such that `score[i] - score[k] > 0`, which simplifies to `score[k] < score[i]`. To maximize the interval length (i - k), we need to find the smallest such 'k'.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Stack, Monotonic Stack, Prefix Sum.

Companies

Asked at: Infosys.

Longest Well-Performing Interval | LeetCode 1124

Medium

Array Hash Table Stack Monotonic Stack Prefix Sum

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int longestWPI(int[] hours) {
        int score = 0;
        int maxLength = 0;

        // A map from score to the first index where that score was seen.
        Map<Integer, Integer> seenScores = new HashMap<>();
        seenScores.put(0, -1);

        for (int i = 0; i < hours.length; i++) {
            int h = hours[i];
            if (h > 8) {
                score += 1;
            } else {
                score -= 1;
            }

            // If the current score is positive, the interval from the beginning [0, i]
            // is a well-performing interval. The length is i + 1.
            if (score > 0) {
                maxLength = i + 1;
            } else {
                // We are looking for an interval (k, i] with a positive sum.
                // The sum of this interval is score_i - score_k.
                // We need score_i - score_k > 0, which means score_k < score_i.
                // To maximize the length (i - k), we need to find the smallest k.
                // A candidate for score_k is score_i - 1.
                // If we have seen `score - 1` before, it gives us a valid interval.
                // The sum would be score - (score - 1) = 1.
                if (seenScores.containsKey(score - 1)) {
                    maxLength = Math.max(maxLength, i - seenScores.get(score - 1));
                }
            }

            // Store the first time a score is seen.
            if (!seenScores.containsKey(score)) {
                seenScores.put(score, i);
            }
        }

        return maxLength;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1124: Longest Well-Performing Interval - Detailed explanation and solution approaches.

Topics

Array Hash Table Stack Monotonic Stack Prefix Sum

Companies

Infosys

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:1124

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Initialize `score` to 0 and `max_length` to 0.
2
Step 2: Initialize a hash map `seen_scores` to store the first index of each score. Add the initial score of 0 at index -1 to handle edge cases.
3
Step 3: Iterate through the `hours` array from index 0 to n-1.
4
Step 4: For each day, update the `score`. If `hours[i] > 8`, increment `score` by 1. Otherwise, decrement `score` by 1.
5
Step 5: If `score > 0`, update `max_length` to `i + 1` because [0, i] is a well-performing interval.
6
Step 6: If `score <= 0`, check if `score - 1` is present in `seen_scores`. If it is, update `max_length` to `max(max_length, i - seen_scores[score - 1])`.
7
Step 7: If the current `score` is not already in `seen_scores`, add it to the `seen_scores` along with its index `i`.
8
Step 8: After iterating through all the days, return `max_length`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is O(n) because each element in the `hours` array is processed in constant time. The space complexity is O(n) because, in the worst-case scenario where the score alternates between positive and negative values, the hash map `seen_scores` could store up to 'n' unique score values.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Iterate through all possible subarrays and check if they are well-performing. This involves calculating the number of tiring and non-tiring days for each subarray.

Time: O(n^2), where n is the length of the `hours` array.Space: O(1)

Trade-offs: This approach is simpler to understand but significantly less efficient than the prefix sum approach. It's suitable for small input sizes but will time out for larger inputs. It avoids using extra space, so useful if memory is extremely constrained.

✨

Key Insights

1Insight 1: Convert the problem to a prefix sum problem. Represent tiring days as +1 and non-tiring days as -1. A well-performing interval is then equivalent to a subarray with a positive sum.
2Insight 2: If the overall score (prefix sum) is positive at index 'i', then the interval [0, i] is a well-performing interval. This gives us a candidate for the longest well-performing interval.
3Insight 3: To find a well-performing interval ending at index 'i' when the prefix sum at 'i' is non-positive, look for a previous index 'k' such that `score[i] - score[k] > 0`, which simplifies to `score[k] < score[i]`. To maximize the interval length (i - k), we need to find the smallest such 'k'.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

Edge Cases

Edge case 1: Empty input array. The code will correctly return 0 because the loop won't execute.
Edge case 2: All days are non-tiring (hours[i] <= 8 for all i). The score will keep decreasing, and no interval will be well-performing. The algorithm correctly returns 0 as max_length will never be updated beyond its initial value.
Edge case 3: All days are tiring (hours[i] > 8 for all i). The score will keep increasing, and the longest well-performing interval will be the entire array. The condition `score > 0` will always be true after the first iteration, and max_length will eventually become the size of the array.
Edge case 4: The importance of initializing `seen_scores` with `{0: -1}`. Consider the case where the first day is a tiring day. The score will be 1. Without this initialization, the algorithm would miss the interval of length 1.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not initializing `seen_scores` with `{0: -1}`. This can lead to incorrect results when the prefix sum becomes positive at the beginning.

✗Common mistake 2: Forgetting to update `max_length` when `score > 0`. This condition ensures that the interval from the beginning to the current index is considered.

✗Common mistake 3: Not considering the case where the input hours array is empty. Although, based on the constraints, the array will never be empty.

✗Common mistake 4: Incorrectly calculating the length of the interval. The length is `i - seen_scores[score - 1]` and not `i - seen_scores[score]`.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Analyzing website traffic. Identify periods where the number of active users significantly exceeds the number of inactive users.

🏦Real-world scenario 2: Stock market analysis. Determine periods where the number of days with positive stock gains outweighs the number of days with losses, indicating a bullish trend.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 15, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 14

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Longest Well-Performing Interval"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?