'I am doing the leetcode problem Container with most water. I am wondering why one method goes over the time limit
I solved the leetcode problem https://leetcode.com/problems/container-with-most-water/ I had to write two different solutions because one of them would go over the time limit. I would expect behavior for both of them to be O(n) time and I was wondering what might be causing one of them to have a longer runtime. I am not looking for a cleaner solution this is more for my understanding of why there is a significant difference in runtime for what I perceive to be very similar solutions. My guess is maybe erase() copies over the vector and takes O(n) but I really do not understand how it works. I have attached a link to the problem for context: https://leetcode.com/problems/container-with-most-water/ and my solutions below. Thank you in advance!
class Solution {
public:
int maxArea(vector<int>& height) {
int largest = 0;
int first = 0;
int last = 0;
first = height.front();
last = height.back();
while(height.size() != 1) {
first = height.front();
last = height.back();
int temp = min(first,last)*(height.size()-1);
largest = max(largest, temp);
if(first <= last){
height.erase(height.begin());
}
else
{
height.pop_back();
}
}
return largest;
}
};
The solution above did not pass as it took too much time on the longer examples, which makes me think I am getting a runtime that is not O(n).
class Solution {
public:
int maxArea(vector<int>& height) {
unsigned int largest = 0;
unsigned int first = 0;
unsigned int last = 0;
unsigned int i = 0;
unsigned int j = height.size() - 1;
while(i!=j) {
first = height[i];
last = height[j];
unsigned int temp = min(first,last)*(j - i);
largest = max(largest, temp);
if(first <= last){
i++;
}
else
{
j--;
}
}
return largest;
}
};
This solution passed fine. I do not understand why my first solution would have a significant runtime difference in comparison to my second solution.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
