Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2009.html

2009. Minimum Number of Operations to Make Array Continuous (Hard)

You are given an integer array nums. In one operation, you can replace any element in nums with any integer.

nums is considered continuous if both of the following conditions are fulfilled:

• All elements in nums are unique.
• The difference between the maximum element and the minimum element in nums equals nums.length - 1.

For example, nums = [4, 2, 5, 3] is continuous, but nums = [1, 2, 3, 5, 6] is not continuous.

Return the minimum number of operations to make nums continuous.

 

Example 1:

Input: nums = [4,2,5,3]
Output: 0
Explanation: nums is already continuous.

Example 2:

Input: nums = [1,2,3,5,6]
Output: 1
Explanation: One possible solution is to change the last element to 4.
The resulting array is [1,2,3,5,4], which is continuous.

Example 3:

Input: nums = [1,10,100,1000]
Output: 3
Explanation: One possible solution is to:
- Change the second element to 2.
- Change the third element to 3.
- Change the fourth element to 4.
The resulting array is [1,2,3,4], which is continuous.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

Similar Questions:

• Longest Repeating Character Replacement (Medium)
• Continuous Subarray Sum (Medium)
• Moving Stones Until Consecutive II (Medium)
• Minimum One Bit Operations to Make Integers Zero (Hard)
• Minimum Adjacent Swaps for K Consecutive Ones (Hard)

Solution 1. Sliding Window

Check out “C++ Maximum Sliding Window Cheatsheet Template!”.

Intuition: Sort and only keep unique elements. The problem is the same as “get the length of the longest subarray whose difference between min and max elements is N - 1”.

Algorithm:

The brute force way is to pick each A[i] as the start of the subarray and count the number of elements that are <= A[i] + N - 1, which takes O(N^2) time.

Since the array is already sorted, we can use sliding window so that we only traverse the entire array once.

• C++
• Python
• Java
• Go
• RenderScript

• // OJ: https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/
  // Time: O(NlogN)
  // Space: O(1)
  class Solution {
  public:
      int minOperations(vector<int>& A) {
          int N = A.size(), ans = N, j = 0;
          sort(begin(A), end(A));
          A.erase(unique(begin(A), end(A)), end(A)); // only keep unique elements
          int M = A.size();
          for (int i = 0; i < M; ++i) {
              while (j < M && A[j] < A[i] + N) ++j; // let `j` point to the first element that is out of range -- `>= A[i] + N`.
              ans = min(ans, N - j + i); // The length of this subarray is `j - i`. We need to replace `N - j + i` elements to make it continuous.
          }
          return ans;
      }
  };
  

• class Solution:
      def minOperations(self, nums: List[int]) -> int:
          n = len(nums)
          nums = sorted(set(nums))
          ans, j = n, 0
          for i, v in enumerate(nums):
              while j < len(nums) and nums[j] - v <= n - 1:
                  j += 1
              ans = min(ans, n - (j - i))
          return ans
  
  ############
  
  # 2009. Minimum Number of Operations to Make Array Continuous
  # https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous
  
  class Solution:
      def minOperations(self, nums: List[int]) -> int:
          n = len(nums)
          res = n
          nums = sorted(set(nums))
          
          for i, start in enumerate(nums):
              end = start + n - 1
              index = bisect.bisect_right(nums, end)
              between = index - i
              res = min(res, n - between)
          
          return res
  
  
  

• class Solution {
      public int minOperations(int[] nums) {
          int n = nums.length;
          Arrays.sort(nums);
          int m = 1;
          for (int i = 1; i < n; ++i) {
              if (nums[i] != nums[i - 1]) {
                  nums[m++] = nums[i];
              }
          }
          int ans = n;
          for (int i = 0, j = 0; i < m; ++i) {
              while (j < m && nums[j] - nums[i] <= n - 1) {
                  ++j;
              }
              ans = Math.min(ans, n - (j - i));
          }
          return ans;
      }
  }
  

