mediumSliding WindowPattern: Mixed
Max Consecutive Same Type Solution
Problem Statement
Given an array of integers `fruit_types` representing the types of fruits, determine the maximum number of fruits that can be harvested under the constraint that only fruits of the same type can be picked consecutively.
Examples
Example 1:
Input:[1, 2, 1, 2, 3, 3, 3]
Output:3
Explanation: The maximum number of fruits that can be harvested consecutively is 3, which are of type 3.
Example 2:
Input:[1, 1, 1, 1, 1]
Output:5
Explanation: All 5 fruits are of the same type and can be harvested consecutively.
Constraints
- 1 <= length of `fruit_types` <= 10^5
- -10^9 <= `fruit_types[i]` <= 10^9
- `fruit_types` contains only integers
- The input array is not empty
- The input array contains at least one positive integer
Time: O(n) Space: O(1)
The optimized approach utilizes a sliding window technique, where we maintain a window of consecutive fruits of the same type and slide it forward when we encounter a different type, keeping track of the maximum window size seen so far. This approach has a linear time complexity of O(n), where n is the number of fruits.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
fruit_types = list(map(int, input().split()))
max_count = 0
window_start = 0
fruit_type = fruit_types[0]
for window_end in range(len(fruit_types)):
if fruit_types[window_end] != fruit_type:
max_count = max(max_count, window_end - window_start)
window_start = window_end
fruit_type = fruit_types[window_end]
max_count = max(max_count, len(fruit_types) - window_start)
print(max_count)