Find the number of subarrays in an array which don't contain the largest element of the array in them ?

Question

Expected Time Complexity : O(N) , where 'N'  is the size of the array .

1<=A[i]<=1000000

1<=N<=100000

Example :

100 200 400

Output : 3 ( (100),(200),(100,200) are the subarrays which don't contain the maximum element in them)

Note :

1)Algorithm-explanation is must .

2)Adding code is optional .

3)Use Format option while adding code

Answer 1

With every increase in length of array, number of subarray increases by n

example arr = {3,2,5} total Possible subarray is 1 + 2 + 3 = 6;

example arr = {1,2,3,2} total Possible subarray is 1 + 2 + 3 + 4 = 10;

so in this question find the count of all consecutive elements that doesnot containg maxNumber, and return the total number of subarrays.

Probably this is it, let me know if logic is wrong


#include<bits/stdc++.h>

using namespace std;

int32_t main()

{

    vector<int> TC1 = {1,2,3,9};   // output  = 6    {1,2,3, 12 , 23, 123}

    vector<int> TC2 = {1,9,3,9};   // output = 2     {1,3}

    vector<int> TC3 = {1,9,3,8};   // output = 4     {1,3,8,38}

    vector<int> TC4 = {9};         // output = 0     {}


    // CODE BEGINS

    vector<int> a = TC1;

    int maxElement = *max_element(a.begin() , a.end());


    int ans = 0,

        ct = 0;

    for(auto i : a)

        {

            if(i != maxElement)

                    ++ct,

                    ans += ct;

            else

                ct = 0;

        }

    cout<<"ans is "<<ans;

}

Comments

Brilliant , the original version of this problem asked to find the number of sub-arrays which do contain the largest element :-)
I hope solution for this helps in that one too :-)