• func minOperations(nums []int) int {
  	sort.Ints(nums)
  	n := len(nums)
  	m := 1
  	for i := 1; i < n; i++ {
  		if nums[i] != nums[i-1] {
  			nums[m] = nums[i]
  			m++
  		}
  	}
  	ans := n
  	for i, j := 0, 0; i < m; i++ {
  		for j < m && nums[j]-nums[i] <= n-1 {
  			j++
  		}
  		ans = min(ans, n-(j-i))
  	}
  	return ans
  }
  
  func min(a, b int) int {
  	if a < b {
  		return a
  	}
  	return b
  }
  

• use std::collections::BTreeSet;
  
  impl Solution {
      #[allow(dead_code)]
      pub fn min_operations(nums: Vec<i32>) -> i32 {
          let n = nums.len();
          let nums = nums.into_iter().collect::<BTreeSet<i32>>();
  
          let m = nums.len();
          let nums = nums.into_iter().collect::<Vec<i32>>();
  
          let mut ans = n;
  
          for i in 0..m {
              let j = match nums.binary_search(&(nums[i] + n as i32)) {
                  Ok(idx) => idx,
                  Err(idx) => idx,
              };
              ans = std::cmp::min(ans, n - (j - i))
          }
  
          ans as i32
      }
  }
  

Use Shrinkable Sliding Window Template:

• C++
• Python
• Java
• Go
• RenderScript

• // OJ: https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/
  // Time: O(NlogN)
  // Space: O(1)
  class Solution {
  public:
      int minOperations(vector<int>& A) {
          int N = A.size(), i = 0, j = 0, ans = 0;
          sort(begin(A), end(A));
          A.erase(unique(begin(A), end(A)), end(A)); // only keep unique elements
          for (int M = A.size(); j < M; ++j) {
              while (A[i] + N <= A[j]) ++i; // let `i` point to the first element that is in range -- `A[i] + N > A[j]`
              ans = max(ans, j - i + 1);
          }
          return N - ans;
      }
  };
  

• class Solution:
      def minOperations(self, nums: List[int]) -> int:
          n = len(nums)
          nums = sorted(set(nums))
          ans, j = n, 0
          for i, v in enumerate(nums):
              while j < len(nums) and nums[j] - v <= n - 1:
                  j += 1
              ans = min(ans, n - (j - i))
          return ans
  
  ############
  
  # 2009. Minimum Number of Operations to Make Array Continuous
  # https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous
  
  class Solution:
      def minOperations(self, nums: List[int]) -> int:
          n = len(nums)
          res = n
          nums = sorted(set(nums))
          
          for i, start in enumerate(nums):
              end = start + n - 1
              index = bisect.bisect_right(nums, end)
              between = index - i
              res = min(res, n - between)
          
          return res
  
  
  

• class Solution {
      public int minOperations(int[] nums) {
          int n = nums.length;
          Arrays.sort(nums);
          int m = 1;
          for (int i = 1; i < n; ++i) {
              if (nums[i] != nums[i - 1]) {
                  nums[m++] = nums[i];
              }
          }
          int ans = n;
          for (int i = 0, j = 0; i < m; ++i) {
              while (j < m && nums[j] - nums[i] <= n - 1) {
                  ++j;
              }
              ans = Math.min(ans, n - (j - i));
          }
          return ans;
      }
  }
  

• func minOperations(nums []int) int {
  	sort.Ints(nums)
  	n := len(nums)
  	m := 1
  	for i := 1; i < n; i++ {
  		if nums[i] != nums[i-1] {
  			nums[m] = nums[i]
  			m++
  		}
  	}
  	ans := n
  	for i, j := 0, 0; i < m; i++ {
  		for j < m && nums[j]-nums[i] <= n-1 {
  			j++
  		}
  		ans = min(ans, n-(j-i))
  	}
  	return ans
  }
  
  func min(a, b int) int {
  	if a < b {
  		return a
  	}
  	return b
  }
  

