MediumNo. 2555
Maximize Win From Two Segments — LeetCode 2555 Python Solution
- Pattern
- Sliding Window
- Topics
- Array, Binary Search, Sliding Window
- Reading time
- 2 min
- Source
- leetcode.com
The problem
There are some prizes on the X-axis. You are given an integer array prizePositions that is sorted in non-decreasing order, where prizePositions[i] is the position of the ith prize.
Example
- Input
- prizePositions = [1,1,2,2,3,3,5], k = 2
- Output
- 7
- Explanation
- In this example, you can win all 7 prizes by selecting two segments [1, 3] and [3, 5].
Python solution
class Solution:
def maximizeWin(self, prizePositions: List[int], k: int) -> int:
n = len(prizePositions)
f = [0] * (n + 1)
ans = 0
for i, x in enumerate(prizePositions, 1):
j = bisect_left(prizePositions, x - k)
ans = max(ans, f[j] + i - j)
f[i] = max(f[i - 1], i - j)
return ansComplexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2555. Maximize Win From Two Segments 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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0209 | Minimum Size Subarray Sum | Medium |
| 0713 | Subarray Product Less Than K | Medium |
| 0718 | Maximum Length of Repeated Subarray | Medium |
| 0862 | Shortest Subarray with Sum at Least K | Hard |
| 1004 | Max Consecutive Ones III | Medium |
| 2106 | Maximum Fruits Harvested After at Most K Steps | Hard |
Frequently asked questions
- How hard is LeetCode 2555. Maximize Win From Two Segments?
LeetCode 2555. Maximize Win From Two Segments is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2555. Maximize Win From Two Segments?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 2555. Maximize Win From Two Segments?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2555. Maximize Win From Two Segments cover?
LeetCode 2555. Maximize Win From Two Segments is tagged Array, Binary Search and Sliding Window on LeetCode.