DEV Community 👩‍💻👨‍💻

Miss Pooja Anilkumar Patel
Miss Pooja Anilkumar Patel

Posted on • Updated on

1326. Leetcode Solution in Cpp

class Solution {
 public:
  int minTaps(int n, vector<int>& ranges) {
    vector<int> nums(n + 1);

    for (int i = 0; i <= n; ++i) {
      int l = max(0, i - ranges[i]);
      int r = min(n, i + ranges[i]);
      nums[l] = max(nums[l], r - l);
    }

    int ans = 0;
    int end = 0;
    int farthest = 0;

    for (int i = 0; i < n; i++) {
      farthest = max(farthest, i + nums[i]);
      if (i == end) {
        ++ans;
        end = farthest;
      }
    }

    return end == n ? ans : -1;
  }
};

Enter fullscreen mode Exit fullscreen mode

Top comments (0)

🌚 Browsing with dark mode makes you a better developer by a factor of exactly 40.

It's a scientific fact.