• use std::collections::BTreeSet;
  
  impl Solution {
      #[allow(dead_code)]
      pub fn min_operations(nums: Vec<i32>) -> i32 {
          let n = nums.len();
          let nums = nums.into_iter().collect::<BTreeSet<i32>>();
  
          let m = nums.len();
          let nums = nums.into_iter().collect::<Vec<i32>>();
  
          let mut ans = n;
  
          for i in 0..m {
              let j = match nums.binary_search(&(nums[i] + n as i32)) {
                  Ok(idx) => idx,
                  Err(idx) => idx,
              };
              ans = std::cmp::min(ans, n - (j - i))
          }
  
          ans as i32
      }
  }
  

Use Non-shrinkable Sliding Window Template:

• C++
• Python
• Java
• Go
• RenderScript

• // OJ: https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/
  // Time: O(NlogN)
  // Space: O(1)
  class Solution {
  public:
      int minOperations(vector<int>& A) {
          int N = A.size(), i = 0, j = 0;
          sort(begin(A), end(A));
          A.erase(unique(begin(A), end(A)), end(A)); // only keep unique elements
          for (int M = A.size(); j < M; ++j) {
              if (A[i] + N <= A[j]) ++i;
          }
          return N - j + i;
      }
  };
  

• class Solution:
      def minOperations(self, nums: List[int]) -> int:
          n = len(nums)
          nums = sorted(set(nums))
          ans, j = n, 0
          for i, v in enumerate(nums):
              while j < len(nums) and nums[j] - v <= n - 1:
                  j += 1
              ans = min(ans, n - (j - i))
          return ans
  
  ############
  
  # 2009. Minimum Number of Operations to Make Array Continuous
  # https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous
  
  class Solution:
      def minOperations(self, nums: List[int]) -> int:
          n = len(nums)
          res = n
          nums = sorted(set(nums))
          
          for i, start in enumerate(nums):
              end = start + n - 1
              index = bisect.bisect_right(nums, end)
              between = index - i
              res = min(res, n - between)
          
          return res
  
  
  

• class Solution {
      public int minOperations(int[] nums) {
          int n = nums.length;
          Arrays.sort(nums);
          int m = 1;
          for (int i = 1; i < n; ++i) {
              if (nums[i] != nums[i - 1]) {
                  nums[m++] = nums[i];
              }
          }
          int ans = n;
          for (int i = 0, j = 0; i < m; ++i) {
              while (j < m && nums[j] - nums[i] <= n - 1) {
                  ++j;
              }
              ans = Math.min(ans, n - (j - i));
          }
          return ans;
      }
  }
  

• func minOperations(nums []int) int {
  	sort.Ints(nums)
  	n := len(nums)
  	m := 1
  	for i := 1; i < n; i++ {
  		if nums[i] != nums[i-1] {
  			nums[m] = nums[i]
  			m++
  		}
  	}
  	ans := n
  	for i, j := 0, 0; i < m; i++ {
  		for j < m && nums[j]-nums[i] <= n-1 {
  			j++
  		}
  		ans = min(ans, n-(j-i))
  	}
  	return ans
  }
  
  func min(a, b int) int {
  	if a < b {
  		return a
  	}
  	return b
  }
  

• use std::collections::BTreeSet;
  
  impl Solution {
      #[allow(dead_code)]
      pub fn min_operations(nums: Vec<i32>) -> i32 {
          let n = nums.len();
          let nums = nums.into_iter().collect::<BTreeSet<i32>>();
  
          let m = nums.len();
          let nums = nums.into_iter().collect::<Vec<i32>>();
  
          let mut ans = n;
  
          for i in 0..m {
              let j = match nums.binary_search(&(nums[i] + n as i32)) {
                  Ok(idx) => idx,
                  Err(idx) => idx,
              };
              ans = std::cmp::min(ans, n - (j - i))
          }
  
          ans as i32
      }
  }
  

Discuss

https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/discuss/1470857/C%2B%2B-Sliding-Window

All Problems

All Solutions