How To Calculate Time Complexity of an Algorithm.

We calculate the Time and Space complexity of any algorithm by finding the growth rate of the function for different values of N where N is the size of our input. In most cases, we check an algorithm for a bigger value of N to get the worst-case time complexity of an Algorithm. 

It might be possible that one algorithm is giving the best results for smaller values of N and for the same problem another algorithm is giving the best results for larger values of N so we can't predict after which value of N one algorithm is better than other algorithm and this is the reason why we need to check for different values of N. 

But isn't it a tedious task to plug in different values of N to find the growth rate of any program? Here we use our Asymptotic Notations (more specifically Big O notation) to describe the growth rate or time complexity of our programs. 

Before going further into this topic to learn time complexity calculation, we will highly recommend you go through our Algorithms Introduction and Analysis post once. It will help you understand the terminologies used in this post. (alert-passed)  

What is Big O Notation?

When we want to find the running time of an algorithm we are not interested in calculating the exact running time because it is not possible to calculate the exact running time of each algorithm. We always calculate the approximate running time and Big O Notation helps us to achieve this. 

Big O Notation helps us find the time complexity in terms of the size of the input and the best part is that it gives us the upper bound of the function that tells us about the worse case time complexity of an algorithm because the function can never grow faster than this upper bound.

Condition for Big O Notation:

If f(n) and g(n) are the two functions, then

f(n) = O(g(n)) if there exists constants c and no such that f(n) ≤ c.g(n), for all n ≥ no.

Example: 
Given f(n) = n
Is f(n) = O(g(n))?

Let g(n) = 2n

f(n) ≤ c.g(n)
   n ≤ c.2n for all c = 1 and n. = 1

Yes, f(n) = O(g(n))
     f(n) = O(2n) ≈ O(n) Linear Growth

Below is the growth rate of some Standard Functions.

Let's understand the time complexity calculation with some example programs.

Example: Program to calculate the sum of first N natural numbers (using a loop).

//C++ Code to sum n natural numbers
#include<iostream>
using namespace std;

int main(){

    int sum = 0, n;              // ---> 1 time
    cin>>n;                      // ---> 1 time 

    for(int i = 1; i <= n; i++){ 
        sum = sum + i;           // ---> n times 
    }

    cout<<sum;                  // ---> 1 time 

    return 0;                   // ---> 1 time 
}

Output:

5
15

Calculation of Time complexity:

Total number of instruction = f(n) = n + 4

f(n) = n + 4
Let g(n) = n

f(n) ≤ c.g(n)
n+4 ≤ c.n
n ≥ 4

Is f(n) = O(g(n)) ?
Yes, f(n) ≤ c.g(n) for all n ≥ no
where c = 2 and no = 4

f(n) = O(n) Linear Time Complexity

Example: Program to calculate the sum of first N natural numbers (using a formula).

//C++ Code to sum n natural numbers
#include<iostream>
using namespace std;

int main(){

    int sum = 0, n;              // ---> 1 time
    cin>>n;                      // ---> 1 time 

    sum = n*(n+1)/2;            // ---> 1 time
    cout<<sum;                  // ---> 1 time 

    return 0;                   // ---> 1 time 
}

Output:

5
15

Calculation of Time complexity:

Total number of instruction = f(n) = 5

f(n) = 5
Let g(n) = 1

f(n) ≤ c.g(n)
5 ≤ c.1
Take c = 6
5 ≤ 6

Is f(n) = O(g(n)) ?
Yes, f(n) ≤ c.g(n) for all n ≥ no
where c = 6 and no = 1

f(n) = O(1) Constant Time Complexity

In the above two examples, we have solved the same problem using two different methods to make you understand that multiple algorithms are present to solve one particular problem. Here the first approach is giving us time complexity O(n) and the second approach is giving us time complexity O(1) so we will use the second solution as constant time complexity is much faster than linear time complexity. 

What is the time complexity of the below function?

