0

I am not getting why is there a segmentation fault occurring. Kindly help me resolve it. If I am changing the size of array to some lesser value it is executing. Is there any limit on array size but the question demands that size equal to 1000000. What should I do apart from using vector.

Link to question: https://practice.geeksforgeeks.org/problems/maximum-rectangular-area-in-a-histogram-1587115620/1#

#include<bits/stdc++.h>
using namespace std;

class Solution
{
    public:
    //Function to find largest rectangular area possible in a given histogram.
    long long arrN[1000000]={0};
    long long arrP[1000000]={0};
    
    void prevS(long long arr1[],int n)
    {   stack<long long> s;
        for(int i=0;i<n;i++)
        {
            if(s.empty()){s.push(i); arrP[i]=-1;}
            else
            {
                while(!s.empty() && arr1[s.top()]>=arr1[i])
                {
                    s.pop();
                }
                if(s.empty()) arrP[i]=-1;
                else
                arrP[i]=s.top();
                s.push(i);
            }
        }
       
    }
    void nexS(long long arr1[],int n)
    {   stack<long long> s;
        
        for(int i=n-1;i>=0;i--)
        {
            if(s.empty()){s.push(i); arrN[i]=n;}
            else
            {
                while(!s.empty() && arr1[s.top()]>=arr1[i])
                {
                    s.pop();
                }
                if(s.empty()) arrN[i]=n;
                else
                arrN[i]=s.top();
                s.push(i);
            }
        }
        
    }
    long long getMaxArea(long long arr[], int n)
    {
        // Your code here
        prevS(arr,n);
        long long* pre=arrP;
        nexS(arr,n);
        long long* nex=arrN;
        long long ans=INT_MIN;
        for(int i=0;i<n;i++)
        {
            ans=max(ans,arr[i]*(nex[i]-pre[i]-1));
        }
        return ans;
    }
};

int main()
{
long long t;
cin>>t;
while(t--)
{
int n;
cin>>n;
long long arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
Solution ob;
court<<ob.getMaxArea(arr,n)<<endl;
}
return 0;
}

Input: 
1
7
6 2 5 4 5 1 6
Ruhan Saini
  • 17
  • 4
  • Important side note: https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h – Jabberwocky Feb 07 '22 at 07:15
  • What is your input? – Jabberwocky Feb 07 '22 at 07:16
  • @Jabberwocky is that the issue? – Ruhan Saini Feb 07 '22 at 07:17
  • @Jabberwocky 1 7 6 2 5 4 5 1 6 – Ruhan Saini Feb 07 '22 at 07:17
  • No, that's not the issue. But there is at least one issue: both `return arr;` statements: you return the address of the local variable `arr`, but that variable ceases to exist as soon as the function has finished execution. – Jabberwocky Feb 07 '22 at 07:19
  • @Jabberwocky Ok, I was doubtful about this part that after execution of that block memory ceases. I thought since I returned the address it might be existing. – Ruhan Saini Feb 07 '22 at 07:21
  • Use a `std::vector` instead. – WhozCraig Feb 07 '22 at 07:22
  • 1
    Your code consistently uses Variable Length Array, when it is not officially supported in C++. Furthermore, you return the addresses of those **local** arrays. If you want to use C++, use vectors instead, they will handle allocation and deallocation for you. And if you insists in using arrays, then use C (or C-ish constructs) but only return **dynamic** (allocated with `malloc` if C or `new` if C++) from functions. You should learn to write *correct* C++ code instead playing with things like `bits/stdc++.h` which are expected to allow you to code faster but only learn you to produce ugly code. – Serge Ballesta Feb 07 '22 at 07:23
  • @SergeBallesta Kindly tell me how to write proper code. I have learnt that only till now. I would be really grateful. – Ruhan Saini Feb 07 '22 at 07:28
  • Tomes have been written for that expressed purpose; it's not something one can 'teach' in a comment stream on SO, I'm afraid. It takes the same thing anything else does to achieve success; a *lot* of research, a *lot* of work, a *lot* of *failing*, and eventually, hopefully, some success. Been doing this for 30 years and I still learn ways to refine my craft near-every-day. – WhozCraig Feb 07 '22 at 07:31
  • @WhozCraig Thanks for your response my point was just tell me the flaws that you find so that I could improve. Because what happens is ugly code sort of words demotivate you when you are trying your best. If the flaws are directed along with then it really does the needful. I hope you understand. Thanks. – Ruhan Saini Feb 07 '22 at 07:34
  • @RuhanSaini: I did not want to be offensive. C++ comes with a nice standard library, with containers and algorithms that allow you to easily write robust code. Unless when writing low level library modules, you should seldom use raw arrays but `std::vector`. For more general advices, you could have a look at the [c++] tag page which contains a FAQ and a list of good books. – Serge Ballesta Feb 07 '22 at 07:38
  • @Jabberwocky Please tell if you could figure out. Why these lines are giving segmentation fault; long long arrN[1000000]={0}; long long arrP[1000000]={0}; if I remove one 0 it is working fine. – Ruhan Saini Feb 07 '22 at 07:39
  • @SergeBallesta I do certainly understand and I was not taking it in offensive way. Actually my perspective was to learn. And I do appreciate your straight forward answer without sugar coating. I will definitely try improving taking up you advice thankyou:) – Ruhan Saini Feb 07 '22 at 07:41
  • 1
    @RuhanSaini: Undefined Behaviour is close to hell because *sometimes it works and sometimes it breaks* with no evident reason. The cause of the segfault that you experience is that returning the address of a local variable from a function is UB. You simply **cannot** return an array from a function! That is the reason why I advised you to use `std::vector` instead of your arrays. – Serge Ballesta Feb 07 '22 at 07:42
  • `long long arrN[1000000];` local variables are stored on the stack which is typically is limited to typically 8MB. So, no you cannot have very long local arrays. – Jabberwocky Feb 07 '22 at 07:43
  • Yes I understood your point, I should use vector instead. Just the thing was I was also trying to explore the cause of failure. I thought that would help enhance the concept and knowing things better. LIke I came to know now. Kindly help me with one more thing please. long long arrN[1000000]={0}; long long arrP[1000000]={0}; why is this giving me segmentation fault. I am declaring them as global. If I remove one 0 it works fine. – Ruhan Saini Feb 07 '22 at 07:45
  • @Jabberwocky but the question is demanding so because my code is failing on large test case where index exceeds that. The limit for n there is 1000000 but in declaration if I am crossing 100001 then it is giving error. – Ruhan Saini Feb 07 '22 at 07:48
  • @RuhanSaini _" I am declaring them as global"_: no, you're not. At least not in the code you show in the question. – Jabberwocky Feb 07 '22 at 07:52
  • @Jabberwocky no not in this code in new code I have written. – Ruhan Saini Feb 07 '22 at 07:56
  • @RuhanSaini without seeing your code we can't help much. Maybe syou should ask a new question with you new code. – Jabberwocky Feb 07 '22 at 08:02
  • @Jabberwocky I have edited it and updated the question as well. Really grateful for your help. Thanks! – Ruhan Saini Feb 07 '22 at 08:04
  • @RuhanSaini -- The website where you got this question from is notorious for bad C++ code, and encouraging bad C++ coding habits. The second thing is that, even for that website and others that ask questions like this, they assume you know the computer language well-enough to never make simple mistakes, like returning dangling pointers, etc. Those sites are not there to teach C++, only to ask random algorithm questions, with the assumption you know the language well enough to answer their questions. – PaulMcKenzie Feb 07 '22 at 09:24

0 Answers0