Cracking the LeetCode - Kurt's Dev Space

Introduction

This is my first foray into blog writing as well as tackling LeetCode problems so strap in as we take this journey together. I'm going to go over what the problem is, how I tackled it, and a couple of solutions I came up with. Hope you enjoy!

Problem

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.

Examples

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 <= 10<sup>5</sup>
1 <= nums[i] <= 10<sup>9</sup>

Process

ChatGPT

My first step was to paste the problem directly into ChatGPT and see how it went. I've been trying to utilise LLM's since they came out as a "Co-pilot" to coding (GitHub was very clever with their name) and it's always interesting to see the result. Here is what it gave:

public int MinOperations(int[] nums)
{
    Array.Sort(nums);
    int minOps = int.MaxValue;
    int start = 0;
    int targetLength = nums[nums.Length - 1] - nums[0] - (nums.Length - 1);

    for (int end = 0; end < nums.Length; end++)
    {
        int currentSubarrayLength = end - start + 1;
        while (currentSubarrayLength > nums.Length)
        {
            start++;
            currentSubarrayLength = end - start + 1;
        }

        int missingUniqueElements = targetLength - currentSubarrayLength;
        minOps = Math.Min(minOps, missingUniqueElements);
    }

    return minOps;
}

Unfortunately, this didn't even pass the first example -
nums = [4,2,5,3]
Expected: 0
Output: -4

Not all is lost though - there were some things worth taking from this:

Sort the array
- This seems useful as we are trying to make a continuous array of numbers. Makes sense it would be easier if they were already in order
Iterating through the array to find continuous subArrays
- This seems right but the method here isn't quite working

ChatGPT - Take 2

I told ChatGPT it was wrong and gave an example. It came back with this:

public int MinOperations(int[] nums)
{
    Array.Sort(nums);
    int n = nums.Length;
    int minOps = n; // Maximum possible operations is n.

    for (int left = 0, right = 0; left < n; left++)
    {
        while (right < n - 1 && nums[right + 1] - nums[left] <= n - 1)
        {
            right++;
        }

        minOps = Math.Min(minOps, n - (right - left + 1));
    }

    return minOps;
}

And VOILA! Passing all test cases. Let's break this down...

Sort the array
Find the length of the array
1. This is also going to be the maximum possible operations to get a continuous array - you could just change every single number to be numbers from 1 to (Length of Array)
Use a sliding window starting from the first element, find the next element through the array that is needed to be changed by checking if the difference between the first and last values of the sub-array exceeds the length of the array - 1
1. Remember: "The difference between the maximum element and the minimum element in nums equals nums.length - 1."
The minimum number of operations can be calculated by taking the sub-array and subtracting the number of elements that don't need to be changed (right - left + 1) from the total elements in the array.
The sliding window can then be bound on the left by the next element and the process repeated to find the next element that needs to be changed.

This works great for our example cases but it doesn't take into account duplicate numbers in the array. E.g.
nums = [1,2,3,6,6]
Expected: 2
Output: 1

Final Hurdle

Now to fix for duplicates. A quick way to remove duplicates is by converting the array to a HashSet and then back again. A bit of LINQ can help us get there:
int[] uniqueNums = nums.ToHashSet().ToArray();

Using the new array will solve the problem outright because every duplicate number can automatically be treated as a required operation to make a continuous array. This means they can be ignored and automatically included in the minimum operations calculation as this is based on the length of the original array.

Solution

C

And here is our final solution:

public int MinOperations(int[] nums)
{
    int n = nums.Length;
    int minOps = n; // Maximum possible operations is n.
    int[] uniqueNums = nums.ToHashSet().ToArray();
    Array.Sort(uniqueNums);

    for (int left = 0, right = 0; left < uniqueNums.Length; left++)
    {
        while (right < uniqueNums.Length - 1 && uniqueNums[right + 1] - uniqueNums[left] <= n - 1)
        {
            right++;
        }

        minOps = Math.Min(minOps, n - (right - left + 1));
    }

    return minOps;
}

Python

As a fun challenge to keep my other languages sharp, I tried writing the same solution in Python3. Here's what I ended up with:

def minOperations(self, nums: List[int]) -> int:
    n = len(nums)
    min_ops = n
    unique_nums = sorted((set(nums))
    unique_length = len(unique_nums)
    right = 0

    for left in range(unique_length):
        while (right < unique_length - 1 and unique_nums[right + 1] - unique_nums[left] <= n - 1):
            right += 1

        min_ops = min(min_ops, n - (right - left + 1))

    return min_ops;

Conclusion

This turned out to be a pretty hard challenge but was a lot of fun. I found myself thinking about it throughout the day from when I first read the problem statement to when I came up with my solution. I am pretty happy with my final solution although I'm sure there are not only several different ways to solve this but ways to solve it more efficiently.

It's always interesting to see the differences in Runtime and Memory usage between languages doing the same thing. It was also an interesting process re-writing code from C# into Python as I find I normally approach solutions differently between the languages and I'm sure if I had started this problem in Python I likely would have come to a different solution.

While writing this post, I thought it would be interesting to see if I did a check for the original array being continuous before going into the loop. I'm not sure if this is more efficient as it would depend on the sample data and how many would have a minimum solution of 0. However, instead of going back and changing it, I'll leave it to you. I'm sure someone out there can let me know if that's a better solution :)

Cracking the LeetCode - 2009

Minimum Number of Operations to Make Array Continuous

Table of contents