void fun(int n){
  int i, j;
  for(i = 1; i <= n/3; i++){    //Loop 1
     for(j = 1; j <= n; j+=4){  //Loop 2
         cout<<"Hello";
     }
  }
}

Answer:

Calculation of Time complexity:

For Loop 1:Loop is running from i = 1 to i = n/3 and incremented by one

unit each time.

Iteration 1: i = 1

Iteration 2: i = 2

Iteration 3: i = 3

          .

          .

          .

Iteration k: i = n/3 = k ≈ O(n)

Time Complexity = O(n)

For Loop 2: Loop is running from j = 1 to j = n and incremented by four

unit each time.

Iteration 1: j = 1
Iteration 2: j = 1 + 4
Iteration 3: j = 1 + 4 + 4 = 1 + 2*4
          .
          .
          .
Iteration k: j = n = 1 + (k - 1)*4
      n = 1 + (k - 1)*4
    n-1 = (k - 1)*4
(n-1)/4 = (k -1)
(n-1)/4 + 1 = k ≈ O(n)
Time Complexity = O(n)      

Total Time Complexity = O(n) x O(n) = O(n^2)

Time Complexities of Common Programming Conditions:

Loops: Normal loops usually execute for n number of times where n is the size of input present.

for(int i = 0; i < n; i++){
    //statements
}

• The above loop executes n times.
• Time Complexity: O(n)

Nested Loops: One loop run inside another loop and we can multiply the running time of both loops to get the total time.

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++)
        //statements
}

• The outer loop executes n times and the inner loop also executes n times.
• Time Complexity: O(nxn) = O(n^2)

Consecutive statements: Series of statements and conditions are present inside a function and to get the total running time of the function we sum the time taken by each individual condition.

int n = 10;                // 1 time
int sum = 0;               //1 time

for(int i = 1; i <= n; i++){
   //statements           //n times
}

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++)
        //statements       //n^2 times
}

• The first two lines of code will take constant time to execute, the single for loop statement will execute n times and the nested for loops will execute n^2 times. 
• Time Complexity: O(n^2 + n + 2) = O(n^2)

If-then-else statement: Usually taken constant time but if nested loops are present then we have to include their running time as well.

if(n == 0){               // ---> 1 time    

  //statement            // ---> 1 time
}
else{
   for(int i = 1; i <= n; i++){
       //statement       // ---> n times
   }
}

• For if part it will take constant time (1 + 1 = O(1)) and for else part it will take constant time for condition checking and statement will execute n times (1 + n = O(n)).
• Time Complexity: O(1) + O(n) = O(n)

Logarithmic Complexity: Logarithmic time complexity is achieved when the problem size is cut down by a fraction. log2(n) - Logarithmic equation tells us how many times 2 has been multiplied by itself in order to obtain value n.

//Example of Logarithmic growth
while(i <= n){
   //statement
   i = i*2;
}

• Time Complexity: O(log2n) 

I hope you found this post useful, please share your valuable feedback in the comment section below and share the post with other so we can keep on providing more such valuable content.(alert-success)

C++ Program to Add Two Numbers.

Adding two numbers in C++ programming is a very basic beginner-level question and one can easily write the code by following the below instructions. 

Instruction:

• Declare two integer-type variables num1 and num2.
• Take two integer-type input variables from the user which we are going to store in num1 and num2.
• Declare another integer-type variable sum and initialize the variable with 0.
• Add two variables num1 and num2 and store the answer in the sum variable.
• Print the value present in the sum variable.

C++ Code to Add Two Integer Type Numbers.

#include<iostream>
using namespace std;

int main(){

    int num1, num2;
    
    cout<<"Enter the first number: ";
    cin>>num1;
    
    cout<<"\nEnter the second number: ";
    cin>>num2;

    int sum = 0;
    sum = num1 + num2;
    //Print sum 
    cout<<"Sum of two numbers: "<<sum;
    
    return 0;
}

Output:

Enter the first number: 10
Enter the second number: 5
Sum of two numbers: 15

