Maximum Fruits Harvested After At Most K Steps - Leetcode Solution

Problem Statement:

Given an orchard of trees represented by an array arr[] of N integers, where each element in the array denotes the number of fruits in the corresponding tree (arr[i] represents the number of fruits in the i-th tree), we need to harvest as many fruits as possible. However, we can only make at most K consecutive steps in the orchard while harvesting fruits, after which we have to return to the starting point.

Solution:

To solve this problem, we can use the sliding window technique. We will maintain a window of size K, which will slide over the orchard, and we will keep track of the maximum number of fruits harvested during each window position.

We will start by initializing two variables: left and right, which will represent the left and right boundaries of the window. We will also initialize a variable called max_fruits, which will represent the maximum number of fruits harvested so far. Finally, we will initialize a dictionary called fruit_count, which will keep track of the number of fruits harvested during each window position.

We will then start iterating over the orchard array, and for each iteration, we will do the following:

1. Add the current tree's fruit count to the fruit_count dictionary.
2. If the number of keys in the fruit_count dictionary is greater than 2, i.e., we have harvested from more than two types of tree, then we need to move the window.
3. Move the left boundary of the window to the right until the number of keys in the fruit_count dictionary is equal to 2.
4. Update the max_fruits variable with the current window's fruit count.
5. If the current window's fruit count is greater than max_fruits, update max_fruits with the current window's fruit count.

At each iteration, we will check if the size of the window is greater than K. If it is greater than K, we will move the left boundary of the window to the right until it is equal to K.

After we have iterated over the entire orchard array, we will return the max_fruits variable as the solution to the problem.

Python Code:

The following is the Python code for the above approach:

def totalFruit(arr, k):
    left = 0
    right = 0
    fruit_count = {}
    max_fruits = 0

    # Iterate over the orchard array
    for i in range(len(arr)):
        # Add the current tree's fruit count to the fruit_count dictionary
        if arr[i] not in fruit_count:
            fruit_count[arr[i]] = 0
        fruit_count[arr[i]] += 1

        # If the number of keys in the fruit_count dictionary is greater than 2, move the window
        while len(fruit_count) > 2:
            fruit_count[arr[left]] -= 1
            if fruit_count[arr[left]] == 0:
                del fruit_count[arr[left]]
            left += 1

        # Update the max_fruits variable with the current window's fruit count
        window_fruits = sum(fruit_count.values())
        if window_fruits > max_fruits:
            max_fruits = window_fruits

        # If the size of the window is greater than K, move the left boundary of the window
        if i - left + 1 > k:
            fruit_count[arr[left]] -= 1
            if fruit_count[arr[left]] == 0:
                del fruit_count[arr[left]]
            left += 1

    # Return the max_fruits variable as the solution to the problem
    return max_fruits

Time Complexity:

The time complexity of the above solution is O(N), where N is the size of the orchard array. We iterate over the array only once and perform constant time operations for each array element.

Space Complexity:

The space complexity of the above solution is O(1), as we use constant extra space to store the left and right boundaries, the fruit_count dictionary, and the max_fruits variable.

1