Next greater element in the right using 'vector'

Question

Problem statement:

You are given a number n, representing the size of array a.

You are given n numbers, representing elements of array a.

You are required to "next greater element on the right" for all elements of array

Input and output is handled for you.

"Next greater element on the right" of an element x is defined as the first element to right of x having value greater than x.

Note -> If an element does not have any element on it's right side greater than it, consider -1 as it's "next greater element on right"

e.g. for the array [2 5 9 3 1 12 6 8 7]

Next greater for 2 is 5

Next greater for 5 is 9

Next greater for 9 is 12

Next greater for 3 is 12

Next greater for 1 is 12

Next greater for 12 is -1

Next greater for 6 is 8

Next greater for 8 is -1

Next greater for 7 is -1

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

void display(vector<int> a) {
    for(int i=0; i<a.size(); i++) {
        cout << a[i] << endl;
    }
}

vector<int> solve(vector<int> arr) {
    vector<int> v;
    stack<int> st;
    st.push(arr[arr.size()-1]);
    v[arr.size()-1] = -1;
    for(int i=arr.size()-2; i>=0; i--) {
        while(!st.empty() && arr[i]>=st.top()) {
            st.pop();
        }
        if(st.empty()) {
            v[i] = -1;
        }
        else {
            v[i] = st.top();
        }
        st.push(arr[i]);
    }
    return v;
}

int main() {
    int n;
    cin >> n;

    vector<int> arr(n, 0);
    for(int i=0; i<n; i++) {
        cin >> arr[i];
    }
    vector<int> nge(n, 0);
    nge = solve(arr);
    display(nge);
    return 0;
}

This is my code and it gives a segmentation fault. How can I know the error in my code?

In case you didn't know, you're supposed to do the debugging yourself before posting on StackOverflow. — Fareanor, Feb 02 '23 at 12:49
This question's code/phrasing suggests that it came from one of many countless coding challenge/puzzle scam sites. They take advantage of people who want to learn C++ by offering arcane coding puzzles and promising that you don't really need to study and learn C++ with a good textbook for many years, just do a bunch of meaningless coding puzzles. Everyone eventually realizes that these pointless coding puzzles are a waste of time, and there's nothing to be learned from them. But only after spending a lot of time doing them, with nothing to show for it. — Sam Varshavchik, Feb 02 '23 at 13:09
well it's called sport programming problem. There's a reason website like codeforces, leetcode, codechef and many more exists. Without having good knowledge in any one programming language you can't solve any problems and also needs logical ability to solve problems in less time complexity. — codosopher, Feb 02 '23 at 13:17
_"Without having good knowledge [...]"_ It's exactly the point. These websites are the best to pass on bad practices. For instance, someone with a "good knowledge" would know [why is `using namespace std;` considered bad practice](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) :) Moreover, _"competitive programming"_ only teaches how to program in haste. IMHO it would be way better to teach people to take time to properly think about the possible solutions of their problem (which is the exact opposite of rushing questions one after another) — Fareanor, Feb 02 '23 at 15:03
Yeah I agree. But Sport Programming is not about learning a new language. It's used to think how to solve problems, thoughtfully examine the problem by redefining, refining, predicting, analyzing all the corner cases and also adapting with better solutions of others with less time complexity. — codosopher, Feb 02 '23 at 15:29
@Peter Mortensen Thanks Maestro for editing my code. I see you. I'm lacking write clean code, I guess. — codosopher, Jul 31 '23 at 09:48

score 1 · Accepted Answer · answered Feb 02 '23 at 12:48

1

vector<int> v; is an empty vector, it crashes at v[arr.size()-1] = -1;. When you change it to vector<int> v(arr.size()); it will work, because then the vector has enough elements: https://godbolt.org/z/vcrKe4Ecf

Side notes:

vector<int> a as parameter makes a copy, use const vector<int> &a to avoid the copy.
for(int i=0;i<a.size();i++) will give you a warning, because a.size() returns an unsigned type. The ideal type for i would be size_t, which is the type a.size() returns. Even better would be a range for loop: for (const auto& val: a)

answered Feb 02 '23 at 12:48

mch

9,424
2
28
42

I did the same code using c++ says local address returned: https://gist.github.com/Kinji123/e7e196d6b17ddb8c615127651822a004 – codosopher Feb 02 '23 at 13:02
Look at the warnings: https://godbolt.org/z/qnrxnMhaf You cannot return a local array as a pointer. Also variable length arrays (`n` is not known at compile time) are non-standard. The `vector` solution is definitely better. – mch Feb 02 '23 at 13:05
Yeah but why it gives warning like this when I'm working with static array. The exact algorithm I have implement to solve the problem using dynamic array(vector) but never gives warning like this. Why, maestro... – codosopher Feb 02 '23 at 13:13
So I do this way now using static array to dodge the warning lol: https://gist.github.com/Kinji123/6f817fe9a64d6500c6727e0df01c7f64 – codosopher Feb 02 '23 at 13:25
`int arr[n],nger[n];` is still non standard. When returning a pointer to an array, it is just a pointer and the array goes out of scope. When returning a `vector` you return the whole object, which is fine. – mch Feb 02 '23 at 13:58
But maestro, how come array goes out of scope when I'm returning a pointer to an array because it never existed on the stack. It's present in the heap memory. Only pointer to an array present on the stack. – codosopher Feb 02 '23 at 14:54
In your example https://gist.github.com/Kinji123/6f817fe9a64d6500c6727e0df01c7f64 only the elements of `stack` are in the heap. Everything else, including all the variable length arrays are on the stack. – mch Feb 02 '23 at 14:57
No maestro, I'm talking about how compiler allocated memory when the program runs. So basically when I allocated an array inside the function, only pointer to an array present on the stack and all the array elements present in the heap memory. So I'm returning the pointer of that array from the function without touching the array elements in the heap. But it shows a warning that I cannot return a local array as a pointer. I'm not passing a local array, I'm passing the pointer of that local array and that's how array allocated in the memory, by passing the pointer, not the entire array. – codosopher Feb 02 '23 at 15:07
1

"when I allocated an array inside the function, only pointer to an array present on the stack and all the array elements present in the heap memory" is not true. When you define an array like `int a[10];` in the scope of the function, the 10 elements are on the stack. – mch Feb 02 '23 at 15:11
Okay then when we pass an array as a parameter to a function like **func(int arr[])** so in that case **arr** denotes the pointer to the array present in the heap memory. – codosopher Feb 02 '23 at 15:18
when we pass an array as a parameter to a function like **func(int arr[])** so in that case **arr** acts like a pointer to the array which is present in the heap memory, right...Is this true? – codosopher Feb 02 '23 at 17:54
No, the array is still on the stack. `arr` is a pointer to the array, but when the array is declared in a function scope, it is on the stack, not the heap. You do not have any variables on the heap in your example, only the internal memory used by the `stack` object is on the heap. – mch Feb 03 '23 at 07:47
Okay, I have another doubt, what if I use **new** keyword to initialize and declare an array inside the function. Dynamic allocation of array like **int* arr = new int[n];** so I think, in that case **arr** act like a pointer and that pointer point to an array which is located inside the heap, right... – codosopher Feb 03 '23 at 14:14
yes, that's correct. – mch Feb 03 '23 at 14:59

Next greater element in the right using 'vector'

1 Answers1