Note: For this example, we are using an integer-type variable but you can change your change the data type of your variables based on the requirement like you can use float-type variables to add decimal values.(alert-success)

C++ Code to Add Two Float Type Numbers.

#include<iostream>
using namespace std;

int main(){

    float num1, num2;
    
    cout<<"Enter the first number: ";
    cin>>num1;
    
    cout<<"\nEnter the second number: ";
    cin>>num2;

    float sum = 0;
    sum = num1 + num2;
    //Print sum 
    cout<<"Sum of two numbers: "<<sum;
    
    return 0;
}

Output:

Enter the first number: 3.4
Enter the second number: 5.3
Sum of two numbers: 8.7

I hope you found this post useful, please write your comments below if you have any questions or feedback related to this topic.

Find Minimum Sum of Two Number Formed from Splitting Four Digit Number.

Given a four-digit positive integer say num, split the given integer to form two new numbers say num1 and num2. All the digits present in num should be used and leading zeros are allowed for the formation of new numbers. Return the minimum possible sum of new numbers num1 and num2.

Example 1:

Input: num = 2832
Output: 51

Explanation: 
Some possible pairs of numbers [num1, num2]:
[2, 832] = 2 + 832 = 834
[28, 32] = 28 + 32 = 60
[283, 2] = 283 + 2 = 285
[23, 28] = 23 + 28 = 51
etc.
The minimum possible sum of new numbers that can be obtained is [23, 28] = 23 + 28 = 51

Example 2:

Input: num = 5008
Output: 13

Explanation: 
Some possible pairs of numbers [num1, num2]:
[00, 58] = 0 + 58 = 58
[00, 85] = 0 + 85 = 85
[05, 08] = 5 + 8 = 13
[50, 08] = 50 + 8 = 58
etc.
The minimum possible sum of new numbers that can be obtained is [05, 08] = 5 + 8 = 13

Approach 1: Using Sorting.

To solve this problem we do not need to generate all possible combinations of numbers and the length of num1 and num2 is going to be equal in all ideal cases. For creating the two smallest numbers that give you the minimum sum, the smaller digits should appear at the most significant position.

Below are the steps to solve this:

1. Convert the given 4-digit number into an array of digits.

2. Sort the array into increasing order.

3. Traverse the array from 0 to size and create two numbers:

• num1 is going to be formed by digits present at odd positions in the array.
• num2 is going to be formed by digits present at even positions in the array.

4. Return the sum of both digits (num1 + num2).

Below is the Code Implementation:

/*C++ Code for Find Minimum Sum of Two Number Formed 
from Splitting Four Digit Number.*/
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int minimumSum(int num){
    int num1 = 0, num2 = 0;
    int ans = 0;
    //using vector instead of array
    vector<int> vnum;
    //breaking 4 digit number and storing 
    //each digit into integer array
    while(num){
        int rem = num%10;
        vnum.push_back(rem);
        num = num/10;
    }
    //sorting the created list in ascending order
    sort(vnum.begin(), vnum.end());
    //forming num1 and num2
    for(int i = 0; i < vnum.size(); i++){
        if(i % 2 == 0)
           num1 = num1*10 + vnum[i];
        else
           num2 = num2*10 + vnum[i];   
    }
    return num1 + num2;
}

int main(){
    int num = 5008;
    //function call
    cout<<minimumSum(num);
}

Output:

13

• Time Complexity: O(nlogn) because we also have to perform sorting.
• Space Complexity: O(n) where n is the number of digits present.

Approach 2: Using String.

The logic of this approach is almost the same as the previous one but the only benefit is that you don't have to deal with the step of creating an array of digits.

Below are the steps to solve this problem:

1. Convert the given number into a string.

2. Sort the created string in ascending order.

3. Traverse the sorted string from 0 to size and create two numbers:

• num1 is going to be formed by digits present at odd positions in the string.
• num2 is going to be formed by digits present at even positions in the string.

