Problem

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 themaximum total number of fruits you can harvest.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


![](https://assets.leetcode.com/uploads/2021/11/21/1.png)

Input: fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
Output: 9
Explanation: 
The optimal way is to:
- Move right to position 6 and harvest 3 fruits
- Move right to position 8 and harvest 6 fruits
You moved 3 steps and harvested 3 + 6 = 9 fruits in total.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


![](https://assets.leetcode.com/uploads/2021/11/21/2.png)

Input: fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4
Output: 14
Explanation: 
You can move at most k = 4 steps, so you cannot reach position 0 nor 10.
The optimal way is to:
- Harvest the 7 fruits at the starting position 5
- Move left to position 4 and harvest 1 fruit
- Move right to position 6 and harvest 2 fruits
- Move right to position 7 and harvest 4 fruits
You moved 1 + 3 = 4 steps and harvested 7 + 1 + 2 + 4 = 14 fruits in total.

Example 3

1
2
3
4
5
6
7


![](https://assets.leetcode.com/uploads/2021/11/21/3.png)

Input: fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2
Output: 0
Explanation:
You can move at most k = 2 steps and cannot reach any position with fruits.

Constraints

  • 1 <= fruits.length <= 10^5
  • fruits[i].length == 2
  • 0 <= startPos, positioni <= 2 * 10^5
  • positioni-1 < positioni for any i > 0 (0-indexed)
  • 1 <= amounti <= 10^4
  • 0 <= k <= 2 * 10^5

Solution

Method 1 – Sliding Window + Prefix Sum

Intuition

The key idea is to maximize the total fruits collected by considering all possible intervals you can reach within k steps, either by going left first then right, or right first then left. Since the positions are sorted, we can use prefix sums and sliding window to efficiently compute the sum of fruits in any interval.

Approach

  1. Precompute prefix sums of fruit amounts for quick range queries.
  2. For each possible leftmost position you can reach within k steps, calculate the farthest right position you can reach (and vice versa).
  3. For each such interval, compute the total fruits using prefix sums.
  4. Track the maximum fruits collected over all such intervals.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
        int n = fruits.size(), ans = 0, l = 0, r = 0, sum = 0;
        while (r < n && fruits[r][0] <= startPos + k) ++r;
        for (int i = 0; i < r; ++i) sum += fruits[i][1];
        int left = 0;
        for (int i = 0; i < r; ++i) {
            while (fruits[i][0] < startPos - k) sum -= fruits[left++][1];
            int minSteps = min(abs(startPos - fruits[i][0]), abs(startPos - fruits[r-1][0])) + fruits[r-1][0] - fruits[i][0];
            if (minSteps <= k) ans = max(ans, sum);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func maxTotalFruits(fruits [][]int, startPos int, k int) int {
    n, ans, l, sum := len(fruits), 0, 0, 0
    for r := 0; r < n && fruits[r][0] <= startPos+k; r++ {
        sum += fruits[r][1]
    }
    left := 0
    for i := 0; i < n && fruits[i][0] <= startPos+k; i++ {
        for fruits[i][0] < startPos-k {
            sum -= fruits[left][1]
            left++
        }
        minSteps := min(abs(startPos-fruits[i][0]), abs(startPos-fruits[n-1][0])) + fruits[n-1][0] - fruits[i][0]
        if minSteps <= k {
            ans = max(ans, sum)
        }
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
func min(a, b int) int { if a < b { return a }; return b }
func max(a, b int) int { if a > b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int n = fruits.length, ans = 0, l = 0, sum = 0;
        int r = 0;
        while (r < n && fruits[r][0] <= startPos + k) ++r;
        for (int i = 0; i < r; ++i) sum += fruits[i][1];
        int left = 0;
        for (int i = 0; i < r; ++i) {
            while (fruits[i][0] < startPos - k) sum -= fruits[left++][1];
            int minSteps = Math.min(Math.abs(startPos - fruits[i][0]), Math.abs(startPos - fruits[r-1][0])) + fruits[r-1][0] - fruits[i][0];
            if (minSteps <= k) ans = Math.max(ans, sum);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun maxTotalFruits(fruits: Array<IntArray>, startPos: Int, k: Int): Int {
        var ans = 0
        var l = 0
        var sum = 0
        var r = 0
        while (r < fruits.size && fruits[r][0] <= startPos + k) r++
        for (i in 0 until r) sum += fruits[i][1]
        var left = 0
        for (i in 0 until r) {
            while (fruits[i][0] < startPos - k) { sum -= fruits[left++][1] }
            val minSteps = minOf(kotlin.math.abs(startPos - fruits[i][0]), kotlin.math.abs(startPos - fruits[r-1][0])) + fruits[r-1][0] - fruits[i][0]
            if (minSteps <= k) ans = maxOf(ans, sum)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def maxTotalFruits(self, fruits: list[list[int]], startPos: int, k: int) -> int:
        n = len(fruits)
        ans = l = sum_ = 0
        r = 0
        while r < n and fruits[r][0] <= startPos + k:
            r += 1
        for i in range(r):
            sum_ += fruits[i][1]
        left = 0
        for i in range(r):
            while fruits[i][0] < startPos - k:
                sum_ -= fruits[left][1]
                left += 1
            min_steps = min(abs(startPos - fruits[i][0]), abs(startPos - fruits[r-1][0])) + fruits[r-1][0] - fruits[i][0]
            if min_steps <= k:
                ans = max(ans, sum_)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn max_total_fruits(fruits: Vec<Vec<i32>>, start_pos: i32, k: i32) -> i32 {
        let n = fruits.len();
        let mut ans = 0;
        let mut l = 0;
        let mut sum = 0;
        let mut r = 0;
        while r < n && fruits[r][0] <= start_pos + k { r += 1; }
        for i in 0..r { sum += fruits[i][1]; }
        let mut left = 0;
        for i in 0..r {
            while fruits[i][0] < start_pos - k { sum -= fruits[left][1]; left += 1; }
            let min_steps = (start_pos - fruits[i][0]).abs().min((start_pos - fruits[r-1][0]).abs()) + fruits[r-1][0] - fruits[i][0];
            if min_steps <= k { ans = ans.max(sum); }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    maxTotalFruits(fruits: number[][], startPos: number, k: number): number {
        let n = fruits.length, ans = 0, l = 0, sum = 0, r = 0;
        while (r < n && fruits[r][0] <= startPos + k) ++r;
        for (let i = 0; i < r; ++i) sum += fruits[i][1];
        let left = 0;
        for (let i = 0; i < r; ++i) {
            while (fruits[i][0] < startPos - k) sum -= fruits[left++][1];
            let minSteps = Math.min(Math.abs(startPos - fruits[i][0]), Math.abs(startPos - fruits[r-1][0])) + fruits[r-1][0] - fruits[i][0];
            if (minSteps <= k) ans = Math.max(ans, sum);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), since we process each fruit position at most twice (once for left, once for right).
  • 🧺 Space complexity: O(1), as we use only a few variables for tracking sums and indices.