448. Find All Numbers Disappeared in an Array
Problem Description
The given problem describes a scenario where we have an array nums containing n integers. Each integer is within the range from 1 to n. The goal is to find all the numbers that are missing from the array. A number is missing if it is within the given range but does not appear in nums. The task is to return an array of all such missing integers.
Intuition
To efficiently find the missing numbers without using extra space, we can harness the fact that the integers in nums are in the range [1, n] and use the index as a way to flag whether a number is present. By traversing the nums array, for each value x we encounter, we can mark that x is present by flipping the sign of the element at index x-1. Note that we use abs(x) - 1 because the values in nums are 1-based, and Python uses 0-based indexing. Moreover, to ensure we don't flip the sign back if we encounter the same number twice, we only flip the sign if it's positive.
Once we've completed marking the presence of numbers, we can make a second pass through the nums array. This time, for each index i, if nums[i] is positive, it indicates that the number i+1 (since i is 0-based) was never marked and thus is missing from nums. We collect all these missing numbers and return them in the final array.
This approach works in-place, without the need for additional memory for tracking the presence of numbers, and runs in linear time since we make two passes through the array.
Which two pointer techniques do you use to check if a string is a palindrome?
Solution Approach
The solution utilizes a clever trick that takes advantage of the fact that the array nums is mutable and that all elements are initially positive. This trick uses the sign of each element to indicate whether a number corresponding to an index has been encountered. Here is a step-by-step explanation:
- Loop Through
nums: We iterate over each elementxin the arraynums. - Calculate Index: For each number
x, we compute the indexi = abs(x) - 1. Theabsfunction ensures that we are always working with a positive index, which is important since we might have previously negated some elements innums. - Negate Elements: We negate the number at index
iinnumsif it's positive (if nums[i] > 0). Negating an element marks that the numberi + 1is present in the array. If the element at indexiis already negative, we do nothing since this implies the presence ofi + 1has already been recorded. - Identify Missing Numbers: After negating elements in step 3, numbers corresponding to indices with positive values in
numsare the ones missing from the array. Thus, we create a list of such numbers by checking for positive values innumsand adjusting the indexito the actual missing numberi + 1.
The algorithm employs no additional data structures for tracking purposes, so the space complexity remains constant, i.e., O(1) (not counting the output array). The time complexity is O(n) because the array is traversed twice: once for marking presence and once for identifying missing numbers. The in-place marking is a pattern that exploits the known range of input values to use the array itself as a direct-access data structure for tracking the presence of numbers.
In summary, the algorithm leverages in-place array manipulation to solve the problem efficiently.
Which of the following problems can be solved with backtracking (select multiple)
Example Walkthrough
Let's consider a small example to illustrate the solution approach. Suppose our nums array is [4, 3, 2, 7, 8, 2, 3, 1], which has n = 8 numbers, and we are looking to find the missing numbers in the range from 1 to 8.
-
First Loop:
- We begin by traversing the array
nums. The first number is4. We calculate the index for4, which isabs(4)-1 = 3. The number at index3is7, and since it's positive, we negate it to mark that4is present. - Continuing, we encounter
3, soabs(3)-1 = 2. We negate the number at index2, which is now-2(it was2before negating7, but the value doesn't matter as we're using the absolute value). - We repeat this process for each number, and our array looks like this after the first loop:
[-4, -3, -2, -7, 8, 2, -3, -1]. Notably, the elements at indices4and5remain positive, signaling that the corresponding numbers5and6are missing.
- We begin by traversing the array
-
Second Loop:
- In this pass, we look for indices with positive numbers. At index
4, the value is8, which is positive, so we know that5is missing (4 + 1). - Similarly, at index
5, the value is2, which is positive, so6is missing (5 + 1).
- In this pass, we look for indices with positive numbers. At index
The final output array containing all missing numbers is [5, 6], as these are the numbers not marked in the nums array. This example demonstrates how, by negating numbers and using the original array as a marker, we can efficiently identify missing elements with only two traversals of nums, achieving O(n) time complexity with constant O(1) space complexity, excluding the output array.
Solution Implementation
1class Solution:
2 def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
3 # Iterate through each number in the input list
4 for number in nums:
5 # Use the absolute value to find the index (since we might have negative values due to marking)
6 index = abs(number) - 1
7
8 # Mark the number at this index as visited by making it negative
9 # Only mark it if it is positive (to handle duplicates, ensure only marked once)
10 if nums[index] > 0:
11 nums[index] *= -1
12
13 # After marking all numbers, the positive numbers' indices are the missing ones
14 # Iterate through the list, and for each positive number, the index + 1 is a missing number
15 missing_numbers = [i + 1 for i, x in enumerate(nums) if x > 0]
16
17 return missing_numbers
181class Solution {
2
3 /**
4 * Finds all the elements of [1, n] inclusive that do not appear in the array.
5 *
6 * @param nums Array of integers ranging from 1 to n, possibly containing duplicates.
7 * @return A list of integers that are missing from the array.
8 */
9 public List<Integer> findDisappearedNumbers(int[] nums) {
10 int n = nums.length;
11
12 // Iterate over each number in the array.
13 for (int num : nums) {
14 // Use absolute value in case nums[i] has been marked negative already.
15 int index = Math.abs(num) - 1;
16
17 // Mark the number at index i as negative if it's not already.
18 if (nums[index] > 0) {
19 nums[index] = -nums[index];
20 }
21 }
22
23 // Create a list to hold the result of missing numbers.
24 List<Integer> missingNumbers = new ArrayList<>();
25
26 // Check for numbers that were not marked negative.
27 for (int i = 0; i < n; i++) {
28 // If the number is positive, the number (i + 1) is missing.
29 if (nums[i] > 0) {
30 missingNumbers.add(i + 1);
31 }
32 }
33
34 return missingNumbers;
35 }
36}
371class Solution {
2public:
3 vector<int> findDisappearedNumbers(vector<int>& nums) {
4 int size = nums.size(); // Get the size of the input vector
5
6 // Iterate over all elements in the input vector
7 for (int& num : nums) {
8 int index = abs(num) - 1; // Calculate the index from the value
9
10 // If the value at the calculated index is positive, negate it
11 // Negation marks that the number at 'index + 1' exists in the array
12 if (nums[index] > 0) {
13 nums[index] = -nums[index];
14 }
15 }
16
17 vector<int> result; // Initialize an empty vector to store missing numbers
18
19 // Iterate over the numbers from 1 to n and find which indices have positive values
20 for (int i = 0; i < size; ++i) {
21 // If the value at index 'i' is positive, it means 'i + 1' is missing
22 if (nums[i] > 0) {
23 result.push_back(i + 1); // Add the missing number to the result vector
24 }
25 }
26
27 return result; // Return the vector of missing numbers
28 }
29};
301function findDisappearedNumbers(nums: number[]): number[] {
2 const size = nums.length; // The size of the input array 'nums'.
3 // Mark each number that appears in the array by negating the value at the index
4 // corresponding to that number.
5 for (const num of nums) {
6 const index = Math.abs(num) - 1; // Calculate the correct index.
7 // Negate the number at the index if it is positive.
8 if (nums[index] > 0) {
9 nums[index] = -nums[index];
10 }
11 }
12
13 // Initialize an array to hold the numbers that did not appear in 'nums'.
14 const missingNumbers: number[] = [];
15 // Traverse the array to find the indices that contain a positive number, which
16 // indicates that the number corresponding to that index did not appear in 'nums'.
17 for (let i = 0; i < size; i++) {
18 if (nums[i] > 0) {
19 missingNumbers.push(i + 1); // Add the missing number to the result array.
20 }
21 }
22
23 // Return the array containing all the missing numbers.
24 return missingNumbers;
25}
26Which two pointer techniques do you use to check if a string is a palindrome?
Time and Space Complexity
The time complexity of the provided code is O(n). This is because the code consists of a single loop that goes through the nums array with n elements exactly once, marking each number that has been seen by negating the value at the index corresponding to that number. The loop to create the output list also runs for n elements, so the entire operation is linear.
The space complexity of the code is O(1), as it only uses constant extra space. The input list is modified in place to keep track of which numbers have been seen. The list of disappeared numbers is the only additional space used, and it's the output of the function, which typically isn't counted towards space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these properties could exist for a graph but not a tree?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.