4. Return the sum of both numbers (num1 + num2).

Below is the Code Implementation:

/*C++ Code for Find Minimum Sum of Two Number Formed 
from Splitting Four Digit Number.*/
#include<iostream>
#include<algorithm>
using namespace std;

int minimumSum(int num){
    int num1 = 0, num2 = 0;
    int ans = 0;
    //converting number to string
    string str = to_string(num);
    //sorting the convert string in ascending order
    sort(str.begin(), str.end());
    //forming num1 and num2
    for(int i = 0; i < str.size(); i++){
        if(i % 2 == 0)
           num1 = num1*10 + (str[i] - '0');
        else
           num2 = num2*10 + (str[i] - '0');   
    }
    return num1 + num2;
}

int main(){
    int num = 5008;
    //function call
    cout<<minimumSum(num);
}

Output:

13

• Time Complexity: (nlogn)
• Space Complexity: O(n)

I hope you found this post useful, please write your comments below if you want to give us any feedback to improve our content.

Sliding Window Algorithm with Example

The sliding Window Algorithm helps us solve many simple and complex coding problems with an optimized approach and lesser time complexity. In most cases, we use the sliding window algorithm to reduce the use of nested loops and the repetitive work that we do while solving any problem. 

Why it is called Sliding Window Algorithm?

When we solve problems using this Sliding Window algorithm we try to create or find fixed-size or variable-size windows (here window is nothing but a subarray or substring) which satisfies the given condition of the problem and then we keep sliding the window by one unit to cover next subarrays. 

We can easily find the required window (subarray) using two nested loops but the sliding window algorithm helps us find all possible windows by using a single loop and here now it helps us reduce our time complexity. The name of this algorithm is quite interesting and when we start visualizing the solution using this algorithm then everyone gets satisfied with the name of this algorithm. 

When should we use Sliding Window Algorithm?

Whenever we want to use some algorithm to solve any particular problem we should always be trying to find some pattern in the given question like when we want to apply a binary search algorithm then we try to check whether the given array is sorted or not. 

There are a few points that you can check for before using the sliding window algorithm:

• There should be some discussion related to subarray or substring in the given problem.
• There should be some discussion related to finding the largest, smallest, maximum, minimum, or any count.
• The problem might give us a window size denoting with variable k but if the window size is not given then it means we need to find the window size based on the given conditions.

Types of Sliding Windows.

We can solve several varieties of coding problems using the sliding window algorithm but more or less we can divide them into two different categories.

• Fixed Size Sliding Window: In this type, the size of the window (subarray) is static for the entire duration of the program and already given in the problem. 
• Variable Size Sliding Window: In this type, the size of the window (subarray) is dynamic and keeps on changing for the entire duration of the program and we need to calculate the required largest or smallest window size.  

Example of Fixed-size sliding window. 

Given an array of integers of size n, find the minimum sum of the subarray of size k. 

Example 1:

Input: arr[] = {2, 3, 5, 4, 9, 7, 1}  k = 3
Output: 10

Explanation: 
Sum of all possible subarrays of size 3
{2, 3, 5} = 2+3+5 = 10
{3, 5, 4} = 3+5+4 = 12
{5, 4, 9} = 5+4+9 = 18
{4, 9, 7} = 4+9+7 = 20
{9, 7, 1} = 9+7+1 = 17 
The minimum sum we get by adding the subarray {2, 3, 5} of size 3.

Example 2:

Input: arr[] = {5, -3, 2, 8, 4, 1} k = 2
Output: -1

Explanation:
The minimum sum we get by adding the subarray {-3, 2} of size 2

We can easily solve this problem using a brute force approach by running two nested loops for calculating the sum of all possible subarrays of size k and returning the minimum sum out of all possible. Time Complexity for this approach is O(n*k) where n is the number of elements and k is the size of the subarray.

Below is the code for the brute force approach:

//C++ Code for minimum sum of subarray of size k (O(n*k) solution)
#include<iostream>
using namespace std;

