Given an array of n integers, find the no of subarrays whose minimal and maximum elements are the same. A subarray is defined as a non-empty sequence of consecutive elements.
Examples:
Input: 2 3 1 1
Output: 5
Explanation: The subarrays are (2), (3), (1), (1) and (1, 1)Input: 2 4 5 3 3 3
Output: 9
Explanation: The subarrays are (2), (4), (5), (3), (3, 3), (3, 3, 3), (3), (3, 3) and (3)
The first thing to observe is that only those subarrays whose all elements are same will have the same minimum and maximum. Having different elements clearly means different minimum and maximum. Hence, we just need to calculate the number of continuous same elements (say d), then by combinations’ formula we get the no of subarrays to be –
No of subarrays possible with d elements = (d * (d+1) / 2)
where d is a number of continuous same elements.
We traverse from 1-n and then from I+1 to n and then find the number of continuous same elements and then add to the result the no subarrays possible.
Below is the implementation of the above approach:
C++
// CPP program to count number of subarrays // having same minimum and maximum. #include <bits/stdc++.h> using namespace std; // calculate the no of contiguous subarrays // which has same minimum and maximum int calculate(int a[], int n) { // stores the answer int ans = 0; // loop to traverse from 0-n for (int i = 0; i < n; i++) { // start checking subarray from next element int r = i + 1; // traverse for finding subarrays for (int j = r; j < n; j++) { // if the elements are same then // we check further and keep a count // of same numbers in 'r' if (a[i] == a[j]) r += 1; else break; } // the no of elements in between r and i // with same elements. int d = r - i; // the no of subarrays that can be formed // between i and r ans += (d * (d + 1) / 2); // again start checking from the next index i = r - 1; } // returns answer return ans; } // driver program to test the above function int main() { int a[] = { 2, 4, 5, 3, 3, 3 }; int n = sizeof(a) / sizeof(a[0]); cout << calculate(a, n); return 0; } |
Java
// Java program to count number of subarrays // having same minimum and maximum. class Subarray { // calculate the no of contiguous subarrays // which has same minimum and maximum static int calculate(int a[], int n) { // stores the answer int ans = 0; // loop to traverse from 0-n for (int i = 0; i < n; i++) { // start checking subarray from // next element int r = i + 1; // traverse for finding subarrays for (int j = r; j < n; j++) { // if the elements are same then // we check further and keep a // count of same numbers in 'r' if (a[i] == a[j]) r += 1; else break; } // the no of elements in between r // and i with same elements. int d = r - i; // the no. of subarrays that can be // formed between i and r ans += (d * (d + 1) / 2); // again start checking from the next // index i = r - 1; } // returns answer return ans; } // Driver program to test above functions public static void main(String[] args) { int a[] = { 2, 4, 5, 3, 3, 3 }; System.out.println(calculate(a, a.length)); } } // This code is contributed by Prerna Saini |
Python3
# Python3 program to count # number of subarrays having # same minimum and maximum. # calculate the no of contiguous # subarrays which has same # minimum and maximum def calculate(a, n): # stores the answer ans = 0; i = 0; # loop to traverse from 0-n while(i < n): # start checking subarray # from next element r = i + 1; # traverse for # finding subarrays for j in range(r, n): # if the elements are same # then we check further # and keep a count of same # numbers in 'r' if (a[i] == a[j]): r = r + 1; else: break; # the no of elements in # between r and i with # same elements. d = r - i; # the no of subarrays that # can be formed between i and r ans = ans + (d * (d + 1) / 2); # again start checking # from the next index i = r - 1; i = i + 1; # returns answer return int(ans); # Driver Code a = [ 2, 4, 5, 3, 3, 3 ]; n = len(a); print(calculate(a, n)); # This code is contributed by mits |
C#
// Program to count number // of subarrays having same // minimum and maximum. using System; class Subarray { // calculate the no of contiguous // subarrays which has the same // minimum and maximum static int calculate(int[] a, int n) { // stores the answer int ans = 0; // loop to traverse from 0-n for (int i = 0; i < n; i++) { // start checking subarray // from next element int r = i + 1; // traverse for finding subarrays for (int j = r; j < n; j++) { // if the elements are same then // we check further and keep a // count of same numbers in 'r' if (a[i] == a[j]) r += 1; else break; } // the no of elements in between // r and i with same elements. int d = r - i; // the no. of subarrays that can // be formed between i and r ans += (d * (d + 1) / 2); // again start checking from // the next index i = r - 1; } // returns answer return ans; } // Driver program public static void Main() { int[] a = { 2, 4, 5, 3, 3, 3 }; Console.WriteLine(calculate(a, a.Length)); } } // This code is contributed by Anant Agarwal. |
PHP
<?php // PHP program to count number // of subarrays having same // minimum and maximum. // calculate the no of contiguous // subarrays which has same minimum // and maximum function calculate($a, $n) { // stores the answer $ans = 0; // loop to traverse from 0-n for ($i = 0; $i < $n; $i++) { // start checking subarray // from next element $r = $i + 1; // traverse for finding subarrays for ($j = $r; $j < $n; $j++) { // if the elements are same // then we check further and // keep a count of same numbers // in 'r' if ($a[$i] == $a[$j]) $r += 1; else break; } // the no of elements in between // r and i with same elements. $d = $r - $i; // the no of subarrays that // can be formed between i and r $ans += ($d * ($d + 1) / 2); // again start checking // from the next index $i = $r - 1; } // returns answer return $ans; } // Driver Code $a = array( 2, 4, 5, 3, 3, 3 ); $n = count($a); echo calculate($a, $n); // This code is contributed by Sam007 ?> |
Javascript
<script> // JavaScript program to count number of subarrays // having same minimum and maximum. // calculate the no of contiguous subarrays // which has same minimum and maximum function calculate(a, n) { // stores the answer let ans = 0; // loop to traverse from 0-n for (let i = 0; i < n; i++) { // start checking subarray from // next element let r = i + 1; // traverse for finding subarrays for (let j = r; j < n; j++) { // if the elements are same then // we check further and keep a // count of same numbers in 'r' if (a[i] == a[j]) r += 1; else break; } // the no of elements in between r // and i with same elements. let d = r - i; // the no. of subarrays that can be // formed between i and r ans += (d * (d + 1) / 2); // again start checking from the next // index i = r - 1; } // returns answer return ans; } // Driver Code let a = [ 2, 4, 5, 3, 3, 3 ]; document.write(calculate(a, a.length)); </script> |
Output
9
Time Complexity: O(n), where n is the size of the given array.
Auxiliary Space: O(1)
This article is contributed by Raja Vikramaditya (Raj). If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
