Count Subarrays with Consecutive elements differing by 1-CodePudding

I am going through this program mentioned here.

Given an array arr[] of N integers. The task is to count the total number of subarrays of the given array such that the difference between the consecutive elements in the subarrays is one. That is, for any index i in the subarrays, arr[i 1] – arr[i] = 1.

Examples:

Input : arr[] = {1, 2, 3}
Output : 3
The subarrays are {1, 2}. {2, 3} and {1, 2, 3}

Input : arr[] = {1, 2, 3, 5, 6, 7}
Output : 6

Efficient Approach: An efficient approach is to observe that in an array of length say K, the total number of subarrays of size greater than 1 = (K)*(K-1)/2. So, the idea is to traverse the array by using two pointers to calculate subarrays with consecutive elements in a window of maximum length and then calculate all subarrays in that window using the above formula. Below is the step-by-step algorithm:

Take two pointers to say fast and slow, for maintaining a window of consecutive elements. Start traversing the array. If elements differ by 1 increment only the fast pointer. Else, calculate the length of the current window between the indexes fast and slow.

My question is about the statement An efficient approach is to observe that in an array of length say K, the total number of subarrays of size greater than 1 = (K)*(K-1)/2 How this formula (K)*(K-1)/2 is derived?

CodePudding user response：

The number of subarrays of size 1 is K.

The number of subarrays of size 2 is K-1. ( We need to select subarrays of size 2, hence we can have pair with the indices (0,1), (1,2), .......(K-1,K). In total we can have K-1 such pairs)

The number of subarrays of size 3 is K-2.

...

The number of subarrays of size K is 1

So, the number of subarrays of size greater than 1 is

= K-1   K-2   K-3  ...... 1
= (K   K-1   K-2   K-3  ...... 1) - K //adding and removing K
= (K(K 1)/2) - K
= K(K-1)/2