int minSubarraySum(int arr[], int n, int k){

    int minSum = INT_MAX;

    for(int i = 0; i < n-k; i++){
        int sum = 0;
        for(int j = i; j < i+k; j++){
            sum += arr[j];
        }
        minSum = min(minSum, sum);
    }
    return minSum;
}
int main(){
    int arr[] = {5, -3, 2, 8, 4, 1};
    //size of given array
    int n = sizeof(arr)/sizeof(arr[0]);
    //size of subarray
    int k = 3;
    cout<<minSubarraySum(arr, n, k);
}

Output:

4

• Time Complexity: O(n*k)
• Space Complexity: O(1)

Now let's check that can we apply the sliding window algorithm to the above problem? As we discussed above for applying the sliding window algorithm, we can check for certain conditions like the problem is saying something about subarray, the window size k is given and we need to find the minimum subarray sum. It means the given problem satisfies all our conditions so we can think about applying the fixed-size sliding window approach here.

Sliding Window Algorithm: For applying the sliding window approach to this kind of problem where the window size is fixed we first need to compute the sum of the first k elements of the array and it will give us one possible answer that we can store in a variable window_sum. Now to slide the window by one unit to the right we need to remove the calculation of the first element of the previous window and add the last element of the current window. 

We first calculate the initial window_sum starting from index 0 to 0+k and then we store it as a sum of our current window (current_sum) and we update our answer variable min_sum if current_sum is lesser than min_sum (initially min_sum  = INT_MAX). 

• current_sum = 4
• min_sum = 4

Now to get the sum of the next current_window we have to remove the first element from window_sum and add the last element of the current_window. Every time update the value of min_sum if the value of current_sum is smaller than min_sum.

• current_sum = 7
• min_sum = 4

Similarly, again to get the sum of the next current_window we have to remove the first (arr[1]) element from window_sum and add the last element (arr[4]) of the current_window.

• current_sum = 14
• min_sum = 4

• current_sum = 13
• min_sum = 4

Below is the code implementation of a fixed-size sliding window:

//C++ Code for minmum sum of subarray of size k (Sliding Window Approach)

#include<iostream>
using namespace std;

//function to find minmum sum of subarray of size k
int minSubarraySum(int arr[], int n, int k){
    //variable to store maxSum
    int minSum = INT_MAX;
    //variable to calculate window size
    int i = 0, j = 0;
    int window_sum = 0;
    
    while(j < n){
        window_sum = window_sum + arr[j];
        //Window size is less than k
        if(j-i+1 < k){
            j++;
        }
        /*we get one of the possible answer, store it
        and remove the calculation of ith element and 
        slide the window by one unit*/
        else if(j-i+1 == k){
            minSum = min(minSum, window_sum);
            window_sum = window_sum - arr[i];
            i++;
            j++;
        }
    }
    return minSum;
}
int main(){
    int arr[] = {5, -3, 2, 8, 4, 1};
    //size of given array
    int n = sizeof(arr)/sizeof(arr[0]);
    //size of subarray
    int k = 3;
    cout<<minSubarraySum(arr, n, k);
}

Output:

4

• Time Complexity: O(n)
• Space Complexity: O(1)

After solving many fixed-size sliding window problems, I have observed a general pattern for this algorithm that you can also follow while solving problems.

Fixed-size Sliding Window General Format

while(j < n)
{
    /*
    In this step, we need to do calculation for 
    window formation base on given condition.
    */
    if(current_window_size < k)
       /*
       Increase the window size as it is 
       not equal to given window size k
       */
       j++;
    else if(current_window_size == k)
    {
        /*
        We get our one possible answer so store
        them in some answer variable 
        */
        /*
        Remove the calculation of ith index to 
        slide the window one unit right
        */
        /*
        Increment the vlaue of i and  j to maintain
        the window size 
        i++;
        j++;
        */
    }   
}
return answer;

Example of Variable-size sliding window. 

