LeetCode Entry
904. Fruit Into Baskets
Max consequent two-types range
904. Fruit Into Baskets medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/1070
Problem TLDR
Max consequent two-types range #medium #counting
Intuition
Scan from left to right. Count current type and previous. On a third type drop the previous.
Approach
- how many extra variables we need?
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
// 39ms
fun totalFruit(f: IntArray): Int {
var p = -1; var c = 0; var j = 0
return f.withIndex().maxOf { (i, t) ->
if (t != f[j]) {
if (t != p) c = i - j
p = f[j]; j = i
}
++c
}
}
// 0ms
pub fn total_fruit(f: Vec<i32>) -> i32 {
let (mut p, mut k, mut j) = (-1, 0, 0);
f.iter().enumerate().map(|(i, &t)| {
if t != f[j] {
if t != p { k = j }
p = f[j]; j = i
}
i - k + 1
}).max().unwrap() as _
}
// 0ms
int totalFruit(vector<int>& f) {
int r = 0;
for (int i = 0, j = 0, p = -1, k = 0; i < size(f); ++i) {
if (f[i] != f[j]) {
if (f[i] != p) k = j;
p = f[j]; j = i;
}
r = max(r, i - k + 1);
} return r;
}
// 77ms
def totalFruit(self, f: List[int]) -> int:
r = j = k = 0; p = -1
for i, t in enumerate(f):
if t != f[j]:
if t != p: k = j
p,j = f[j],i
r = max(r, i - k + 1)
return r