Minimum Number of Operations to Make Array Continuous

Hard

Google

1 view

Topics:

ArraysSliding Windows

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.

Minimum Number of Operations to Make Array Continuous

Hard

Google

1 view

Topics:

ArraysSliding Windows

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.

Solution

Naive Solution

A brute-force approach would be to try all possible combinations of replacing elements in the nums array and then checking if the resulting array is continuous. This would involve iterating through all possible subsets of elements to replace and, for each subset, iterating through all possible values to replace them with. This approach is highly inefficient.

Optimal Solution

Sort the array: Sort the input array nums in ascending order. This step is crucial for efficiently identifying potential continuous sequences.
Iterate through possible start points: Iterate through the sorted array, considering each element as a potential start of a continuous sequence.
Binary Search/Two Pointers: For each start element, use a second pointer to expand the window (the continuous sequence) as far as possible while maintaining the uniqueness of elements.
Calculate operations: In each window calculate the numbers of elements that are within the correct range of the start element.
Minimize operations: Track the maximum window size found. The minimum operations is nums.length - maxWindowSize

Edge Cases

Empty array: If the input array is empty, return 0 (or handle as an invalid input, depending on the problem constraints).
Array with one element: If the array has only one element, it's already continuous, so return 0.
Duplicate elements: Handle duplicate elements by using a Set to track unique elements within the current window.

Code

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }

        Arrays.sort(nums);
        int maxLen = 0;

        for (int i = 0; i < n; i++) {
            Set<Integer> seen = new HashSet<>();
            int currentLen = 0;
            for (int j = i; j < n; j++) {
                if (!seen.contains(nums[j])) {
                    if (nums[j] <= nums[i] + n - 1) {
                        seen.add(nums[j]);
                        currentLen++;
                    }
                    
                }
            }

            maxLen = Math.max(maxLen, currentLen);
        }

        return n - maxLen;
    }
}

Big O Analysis

Time Complexity: O(n²) due to the nested loops.
Space Complexity: O(n) in the worst case, due to the HashSet potentially storing all elements of the array.

Solution

Naive Solution

Optimal Solution

Sort the array: Sort the input array nums in ascending order. This step is crucial for efficiently identifying potential continuous sequences.
Iterate through possible start points: Iterate through the sorted array, considering each element as a potential start of a continuous sequence.
Binary Search/Two Pointers: For each start element, use a second pointer to expand the window (the continuous sequence) as far as possible while maintaining the uniqueness of elements.
Calculate operations: In each window calculate the numbers of elements that are within the correct range of the start element.
Minimize operations: Track the maximum window size found. The minimum operations is nums.length - maxWindowSize

Edge Cases

Empty array: If the input array is empty, return 0 (or handle as an invalid input, depending on the problem constraints).
Array with one element: If the array has only one element, it's already continuous, so return 0.
Duplicate elements: Handle duplicate elements by using a Set to track unique elements within the current window.

Code

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }

        Arrays.sort(nums);
        int maxLen = 0;

        for (int i = 0; i < n; i++) {
            Set<Integer> seen = new HashSet<>();
            int currentLen = 0;
            for (int j = i; j < n; j++) {
                if (!seen.contains(nums[j])) {
                    if (nums[j] <= nums[i] + n - 1) {
                        seen.add(nums[j]);
                        currentLen++;
                    }
                    
                }
            }

            maxLen = Math.max(maxLen, currentLen);
        }

        return n - maxLen;
    }
}

Big O Analysis

Time Complexity: O(n²) due to the nested loops.
Space Complexity: O(n) in the worst case, due to the HashSet potentially storing all elements of the array.