Total number of sub-arrays whose sum value is greater than or equal to K

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:

  1. 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.

  2. There are

    number of sub-arrays in an array.

  3. 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:

  1. 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.

  2. The idea is to use Sliding Window Technique.

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

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

  5. Now whenever we add an element, there arises two possible cases –

    1. 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.

    2. 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.

    3. 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″]

Space Complexity: O(1)
Previous post Interesting Array
Next post Find the Leader

Leave a Reply

Your email address will not be published. Required fields are marked *