grid47 Exploring patterns and algorithms
Sep 3, 2024
5 min read
Solution to LeetCode 645: Set Mismatch Problem
You are given a list of integers that should originally represent all numbers from 1 to n. However, one number appears twice and another number is missing. Your task is to find the number that is duplicated and the one that is missing.
Problem
Approach
Steps
Complexity
Input: The input consists of a list of integers, nums, where each element is between 1 and n. The list has n elements, but one of the numbers appears twice and another is missing.
Example: nums = [1, 2, 2, 4]
Constraints:
• 2 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^4
Output: Return an array containing two elements: the number that is repeated and the number that is missing.
Example: [2, 3]
Constraints:
• The result array should contain exactly two integers.
Goal: Find the duplicate and the missing number in the list.
Steps:
• 1. Traverse the list and for each number, mark it as visited by negating the number at its index.
• 2. If you encounter a negative number, it means that number has already appeared, so it's the duplicate.
• 3. The missing number is the index that was never visited.
Goal: The input array will always have exactly one duplicate and one missing number.
Steps:
• The array length will be between 2 and 10^4.
• The values in the array will be within the range from 1 to n.
Assumptions:
• There will always be exactly one missing number and one duplicate number in the list.
• Input: [1, 2, 2, 4]
• Explanation: Here, 2 is repeated and the missing number is 3, so the output is [2, 3].
Approach: The solution leverages the fact that the numbers should be between 1 and n and the duplicate and missing numbers can be identified via index manipulation.
Observations:
• We can use index manipulation to mark visited numbers.
• By negating the number at the corresponding index, we can identify duplicates by encountering already negated numbers. The missing number is the index whose value is not negated.
Steps:
• 1. Initialize an array `ans` to store the result.
• 2. Traverse the `nums` array and for each number, check the index it corresponds to and negate the value at that index.
• 3. If the value at the index is already negative, it means the number has been encountered before, so it is the duplicate.
• 4. After traversal, check which index is still positive to find the missing number.
Empty Inputs:
• Input array will never be empty.
Large Inputs:
• The solution should be efficient enough to handle up to 10^4 elements.
Special Values:
• The input will always have one missing and one duplicate number.
Constraints:
• Ensure that the algorithm runs in O(n) time and uses O(1) space.
vector<int> findErrorNums(vector<int>& nums) {
vector<int> ans(2, 0);
for(int i =0; i < nums.size(); i++) {
int val = abs(nums[i]);
ans[1] ^= (i+1) ^ val;
if (nums[val-1] <0) ans[0] = val;
else nums[val-1] =-nums[val-1];
}
ans[1] ^= ans[0];
return ans;
}
1 : Function Definition
vector<int> findErrorNums(vector<int>& nums) {
This is the function definition. The function takes a reference to a vector of integers and returns a vector of integers containing the duplicate and missing number.
2 : Variable Declaration
vector<int> ans(2, 0);
Declares a vector 'ans' of size 2 initialized to zero. This will store the duplicate number at index 0 and the missing number at index 1.
3 : Loop Initialization
for(int i =0; i < nums.size(); i++) {
Starts a loop that iterates over each element in the input vector 'nums'.
4 : Absolute Value Calculation
int val = abs(nums[i]);
Takes the absolute value of the current element in the array, 'nums[i]', to avoid issues with previously modified elements.
5 : XOR Operation for Duplicate/Non-Duplicate
ans[1] ^= (i+1) ^ val;
Performs an XOR operation between the current index (i+1) and the absolute value 'val'. This helps identify the duplicate and missing numbers in the array.
6 : Duplicate Check
if (nums[val-1] <0) ans[0] = val;
Checks if the element at the index corresponding to 'val-1' is negative. If it is, this means the number 'val' is a duplicate, so it is stored in 'ans[0]'.
7 : Mark Number as Visited
else nums[val-1] =-nums[val-1];
If 'val' is not a duplicate, it negates the element at the index 'val-1' to mark that this number has been visited.
8 : Final XOR for Missing Number
ans[1] ^= ans[0];
Performs a final XOR operation between the two numbers, ensuring that the missing number is correctly identified.
9 : Return Statement
return ans;
Returns the vector 'ans' containing the duplicate number at index 0 and the missing number at index 1.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The algorithm always takes linear time to find the duplicate and the missing number.
Best Case: O(1)
Worst Case: O(1)
Description: We only use a constant amount of extra space.
