What is the time complexity of LeetCode 2106. Maximum Fruits Harvested After at Most K Steps?

The Python solution on this page runs in O(n), where n is the length of the array.

What is the space complexity of LeetCode 2106. Maximum Fruits Harvested After at Most K Steps?

The Python solution on this page uses O(1) auxiliary space.

Maximum Fruits Harvested After at Most K Steps — LeetCode 2106 Python Solution

HardArrayBinary SearchPrefix SumSliding Window

Problem: #2106
Pattern: Sliding Window
Reading time: 3 min
Source: leetcode.com

The 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.

Example

Input: fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
Output: 9
Explanation: The optimal way is to:

Python solution

Python

class Solution:
    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        ans = i = s = 0
        for j, (pj, fj) in enumerate(fruits):
            s += fj
            while (
                i <= j
                and pj
                - fruits[i][0]
                + min(abs(startPos - fruits[i][0]), abs(startPos - fruits[j][0]))
                > k
            ):
                s -= fruits[i][1]
                i += 1
            ans = max(ans, s)
        return ans

Complexity

Measure	Complexity
Time	O(n), where n is the length of the array
Space	O(1) auxiliary

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2106. Maximum Fruits Harvested After at Most K Steps is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2106. Maximum Fruits Harvested After at Most K Steps?: LeetCode 2106. Maximum Fruits Harvested After at Most K Steps is rated Hard on LeetCode.
What is the time complexity of LeetCode 2106. Maximum Fruits Harvested After at Most K Steps?: The Python solution on this page runs in O(n), where n is the length of the array.
What is the space complexity of LeetCode 2106. Maximum Fruits Harvested After at Most K Steps?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 2106. Maximum Fruits Harvested After at Most K Steps cover?: LeetCode 2106. Maximum Fruits Harvested After at Most K Steps is tagged Array, Binary Search, Prefix Sum and Sliding Window on LeetCode.