41_first_missing_positive
dz / leetcode / 41_first_missing_positiveSummary
Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums. You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.
Node Tree
Nodes
| URL | |
| content | URL |
| hyperlink | https://leetcode.com/problems/first-missing-positive |
| intuition | |
| content | intuition |
| children | attempt_1 (wrong because it fails to recognize the "not present"), constant_space, how_to_account_for_not_present, non_constant_space |
| attempt_1 | |
| content | Find the minimum integer greater than zero, call in M, M-(M-1) gives the answer. |
| parents | intuition |
| how_to_account_for_not_present | |
| content | How does one account for "not present" in unsorted array? |
| children | what_does_sorting_get_you |
| parents | intuition |
| what_does_sorting_get_you | |
| content | What does sorting get you? Does that count? |
| children | sorted_approach |
| parents | how_to_account_for_not_present |
| sorted_approach | |
| content | if list is pre-sorted, one could do a linear sweep of sorts. The first missing positive integer would be a jump greater than 0. |
| parents | what_does_sorting_get_you |
| non_constant_space | |
| content | one hint says to think about non constant space... |
| children | some_kind_of_binary_tree_check (hint says to think about trying to rework it in constant space), use_a_data_structure |
| parents | intuition |
| use_a_data_structure | |
| content | I bet this involves a data structure. Some kind of tree. You could populate the tree in one pass, then check the tree for holes. |
| children | some_kind_of_binary_tree_check, use_hash_map_non_constant (I was thinking about trees not hash maps. oops) |
| parents | non_constant_space |
| constant_space | |
| content | constant space |
| parents | intuition |
| some_kind_of_binary_tree_check | |
| content | Instead of having it be an actual tree, you might be able to rework it so it only saves one item at a time, and have it do some kind of special check in the loop. The hint also reminds that O(n)=O(2n), so that would suggest that there could also be a sweep. |
| parents | non_constant_space, use_a_data_structure |
| editorial | |
| content | editorial |
| children | 1_index_as_hash_key |
2024-05-01 16:09:24 I just want to go on the record and say how friggin stupid this problem is. The solution is way too clever and I don't think anyone should be expected to simply come up with this out of thin air.
| 1_index_as_hash_key | |
| content | approach 1: index as hash key |
| children | use_hash_map_non_constant (non-constant simpler solution), remove_non_positive |
| parents | editorial |
| remove_non_positive | |
| content | Removing non-positive integers can be done by replacing them in place with 1. Check for 1 first, and if 1 is not there, then it was going to be your answer to begin with |
| children | can_get_of_numbers_larger_than_n |
| parents | 1_index_as_hash_key |
| can_get_of_numbers_larger_than_n | |
| content | can also get rid of numbers larger than n, but I don't understand this |
| children | toggle_negative_numbers_in_place (relies on this I think) |
| parents | remove_non_positive |
| use_hash_map_non_constant | |
| content | hash map positive number -> its presence. |
| children | toggle_negative_numbers_in_place (derived from this) |
| parents | 1_index_as_hash_key, use_a_data_structure |
| toggle_negative_numbers_in_place | |
| content | The trick here is to use the array itself as a structure to determine if the number is present or not. Say you find the number 3, you'd toggle the value x[3] to be negative, which is a way of knowing that this number exists. So, you're leveraging the negative bit flag, and the mutable nature of the array in order to keep the space constant. |
| parents | use_hash_map_non_constant, can_get_of_numbers_larger_than_n |