Given an integer array of size n, find the length of the longest subarray having a sum equal to k.

Example 1:

Input: arr[] = {8, 7, 3, 6, 1, 5}  k = 15
Output: 4

Explanation: 
The longest subarray with sum 15 is {3, 6, 1, 5}

Example 2:

Input: arr[] = {1, 2, 3} k = 3
Output: 2

Explanation:

The longest subarray with sum 5 is {1, 2}

Input: arr[] = {-5, 7, -14, 3, 4, 12} k = -5

Output: 5

Brute Force: We find the sum of all possible subarrays and return the length of the longest subarray having a sum equal to k. The time complexity of this approach is O(n^2) as we are calculating the sum of all subarrays.

Below is the C++ Code Implementation.

#include<iostream>
using namespace std;

//function to find longest subarray of sum k
int longestSubarraySum(int arr[], int n, int k){
    //variable to store answer
    int maxlen = 0;

    for(int i = 0; i < n; i++){
        int sum = 0;
        for(int j = i; j < n; j++){
            sum += arr[j];

            if(sum == k){
                maxlen = max(maxlen, j-i+1);
            }
        }
    }
    return maxlen;
}

int main(){
    int arr[] = {10, 5, 2, 7, 1, 9};
    //given array size
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 15;
    cout<<longestSubarraySum(arr, n, k);
}

Output:

4

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Let's check if can we apply the sliding window algorithm to this problem. If we go through the problem description we observe that it tells us to find subarrays for a given condition and return the longest one out of them. Here the size of the window is not fixed as we need to find the longest possible subarray. Now we can think of variable-size sliding windows.

Sliding Window Algorithm: (This approach will not work for arrays containing negative numbers).

In this problem where the Window size is not fixed, we will get three conditions to handle:

• When the sum is less than k, we need to add more variables and increment j.
• When the sum is equal to k, we get one possible answer and store the length of the current subarray in some max variable.
• When the sum is greater than k, then subtract the ith elements until the sum becomes less than k.

Below is the C++ Code Implementation of the variable size sliding window approach.

#include<iostream>
using namespace std;

//function to find longest subarray of sum k (Sliding Window approach)
int longestSubarraySum(int arr[], int n, int k){
    //variable to store answer
    int i = 0, j = 0, sum = 0;
    int maxlen = INT_MIN;

    while(j < n){
        sum += arr[j];
        //sum is less than k
        if(sum < k){
            j++;
        }
        //sum is equal to k
        else if(sum == k){
            maxlen = max(maxlen, j-i+1);
            j++;
        }
        //sum is greater than k
        else if(sum > k){
            //remove ith elements until sum 
            //again become equal or less than k
            while(sum > k){
                sum -= arr[i];
                i++;
            }
            if(sum == k){
                maxlen = max(maxlen, j-i+1);
            }
            j++;
        }
    }
    return maxlen;
}

int main(){
    int arr[] = {10, 5, 2, 7, 1, 9};
    //given array size
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 15;
    cout<<longestSubarraySum(arr, n, k);
}

Output:

4

• Time Complexity: O(n)
• Space Complexity: O(1)

After solving many variable-size sliding window problems, I have observed a general pattern for this algorithm that you can also follow while solving problems.

Variable-size Sliding Window General Format

while(j < n)
{
    /*
    we need to do [calculation] for window 
    formation base on given condition.
    */
    if(calculation < k)
    {
       /*
       Increase the window size as calculation
       is not matching with given condition k
       */
       j++;
    }   
    else if(calculation == k)
    {
        /*
        we get our one possible answer, store them in some variable
        Increment the value of j.
        */
    }
    else if(calculation > k)
    {
        /*
        start removing ith elements to from calculation
        so it again meet our condition calculation == k
        */
        while(condition > k)
        {
            //remove calculation for i
            i++;
        }
        //check if we are meeting the given condition
        j++;
    }   
}
return answer;

