Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1326.html
1326. Minimum Number of Taps to Open to Water a Garden (Hard)
There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).
There are n + 1 taps located at points [0, 1, ..., n] in the garden.
Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.
Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.
Example 1:
Input: n = 5, ranges = [3,4,1,1,0,0] Output: 1 Explanation: The tap at point 0 can cover the interval [-3,3] The tap at point 1 can cover the interval [-3,5] The tap at point 2 can cover the interval [1,3] The tap at point 3 can cover the interval [2,4] The tap at point 4 can cover the interval [4,4] The tap at point 5 can cover the interval [5,5] Opening Only the second tap will water the whole garden [0,5]
Example 2:
Input: n = 3, ranges = [0,0,0,0] Output: -1 Explanation: Even if you activate all the four taps you cannot water the whole garden.
Example 3:
Input: n = 7, ranges = [1,2,1,0,2,1,0,1] Output: 3
Example 4:
Input: n = 8, ranges = [4,0,0,0,0,0,0,0,4] Output: 2
Example 5:
Input: n = 8, ranges = [4,0,0,0,4,0,0,0,4] Output: 1
Constraints:
1 <= n <= 10^4ranges.length == n + 10 <= ranges[i] <= 100
Related Topics:
Dynamic Programming, Greedy
Solution 1.
-
class Solution { public int minTaps(int n, int[] ranges) { int[][] minMaxArray = new int[n + 1][2]; for (int i = 0; i <= n; i++) { int range = ranges[i]; int min = Math.max(i - range, 0); int max = Math.min(i + range - 1, n - 1); minMaxArray[i][0] = min; minMaxArray[i][1] = max; } boolean[] covered = new boolean[n]; int coverCount = 0; int openCount = 0; boolean[] used = new boolean[n + 1]; boolean flag = true; while (flag) { flag = false; for (int i = 0; i < n; i++) { if (covered[i]) continue; int maxLengthIndex = -1; int maxLength = 0; for (int j = 0; j <= n; j++) { if (used[j]) continue; int[] array = minMaxArray[j]; int min = array[0], max = array[1]; if (min <= i && max >= i) { int length = 0; for (int k = min; k <= max; k++) { if (!covered[k]) length++; } if (length > maxLength) { maxLengthIndex = j; maxLength = length; } } } if (maxLengthIndex >= 0) { used[maxLengthIndex] = true; int min = minMaxArray[maxLengthIndex][0], max = minMaxArray[maxLengthIndex][1]; for (int j = min; j <= max; j++) { if (!covered[j]) { covered[j] = true; coverCount++; } } flag = true; openCount++; } } } return coverCount == n ? openCount : -1; } } ############ class Solution { public int minTaps(int n, int[] ranges) { int[] last = new int[n + 1]; for (int i = 0; i < n + 1; ++i) { int l = Math.max(0, i - ranges[i]), r = i + ranges[i]; last[l] = Math.max(last[l], r); } int ans = 0, mx = 0, pre = 0; for (int i = 0; i < n; ++i) { mx = Math.max(mx, last[i]); if (mx <= i) { return -1; } if (pre == i) { ++ans; pre = mx; } } return ans; } } -
// OJ: https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/ // Time: O(NlogN) // Space: O(N) class Solution { public: int minTaps(int n, vector<int>& ranges) { vector<pair<int, int>> v; for (int i = 0; i < ranges.size(); ++i) v.emplace_back(max(0, i - ranges[i]), min(n, i + ranges[i])); sort(v.begin(), v.end()); int end = 0, newEnd = 0, ans = 0; for (int i = 0; i < v.size() && end != n; ++i) { if (v[i].first > end) return -1; newEnd = max(newEnd, v[i].second); if (i + 1 == v.size() || v[i + 1].first > end) { end = newEnd; ++ans; } } return ans; } }; -
class Solution: def minTaps(self, n: int, ranges: List[int]) -> int: last = [0] * (n + 1) for i, v in enumerate(ranges): l, r = max(0, i - v), min(n, i + v) last[l] = max(last[l], r) ans = mx = pre = 0 for i in range(n): mx = max(mx, last[i]) if mx <= i: return -1 if pre == i: ans += 1 pre = mx return ans -
func minTaps(n int, ranges []int) (ans int) { last := make([]int, n+1) for i, x := range ranges { l, r := max(0, i-x), i+x last[l] = max(last[l], r) } var pre, mx int for i, j := range last[:n] { mx = max(mx, j) if mx <= i { return -1 } if pre == i { ans++ pre = mx } } return } func max(a, b int) int { if a > b { return a } return b } -
function minTaps(n: number, ranges: number[]): number { const last = new Array(n + 1).fill(0); for (let i = 0; i < n + 1; ++i) { const l = Math.max(0, i - ranges[i]); const r = i + ranges[i]; last[l] = Math.max(last[l], r); } let ans = 0; let mx = 0; let pre = 0; for (let i = 0; i < n; ++i) { mx = Math.max(mx, last[i]); if (mx <= i) { return -1; } if (pre == i) { ++ans; pre = mx; } } return ans; } -
impl Solution { #[allow(dead_code)] pub fn min_taps(n: i32, ranges: Vec<i32>) -> i32 { let mut last = vec![0; (n + 1) as usize]; let mut ans = 0; let mut mx = 0; let mut pre = 0; // Initialize the last vector for (i, &r) in ranges.iter().enumerate() { if i as i32 - r >= 0 { last[(i as i32 - r) as usize] = std::cmp::max(last[(i as i32 - r) as usize], i as i32 + r); } else { last[0] = std::cmp::max(last[0], i as i32 + r); } } for i in 0..n as usize { mx = std::cmp::max(mx, last[i]); if mx <= i as i32 { return -1; } if pre == i as i32 { ans += 1; pre = mx; } } ans } }