## Thursday, February 11, 2016

### Count Strictly Increasing Subarrays

http://www.geeksforgeeks.org/count-strictly-increasing-subarrays/
Given an array of integers, count number of subarrays (of size more than one) that are strictly increasing.
```Input: arr[] = {1, 2, 3, 4}
Output: 6
There are 6 subarrays {1, 2}, {1, 2, 3}, {1, 2, 3, 4}
{2, 3}, {2, 3, 4} and {3, 4}
```
Simple Solution is to generate all possible subarrays, and for every subarray check if subarray is strictly increasing or not. Worst case time complexity of this solution would be O(n3).
Better Solution is to use the fact that if subarray arr[i:j] is not strictly increasing, then subarrays arr[i:j+1], arr[i:j+2], .. arr[i:n-1] cannot be strictly increasing.
`int` `countIncreasing(``int` `arr[], ``int` `n)`
`{`
`    ``// Initialize count of subarrays as 0`
`    ``int` `cnt = 0;`

`    ``// Pick starting point`
`    ``for` `(``int` `i=0; i<n; i++)`
`    ``{`
`        ``// Pick ending point`
`        ``for` `(``int` `j=i+1; j<n; j++)`
`        ``{`
`            ``if` `(arr[j] > arr[j-1])`
`                ``cnt++;`

`            ``// If subarray arr[i..j] is not strictly `
`            ``// increasing, then subarrays after it , i.e., `
`            ``// arr[i..j+1], arr[i..j+2], .... cannot`
`            ``// be strictly increasing`
`            ``else`
`                ``break``;`
`        ``}`
`    ``}`
`    ``return` `cnt;`
`}`
Time complexity of the above solution is O(m) where m is number of subarrays in output
An Efficient Solution can count subarrays in O(n) time. The idea is based on fact that a sorted sunarray of length ‘len’ adds len*(len-1)/2 to result. For example, {10, 20, 30, 40} adds 6 to the result.
`int` `countIncreasing(``int` `arr[], ``int` `n)`
`{`
`    ``int` `cnt = 0;  ``// Initialize result`

`    ``// Initialize length of current increasing`
`    ``// subarray`
`    ``int` `len = 1;`

`    ``// Traverse through the array`
`    ``for` `(``int` `i=0; i < n-1; ++i)`
`    ``{`
`        ``// If arr[i+1] is greater than arr[i],`
`        ``// then increment length`
`        ``if` `(arr[i + 1] > arr[i])`
`            ``len++;`
`            `
`        ``// Else Update count and reset length`
`        ``else`
`        ``{`
`            ``cnt += (((len - 1) * len) / 2);`
`            ``len = 1;`
`        ``}`
`    ``}`
`    `
`    ``// If length is more than 1`
`    ``if` `(len > 1)`
`        ``cnt += (((len - 1) * len) / 2);`

`    ``return` `cnt;`
`}`