vector error

[leo2008]

I am trying to solve this in C++. How can I test it? I end up with the below errors while compiling this code.

https://www.chegg.com/homework-help/questions-and-answers/room-decorated-largest-wall-would-like-paint-skyline-skyline-consists-rectangular-building-q98118429

#include <iostream>
#include <vector>
#include <stack>

class Solution {
public:
int solution(vector<int> &A) {
    int count{0};
    std::stack<int> paintSky;

    for (auto a : A) {
        if (paintSky.empty() || (a > paintSky.top())) {
            paintSky.push(a); count++;
        } else if (a < paintSky.top()) {
            while ((!paintSky.empty()) && (a < paintSky.top())) {
                paintSky.pop();
            }
            if ((!paintSky.empty()) && (a == paintSky.top())) {
                continue;
            } else {
                paintSky.push(a); count++;
            }
        }
    }

    return count;
}

};

OUTPUT:

main.cpp:8:14: error: no template named 'vector'; did you mean 'std::vector'?
int solution(vector<int> &A) {
             ^~~~~~
             std::vector
/root/emsdk/upstream/emscripten/cache/sysroot/include/c++/v1/vector:306:28: note: 'std::vector' declared here
class _LIBCPP_TEMPLATE_VIS vector
                           ^
1 error generated.

[Peter87]

As the error says, it should be "std::vector" on line 8.

All the names in the standard library has been put inside the std namespace to avoid name clashes with your code and with other libraries. That's why you write std::stack, std::vector, etc.

[leo2008]

Ok, my bad.Never noticed it.

#include <iostream>
#include <vector>
#include <stack>

class Solution {
public:
int solution(std::vector<int> &A) {
    int count{0};
    std::stack<int> paintSky;

    for (auto a : A) {
        if (paintSky.empty() || (a > paintSky.top())) {
            paintSky.push(a); count++;
        } else if (a < paintSky.top()) {
            while ((!paintSky.empty()) && (a < paintSky.top())) {
                paintSky.pop();
            }
            if ((!paintSky.empty()) && (a == paintSky.top())) {
                continue;
            } else {
                paintSky.push(a); count++;
            }
        }
    }

    return count;
}

};

int main ()
{
}

[leo2008]

While I test the code, it does not give the expected results. For A1, expected value is 9,but got 8. For A2, expected value is 8, but got 2.

#include <iostream>
#include <vector>
#include <stack>

int solution(std::vector<int> &A) {
    int count{0};
    std::stack<int> paintSky;

    for (auto a : A) {
        if (paintSky.empty() || (a > paintSky.top())) {
            paintSky.push(a); count++;
        } else if (a < paintSky.top()) {
            while ((!paintSky.empty()) && (a < paintSky.top())) {
                paintSky.pop();
            }
            if ((!paintSky.empty()) && (a == paintSky.top())) {
                continue;
            } else {
                paintSky.push(a); count++;
            }
        }
    }

    return count;
}


int main ()
{   
    std::vector<int> A1 {1, 3, 2, 1, 2, 1, 5, 3, 3, 4, 2}, A2 {5, 8};
    std::cout << solution(A1) << ' ' << solution(A2) << std::endl;
}


OUTPUT:
8 2

[Peter87]

If you pass an array with a single array element {3} then it should return 3 if I understand correctly. But your algorithm just pushes a single element onto the paintSky stack and increments the count only once, and returns 1, so something is obviously not right. You probably need to think through your algorithm a bit more.

[seeplus]

What debugging of the code have you done? Use the debugger to trace through the code and see where it deviates from that expected from your program design. When you find an issue, you either have a code issue from the design or you have a design issue.

[leo2008]

Tried change my logic here, but the output still remains the same.
Any idea what I am doing wrong here?

Some java code is provided here, but I do not understand it.
https://stackoverflow.com/questions/53926885/how-would-i-fix-my-approach-to-this-manhattan-skyline-stone-wall-and-where-did-i

#include <iostream>
#include <vector>
#include <stack>

int solution(std::vector<int> &A) {
    std::vector<int> st;
    st.resize(A.size());
    int sp = -1;
    int ch = 0;
    for (unsigned i = 0; i < A.size(); ++i) {
        int currElem = A.at(i);
        while (sp != -1) {
            if (currElem >= st[sp])
                break;
            sp--;
        }
        if (sp == -1 || currElem != st[sp]) {
            st[++sp] = currElem;
            ch++;
        }
    }
    return ch;
}


int main ()
{   
    std::vector<int> A1 {1, 3, 2, 1, 2, 1, 5, 3, 3, 4, 2}, A2 {5, 8};
    std::cout << solution(A1) << ' ' << solution(A2) << std::endl;
}




OUTPUT:
8 2

[Peter87]

Isn't the point of this exercises that you should understand the problem and figure out a solution? You won't learn much by just looking at someone else's code and trying to copy it without understanding what it is actually doing.

I believe people need to do the things they want to become good at. If you want to learn how to write code you need to write code. If you want to learn how solve problems you need to at least try to solve problems.

[leo2008]

I am just trying to make it work, by changing my code, but somehow I still got issues. I have understood problem, but tried with 2 different logical ways to solve it.

[Peter87]

leo2008 wrote:

I am just trying to make it work...

Okay, but you won't get a complete solution from me.

leo2008 wrote:

I have understood problem

That's good but you also need to understand the different steps involved in your solution. Otherwise you have no idea what goes wrong and what you should change if it doesn't work.

[seeplus]

As I said above, step through the code and see where it deviates from what you expected from your program design. You then either have a design issue (so back back and change the design then the code to match) or you have a coding issue from the design so change the code as indicated by the design.

These kind of problems require thought first to produce an algorithm for the problem. Once you have that that you worked through that produces the correct solution then you code the program from the algorithm.

[lastchance]

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

int solution( const vector<int> &A )
{
   int counter = 0;
   for ( int i = 1; i < A.size(); i++ ) counter += max( A[i-1] - A[i], 0 );
   return counter + A.back();
}


int main ()
{   
   vector < vector<int> > tests = { { 1, 3, 2, 1, 2, 1, 5, 3, 3, 4, 2 }, {5, 8} };
   for ( auto &A : tests ) cout << solution( A ) << '\n';
}

9
8

[leo2008]

Thanks lastchance. I understood my logic had issues. Thanks everyone for your guidance and support, I have learnt from you all and lets keep learning.

[seeplus]

It isn't just logic issues. It was the approach. Lastchance's simple code above shows the benefit of having the right approach to a problem. The coding is secondary to this. Lastchance's code could be easily expressed in pseudo-code and then coded in any required language. Before approaching problems like this, often much thought is required to arrive at how the problem can be solved. Some thoughts as to how to solve won't work or become very complex. This is the important part. Once you have the how, then you're almost there. I don't know how you started, but what you don't do is to just start coding something (called 'design by code') and 'see how it goes'.

Obviously, experience in obtaining the 'right approach' helps. The more experience you have of these type of problems then often the easier it is to come up with the right approach. It can also help to come up with more than one approach and investigate the merits/problems with the different ones.

[lastchance]

@leo2008,
FWIW. my approach was:
- DRAW the first example;
- think about how to count the ENDS of the horizontal bars.

Actually, you can do it equally well by counting the STARTS of the horizontal bars. As an exercise, you could consider how to change the code to do that.