LeetCode #268 Missing Number Solution & Explanation

Klook.com
Post Views: 299

LeetCode Problem

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Solution

C# Solution

Solution1 – Array.Sort + for loop

public class Solution {
    public int MissingNumber(int[] nums) {
        int n = nums.Length;
        Array.Sort(nums);

        if(nums[0]>0)
        {
            return 0;
        }

        for(int i =1; i<n;i++)
        {
            if(nums[i]-nums[i-1]>1)
            {
                return nums[i]-1;
            }
        }

        return n;
    }
}

In this solution, we used Array.Sort function to sort the array first.

Then we can use an easy for loop to check if any number is missing.

Time Complexity : O(n log n) + O(n) ≈ O(n log n)

Extra Space Complexity : O(1) ➡ used a variable

⭐Solution2

public class Solution {
    public int MissingNumber(int[] nums) {
        return (1+nums.Length) * nums.Length /2 - nums.Sum();
    }
}

How to sum 1 to n, there have a math formula for it

➡ Sum = (1+n)*n/2

And in this problem, we need to start from 0, but that won’t affect our formula.

Time Complexity : O(n)

Extra Space Complexity : O(1)

Java Solution

Solution1

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);

        if (nums[0] > 0) {
            return 0;
        }

        for (int i = 1; i < n; i++) {
            if (nums[i] - nums[i - 1] > 1) {
                return nums[i] - 1;
            }
        }

        return n;
    }
}

Runtime : 6ms、6ms、6ms ≈ faster than 28% ….

⭐Solution2

class Solution {
    public int missingNumber(int[] nums) {
        return (nums.length * (nums.length + 1) / 2) - Arrays.stream(nums).sum();
    }
}

Runtime : 2ms、2ms、2ms ≈ faster than 30% ….

That means there must be a faster solution, and I should find it someday.

Python3 Solution

Solution1

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        
        if nums[0] > 0:
            return 0
        
        for i in range(1, n):
            if nums[i] - nums[i-1] > 1:
                return nums[i] - 1
        
        return n

Solution2

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        return (1 + len(nums)) * len(nums) // 2 - sum(nums)

JavaScript Solution

Solution1

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    nums.sort((a, b) => a - b);
    let n = nums.length;
    
    if (nums[0] > 0) {
        return 0;
    }
    
    for (let i = 1; i < n; i++) {
        if (nums[i] - nums[i-1] > 1) {
            return nums[i] - 1;
        }
    }
    
    return n;
};

⭐Array.sort() method will default to sorting the array elements as strings.

This means that if the elements in the array are numbers, they will be sorted based on their string representations in lexicographical order, rather than their numerical values.

Solution2

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    return (1 + nums.length) * nums.length / 2 - nums.reduce((sum, num) => sum + num, 0);
};

Conclusion

We can solve this problem in just one line of code, but it may not be the most efficient solution.

🧡If my solution helps, that is my honor!

🧡You can support me by clicking some ad, Thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link : Missing Number – LeetCode

Random post

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *