2106. Maximum Fruits Harvested After at Most K Steps

[mah-shamim]

Topics: Array, Binary Search, Sliding Window, Prefix Sum, Weekly Contest 271

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.

Example 1:

• 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:

• 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:

• 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 <= 105
• fruits[i].length == 2
• 0 <= startPos, positioni <= 2 * 105
• positioni-1 < positioni for any i > 0 (0-indexed)
• 1 <= amounti <= 104
• 0 <= k <= 2 * 105

Hint:

1. Does an optimal path have very few patterns? For example, could a path that goes left, turns and goes right, then turns again and goes left be any better than a path that simply goes left, turns, and goes right?
2. The optimal path turns at most once. That is, the optimal path is one of these: to go left only; to go right only; to go left, turn and go right; or to go right, turn and go left.
3. Moving x steps left then k-x steps right gives you a range of positions that you can reach.
4. Use prefix sums to get the sum of all fruits for each possible range.
5. Use a similar strategy for all the paths that go right, then turn and go left.

[mah-shamim]

We need to maximize the number of fruits harvested by moving at most k steps from a starting position on an infinite x-axis. The fruits are located at specific positions, and we can move left or right, harvesting fruits at each position we visit. The solution involves considering different movement patterns to cover the maximum number of fruits within the step constraint.

Approach

1. Problem Analysis: The problem requires us to find the optimal path that maximizes the fruit harvest while moving at most k steps. The fruits are given as a sorted list of positions and amounts. The key insight is that the optimal path can be one of four types:

   • Non-turning left: Move only left from the starting position.
   • Non-turning right: Move only right from the starting position.
   • Left then right: Move left first, then turn and move right.
   • Right then left: Move right first, then turn and move left.

2. Intuition: For each possible movement pattern, we calculate the maximum fruits harvested by leveraging binary search and prefix sums:

   • Prefix Sum Array: Precompute a prefix sum array to quickly calculate the sum of fruits over any contiguous segment.
   • Binary Search: Use binary search to efficiently find the boundaries of segments that can be covered within k steps for each movement pattern.

3. Algorithm Selection:

   • Non-turning Paths: For left-only and right-only movements, iterate over possible segments starting from the initial position and extending left or right as far as allowed by k steps.
   • Turning Paths: For paths that change direction once, calculate the maximum reachable segments by considering the step constraints derived from the movement patterns. Use binary search to determine the furthest positions reachable within k steps.

4. Complexity Analysis:

   • Time Complexity: The solution involves binary searches over the fruit positions for each movement pattern, leading to an overall time complexity of O(n log n), where n is the number of fruits.
   • Space Complexity: O(n) for storing prefix sums and fruit positions.

Let's implement this solution in PHP: 2106. Maximum Fruits Harvested After at Most K Steps

<?php
/**
 * @param Integer[][] $fruits
 * @param Integer $startPos
 * @param Integer $k
 * @return Integer
 */
