algoadvance

Leetcode 645. Set Mismatch

Problem Statement

You have a set of integers 1, 2, ..., n with one duplicate and one missing number. Your task is to identify the duplicate number and the missing number.

You are given an integer array nums that represents this set and satisfies the following properties:

• The numbers in the given array are in the range [1, n].
• All the integers appear exactly once except for one integer which appears twice and one integer which is missing.

Return an array containing the duplicate number and the missing number.

Clarifying Questions

1. What should be the return format?
   • Return a list of two elements: the first one is the duplicate number and the second one is the missing number.
2. Are the elements in the input array guaranteed to be in the range [1, n]?
   • Yes, the problem statement guarantees that all elements in the list are within this range.
3. What is the size range of the input array?
   • The size of the array is n, where n is the number of distinct integers in the set.
4. Could the input array be empty or contain null elements?
   • According to the problem statement, the input array will not be empty and will not contain null elements.

Strategy

1. HashMap Strategy:
   • We will use a HashMap to keep track of the frequency of each number in the array.
   • Iterate through the array to populate the HashMap.
   • Iterate through the range 1 to n to find the missing number (appearing 0 times) and the duplicate number (appearing 2 times).
2. Mathematical Strategy:
   • Use mathematical properties to find the missing and duplicate numbers.
   • Calculate the expected sum and the expected sum of squares.
   • Calculate the actual sum and the actual sum of squares from the array.
   • Solve the system of equations to get the missing and duplicate numbers.

Code

Let’s implement the HashMap strategy first as it is more intuitive and easy to understand:

import java.util.HashMap;

public class SetMismatch {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        HashMap<Integer, Integer> countMap = new HashMap<>();
        
        // Populate the count map
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        
        int duplicate = -1, missing = -1;
        
        // Determine the duplicate and missing numbers
        for (int i = 1; i <= n; i++) {
            if (countMap.getOrDefault(i, 0) == 0) {
                missing = i;
            } else if (countMap.get(i) == 2) {
                duplicate = i;
            }
        }
        
        return new int[] {duplicate, missing};
    }
    
    public static void main(String[] args) {
        SetMismatch sm = new SetMismatch();
        int[] nums = {1, 2, 2, 4};
        int[] result = sm.findErrorNums(nums);
        
        System.out.println("Duplicate number: " + result[0]);
        System.out.println("Missing number: " + result[1]);
    }
}

Time Complexity

• Time Complexity: (O(n)) because we iterate through the list once to populate the HashMap, and then iterate through the range 1 to n to find the duplicate and missing numbers.
• Space Complexity: (O(n)) due to the extra space used by the HashMap to store counts of each integer.

This solution is efficient and easy to understand. It leverages the properties of HashMaps to solve the problem with linear time complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?