Longest Well-Performing Interval LeetCode solution in Java

1
// Brute Force Approach : PrefixSum ((Tiring - Non Tiring) Days) + Checking All Sliding Windows
2
// (Lengths 1 To n)
3
// For Longest Well Performing Interval/Window
4
// T.C. = O(n^2) , S.C. = O(n)
5
class Solution {
6

7
  public int longestWPI(int[] hours) {
8
    int n = hours.length;
9

10
    int[] prefixSumTiringDaysMinusNonTiringDaysArr = new int[n + 1];
11
    prefixSumTiringDaysMinusNonTiringDaysArr[0] = 0;
12

13
    int prefixSumTiringDaysCount = 0;
14
    int prefixSumNonTiringDaysCount = 0;
15

16
    for (int i = 0; i < n; i++) {
17
      int noOfHoursWorkedToday = hours[i];
18

19
      if (noOfHoursWorkedToday > 8) {
20
        prefixSumTiringDaysCount++;
21
      } else {
22
        prefixSumNonTiringDaysCount++;
23
      }
24

25
      prefixSumTiringDaysMinusNonTiringDaysArr[i + 1] =
26
          prefixSumTiringDaysCount - prefixSumNonTiringDaysCount;
27
      // System.out.print(prefixSumTiringDaysMinusNonTiringDaysArr[i] + " ");
28
    }
29
    // System.out.println(prefixSumTiringDaysMinusNonTiringDaysArr[n]);
30

31
    int longestLengthOfContinuousPositiveSequence = 0;
32

33
    for (int currentSlidingWindowLength = 1;
34
        currentSlidingWindowLength <= n;
35
        currentSlidingWindowLength++) {
36
      // System.out.print(currentSlidingWindowLength + " - ");
37
      for (int i = 0; i <= n - currentSlidingWindowLength; i++) {
38
        int j = i + currentSlidingWindowLength - 1;
39
        // System.out.print(i + "," + j + " ");
40
        int currentIntervalNoOfTiringDaysMinusNonTiringDays =
41
            prefixSumTiringDaysMinusNonTiringDaysArr[j + 1]
42
                - prefixSumTiringDaysMinusNonTiringDaysArr[i];
43
        if (currentIntervalNoOfTiringDaysMinusNonTiringDays
44
            > 0) { // => currentInterval = Well Performing Interval
45
          longestLengthOfContinuousPositiveSequence =
46
              Math.max(currentSlidingWindowLength, longestLengthOfContinuousPositiveSequence);
47
        }
48
      }
49
      // System.out.println();
50
    }
51
    // System.out.println();
52

53
    int lengthOfLongestWellPerformingInterval = longestLengthOfContinuousPositiveSequence;
54

55
    return lengthOfLongestWellPerformingInterval;
56
  }
57
}