function maxTotalFruits($fruits, $startPos, $k) {
    $n = count($fruits);
    if ($n == 0) return 0;

    $positions = array_column($fruits, 0);
    $amounts = array_column($fruits, 1);

    $prefix = [0];
    for ($i = 0; $i < $n; $i++) {
        $prefix[$i+1] = $prefix[$i] + $amounts[$i];
    }

    $j0 = -1;
    $low = 0;
    $high = $n - 1;
    while ($low <= $high) {
        $mid = intdiv($low + $high, 2);
        if ($positions[$mid] <= $startPos) {
            $j0 = $mid;
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
    }

    $j1 = -1;
    $low = 0;
    $high = $n - 1;
    while ($low <= $high) {
        $mid = intdiv($low + $high, 2);
        if ($positions[$mid] >= $startPos) {
            $j1 = $mid;
            $high = $mid - 1;
        } else {
            $low = $mid + 1;
        }
    }
    if ($j1 == -1) {
        $j1 = $n;
    }

    $ans = 0;

    if ($j0 >= 0) {
        for ($i = 0; $i <= $j0; $i++) {
            $steps = $startPos - $positions[$i];
            if ($steps <= $k) {
                $total = $prefix[$j0 + 1] - $prefix[$i];
                if ($total > $ans) {
                    $ans = $total;
                }
            }
        }
    }

    if ($j1 < $n) {
        for ($i = $j1; $i < $n; $i++) {
            $steps = $positions[$i] - $startPos;
            if ($steps <= $k) {
                $total = $prefix[$i + 1] - $prefix[$j1];
                if ($total > $ans) {
                    $ans = $total;
                }
            }
        }
    }

    if ($j0 >= 0) {
        for ($i = 0; $i <= $j0; $i++) {
            $max_r = $k - $startPos + 2 * $positions[$i];
            if ($max_r < $startPos) {
                continue;
            }
            $low_bound = 0;
            $high_bound = $n - 1;
            $r_index = -1;
            $low = 0;
            $high = $n - 1;
            while ($low <= $high) {
                $mid = intdiv($low + $high, 2);
                if ($positions[$mid] <= $max_r) {
                    $r_index = $mid;
                    $low = $mid + 1;
                } else {
                    $high = $mid - 1;
                }
            }
            if ($r_index == -1) {
                continue;
            }
            $total = $prefix[$r_index + 1] - $prefix[$i];
            if ($total > $ans) {
                $ans = $total;
            }
        }
    }

    if ($j1 < $n) {
        for ($i = $j1; $i < $n; $i++) {
            $min_l = 2 * $positions[$i] - $k - $startPos;
            $low_bound = 0;
            $high_bound = $i;
            $l_index = -1;
            $low = 0;
            $high = $i;
            while ($low <= $high) {
                $mid = intdiv($low + $high, 2);
                if ($positions[$mid] >= $min_l) {
                    $l_index = $mid;
                    $high = $mid - 1;
                } else {
                    $low = $mid + 1;
                }
            }
            if ($l_index == -1) {
                continue;
            }
            $total = $prefix[$i + 1] - $prefix[$l_index];
            if ($total > $ans) {
                $ans = $total;
            }
        }
    }

    return $ans;
}

// Test cases
$fruits1 = [[2,8],[6,3],[8,6]];
echo maxTotalFruits($fruits1, 5, 4) . "\n"; // 9

$fruits2 = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]];
echo maxTotalFruits($fruits2, 5, 4) . "\n"; // 14

$fruits3 = [[0,3],[6,4],[8,5]];
echo maxTotalFruits($fruits3, 3, 2) . "\n"; // 0
?>

Explanation:

1. Prefix Sum Array: The prefix sum array allows efficient calculation of the total fruits in any contiguous segment of the fruit positions.
2. Binary Search for Boundaries:
   • j0 is the last fruit position less than or equal to the starting position.
   • j1 is the first fruit position greater than or equal to the starting position.
3. Non-turning Paths:
   • Left-only Movement: For each fruit position to the left of the starting position, check if it can be reached within k steps. If so, calculate the total fruits from that position to j0.
   • Right-only Movement: Similarly, for each fruit position to the right, check reachability and calculate the total fruits from j1 to that position.
4. Turning Paths:
   • Left then Right: For each left fruit position, compute the maximum right position reachable within remaining steps after moving left. Use binary search to find this position and calculate the total fruits from the left position to the right position.
   • Right then Left: For each right fruit position, compute the minimum left position reachable within remaining steps after moving right. Use binary search to find this position and calculate the total fruits from the left position to the right position.
5. Result Calculation: The maximum value obtained from all four movement patterns is the solution. This approach efficiently covers all possible optimal paths within the step constraint.

[kovatz]

Thanks for solving the problem of "Maximum Fruits Harvested After at Most K Steps"

[mah-shamim]

Thanks