11 months ago

Dhruv • 0

The second question can be solved with a greedy approach in O(N):
 

int wateringPlants(vector<int>& plants, int capacity) {
        int ans = 0, cur = capacity;
        int n = plants.size();
        for(int i=0; i<n; i++) {
            if(cur >= plants[i]) {
                ans++;
                cur -= plants[i];
            } else {
                cur = capacity;
                ans += 2*(i);
                i--;
            }
        }
        return ans;
    }

Question link:
https://leetcode.com/problems/watering-plants/description/