Maximum fruits harvested after at most k steps

Array Binary Search Sliding Window Prefix Sum

61.0% acceptance

Feb 25, 2026

1000

Fruits are available at some positions on an infinite x-axis. You are given a 2D integer array fruits where fruits[i] = [positioni, amounti] depicts amounti fruits at the position positioni. fruits is already sorted by positioni in ascending order, and each positioni is unique. You are also given an integer startPos and an integer k. Initially, you are at the position startPos. From any position, you can either walk to the left or right. It takes one step to move one unit on the x-axis, and you can walk at most k steps in total. For every position you reach, you harvest all the fruits at that position, and the fruits will disappear from that position. Return the maximum total number of fruits you can harvest.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_total_fruits(fruits: Vec<Vec<i32>>, start_pos: i32, k: i32) -> i32 {
    let n = fruits.len();
    let mut prefix = vec![0i32; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + fruits[i][1];
    }

    // For window [l..=r] of fruit positions, can we reach all from start_pos in k steps?
    let can_reach = |l: usize, r: usize| -> bool {
      let left_dist = (start_pos - fruits[l][0]).max(0);
      let right_dist = (fruits[r][0] - start_pos).max(0);
      left_dist.min(right_dist) * 2 + left_dist.max(right_dist) <= k
    };

    let mut ans = 0;
    let mut l = 0usize;
    for r in 0..n {
      while l <= r && !can_reach(l, r) {
        l += 1;
      }
      ans = ans.max(prefix[r + 1] - prefix[l]);
    }
    ans
  }
}