#### CONCEPTS USED:

Sliding Window Technique

#### DIFFICULTY LEVEL:

Medium

#### PROBLEM STATEMENT`(`

SIMPLIFIED`)`

:

Given an array of

`N`

elements, print the total number of sub-arrays whose sum value is greater than or equal to`K`

.

**See original problem statement here**

#### For Example:

```
Input : N = 5, K = 3
A[] = [1 2 3 4 5]
Output : 13
Explanation :
There are 13 sub-arrays whose sum is greater than or equal to 3
(3), (4), (5)
(1 2), (2 3), (3 4), (4 5),
(1 2 3), (2 3 4), (3 4 5),
(1 2 3 4), (2 3 4 5), (1 2 3 4 5)
The only two sub-arrays whose sum is less than 3 are (1) and (2).
```

#### SOLVING APPROACH:

#### BRUTE FORCE METHOD:

A simple brute force solution is to generate all the sub-arrays and check whether their sum is greater than or equal to

`K`

or not by referring the best online programming courses.There are

number of sub-arrays in an array.

`Time Complexity`

of this approach would be quadratic i.e.`O(N^2)`

.

NOTE: If`N <= 10^3`

, it would work fine but for greater values of`N`

, it would result in TLE`(`

`Time Limit Exceeded`

`)`

.

#### SOLUTIONS:

[TABS_R id=471]

##### Time Complexity: `O(N^2)`

##### Space Complexity: `O(1)`

#### EFFICIENT METHOD:

In order to find the total no. of subarrays that have sum value greater than equal to

`K`

, instead we can find total subarrays that have value less than`K`

, the difference between total no of subarrays and our calculated subarrays would be our`answer`

.The idea is to use

`Sliding Window Technique`

.We make use of two pointers that point to the starting and the ending of this window,

`start`

and`end`

.Initially both the pointers point to the beginning of the array i.e. 0

^{th}index.Now whenever we add an element, there arises two possible cases –

If the sum is less than

`K`

, we will increment our`end`

pointer by`1`

and the value of (`end`

`-`

`start`

) will give us the current count of subarrays with value less than`K`

. Because there are as many subarrays as the length of the window.If the sum is greater than or equal to

`K`

, we need to subtract the starting element from the sum so that it becomes less than`K`

again and increment our`start`

pointer by`1`

.Keep repeating steps

`1`

and`2`

until we reach the end of the array.

#### ILLUSTRATION:

```
A[] = [1, 2, 3, 4, 5]
K = 3
start = 0
end = 0
sum = A[start] = 1
count = 0
(start < n) and (end < n) and (sum < K)
end ++ => end = 1
count = count + (end - start) = 0 + 1 - 0 = 1
sum = sum + A[end] = 1 + 2 = 3
start = 0
(start < n) and (end < n) and (sum >= K)
sum = sum - A[start] = 3 - 1 = 2
start ++ => start = 1
end = 1
(start < n) and (end < n) and (sum < K)
end ++ => end = 2
count = count + (end - start) = 1 + 2 - 1 = 2
sum = sum + A[end] = 2 + 3 = 5
start = 1
(start < n) and (end < n) and (sum >= K)
sum = sum - A[start] = 5 - 2 = 3
start ++ => start = 2
end = 2
(start < n) and (end < n) and (sum >= K)
sum = sum - A[start] = 3 - 3 = 0
start ++ => start = 3
end = 2
(start < n) and (end < n) and (sum >= K)
sum = sum - A[start] = 0 - 4 = -4
start ++ => start = 4
end = 2
(start < n) and (end < n) and (sum >= K)
sum = sum - A[start] = -4 - 5 = -9
start ++ => start = 5
end = 2
Since (start >= n), we will stop here and count = 2 is the number of subarrays
which have value less than K = 3
Count of subarrays with sum greater than or equal to K can be calculated by subtracting this calculated count by total number of sub-arrays.
```

#### SOLUTIONS:

[TABS_R id=472]

[forminator_quiz id=”488″]