Static sliding windows and Dynamic sliding windows, both are totally two different cases of sliding window problems and both should be handled differently.

Sliding Window Problems:

• Program to Find the K Beauty of a number.
• Find Maximum Sum of a Subarray of size K
• Program to Count Subarrays with K Odd Numbers

Find Maximum Sum of a Subarray of size K.

Given an integer array of size n and a number k, find the maximum sum of a subarray of size k. 

Example 1:

Input: arr[] = {2, 3, 5, 2, 9, 7, 1}  k = 3
Output: 18

Explanation: 
Sum of all possible subarrays of size 3
{2, 3, 5} = 2+3+5 = 10
{3, 5, 2} = 3+5+2 = 10
{5, 2, 9} = 5+2+9 = 16
{2, 9, 7} = 2+9+7 = 18
{9, 7, 1} = 9+7+1 = 17 
The maximum sum we get by adding the subarray {2, 9, 7} of size 3.

Example 2:

Input: arr[] = {5, -3, 2, 8, 4} k = 2
Output: 12

Explanation:
The maximum sum we get by adding the subarray {8, 4} of size 2

Approach 1: Brute Force

We can run two nested loops to calculate the sum of possible subarrays of the given size k and return the maximum of all sums. The time complexity of this approach will be O(n*k) where n is the number of elements in the array and k is the size of the subarray. 

C++ Code for finding the maximum sum of a subarray of size k.

//C++ Code for maximum sum of subarray of size k 
#include<iostream>
using namespace std;

int maxSubarraySum(int arr[], int n, int k){

    int maxSum = INT_MIN;

    for(int i = 0; i < n-k; i++){
        int sum = 0;
        for(int j = i; j < i+k; j++){
            sum += arr[j];
        }
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}
int main(){
    int arr[] = {2, 3, 5, 2, 9, 7, 1};
    //size of given array
    int n = sizeof(arr)/sizeof(arr[0]);
    //size of subarray
    int k = 3;
    cout<<maxSubarraySum(arr, n, k);
}

Output:

18

• Time Complexity: O(n*k)
• Space Complexity: O(1)

Our brute force approach will work fine for a smaller value of k but as soon as the k value goes high our time complexity will also increase. We have to think of an optimized approach and we need to check that is there any repetitive work we are doing? 

 

Approach 2: Fixed-size Sliding Window (Optimized approach).

If we observe carefully we notice that the time taken to calculate the sum of each subarray is O(k) but we can compute this calculation in O(1) time complexity for all the subarray except the first subarray of size k. 

Here we are going to use the fixed-size sliding window concept to optimize our solution where the size of our Window is given as k. First, we are going to calculate the sum of our first subarray (window) of size k, and to get the sum of the next subarray we are going to add the next element in the current sum and remove the first element of the last window. 

C++ Code for finding the maximum sum of a subarray of size k using the Sliding Window Approach.

//C++ Code for maximum sum of subarray of size k (optimized)

#include<iostream>
using namespace std;

//function to find maximum sum of subarray of size k
int maxSubarraySum(int arr[], int n, int k){
    //variable to store maxSum
    int maxSum = INT_MIN;
    //variable to calculate window size
    int i = 0, j = 0;
    int sum = 0;
    
    while(j < n){
        sum = sum + arr[j];
        //Window size is less than k
        if(j-i+1 < k){
            j++;
        }
        /*we get one of the possible answer, store it
        and remove the calculation of ith element and 
        slide the window by one unit*/
        else if(j-i+1 == k){
            maxSum = max(maxSum, sum);
            sum = sum - arr[i];
            i++;
            j++;
        }
    }
    return maxSum;
}
int main(){
    int arr[] = {2, 3, 5, 2, 9, 7, 1};
    //size of given array
    int n = sizeof(arr)/sizeof(arr[0]);
    //size of subarray
    int k = 3;
    cout<<maxSubarraySum(arr, n, k);
}

Output:

18

• Time Complexity: O(n)
• Space Complexity: O(1)