Minimum Number of Operations to Make Array Continuous — LeetCode 2009 Python Solution
HardArrayHash TableBinary SearchSliding Window
- Problem
- #2009
- Pattern
- Sliding Window
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given an integer array nums. In one operation, you can replace any element in nums with any integer.
Example
- Input
- nums = [4,2,5,3]
- Output
- 0
- Explanation
- nums is already continuous.
Python solution
Python
class Solution:
def minOperations(self, nums: List[int]) -> int:
ans = n = len(nums)
nums = sorted(set(nums))
for i, v in enumerate(nums):
j = bisect_right(nums, v + n - 1)
ans = min(ans, n - (j - i))
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \log n) |
| Space | O(\log n) auxiliary |
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2009. Minimum Number of Operations to Make Array Continuous 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
Frequently asked questions
- How hard is LeetCode 2009. Minimum Number of Operations to Make Array Continuous?
- LeetCode 2009. Minimum Number of Operations to Make Array Continuous is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2009. Minimum Number of Operations to Make Array Continuous?
- The Python solution on this page runs in O(n \times \log n).
- What is the space complexity of LeetCode 2009. Minimum Number of Operations to Make Array Continuous?
- The Python solution on this page uses O(\log n) auxiliary space.
- What topics does LeetCode 2009. Minimum Number of Operations to Make Array Continuous cover?
- LeetCode 2009. Minimum Number of Operations to Make Array Continuous is tagged Array, Hash Table, Binary Search and Sliding Window on LeetCode.