Leetcode 1176. Diet Plan Performance: C# | O(N) time complexity | DP solution

 Sept. 1, 2021

C# | O(N) time complexity | DP solution

Aug. 31, 2021

Introduction
The idea is to calculate sliding window with size k, each time one number is added, if the size of window is bigger than k, then one element in left side will be removed.

DP solution | One subtraction, one addition | sliding window with size k
Time complexity should be optimal, to maintain a window size k, each slide takes O(1) calculation, one substraction and one addition.

First k elements starts from index = 0, and ends at index = k -1. So the following statement describe a window to remove one element in the leftmost side.

if( i >= k)
{
	sumK -= calories[i - k];
}

The following code passes online judge.

public class Solution {
    // using O(N) time complexity, DP solution - O(1) to move next calculation of sum
    public int DietPlanPerformance(int[] calories, int k, int lower, int upper) {
        if(calories == null || calories.Length < k || lower > upper)
            return 0; 
        
        var length = calories.Length; 
        var sumK = 0; 
        var total = 0;
        
        for(int i = 0; i < length; i++)
        {
            var current = calories[i];
            
            sumK += current;
            if(i >= k)
            {
                sumK -= calories[i - k];
            }
            
            if(i >= k - 1)
            {
                if(sumK < lower)
                {
                    total--;
                }
                else if(sumK > upper)
                {
                    total++;
                }
            }
        }
        
        return total; 
    }
}