Timeline for Leetcode : First Missing Positive
Current License: CC BY-SA 4.0
28 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 1 at 19:58 | comment | added | Peter Cordes | In terms of performance tuning for modern CPUs, test cases are normally "tiny": so small that big-O is totally irrelevant and startup / cleanup overhead (including possible I-cache misses) are a significant fraction of the total time. e.g. where sort algorithms would use InsertionSort for (sub)-problems of this size. One step above that is what I'd call "small", where loops run a non-trivial number of iterations but data still fits in L1d, or maybe just L2 cache depending on the context of the discussion. But yeah, I can see why you picked that phrasing of "super large" | |
| Mar 1 at 18:17 | comment | added | ccot | @PeterCordes "super large" relatively to other test cases in that challenge, which on average were small. | |
| Mar 1 at 18:01 | comment | added | qwr | The rule of thumb I use for these problems is that a computer can do about 10^7 to 10^8 "simple operations" per second. So if the problem says 10^7 then linear time usually suffices, but if it gives you 10^9 it won't. | |
| Mar 1 at 17:43 | comment | added | Peter Cordes |
FYI, 10^5 integers isn't "super large" by modern standards. For 4-byte int, that would only be 390 KiB, and will fit in L2 cache on recent CPUs. "super large" or "huge" to me implies much larger than L3 cache sizes, like many megabytes, maybe a few gigabytes of data. (Or depending on context, like HPC number crunching, many gigabytes; high-end HPC systems can have terabytes of RAM.) This size is medium, or the lower end of large.
|
|
| Mar 1 at 15:57 | answer | added | carsongh | timeline score: 4 | |
| Mar 1 at 14:17 | comment | added | ccot | @Unmitigated i see, ok. | |
| Mar 1 at 14:05 | comment | added | Unmitigated |
@ccot I actually meant the memory limit is set too high. Using O(n) extra memory, e.g. with a HashSet, still easily passes.
|
|
| Mar 1 at 14:04 | comment | added | ccot | @Unmitigated yeah, I thought the same while working on it; time and memory limits are too restricted for such a problem. | |
| Mar 1 at 14:02 | comment | added | ccot | @JacobRaihle this won't work. If you have nums=[1,12,3,2,4,5]. You loop: 1 --> match index[1-1] ie index[0]. Then 2 does it match index[2-1] ie index[1]? no. How do you know which it maps? you have to check each at least O(n^2) time and even then, what do you do with "12"? length of array is 6, so 12 wont fit in this scenario and will seem like not found, which is not the case. | |
| Mar 1 at 11:49 | vote | accept | ccot | ||
| Mar 1 at 3:15 | answer | added | Unmitigated | timeline score: 6 | |
| Mar 1 at 1:07 | comment | added | Unmitigated | @qwr That will probably pass too. The time and memory limits are not set up well for this problem. | |
| Mar 1 at 0:57 | comment | added | qwr | Does in-place sort count as O(1) extra space? Radix sort runs in O(n) for ints and gives you the answer easily. | |
| Mar 1 at 0:50 | comment | added | qwr | @Unmitigated if you can get away with O(n log n) running time (which is effectively O(n) for such not large n), then a simple in-place sort can work. | |
| Feb 29 at 19:31 | comment | added | Unmitigated |
By the way, this solution that uses O(n) extra memory easily passes: unordered_set<int> s(nums.begin(), nums.end()); int i = 1; for (; s.contains(i); i++); return i;
|
|
| Feb 29 at 15:59 | comment | added | Jacob is on Codidact | Your algorithm is not O(n) in time, so arguably it should fail this way - you need a more clever algorithm to beat the challenge! If you had every positive number (up to the length of the list), then each number would be pointing at an index in the list (adjust for 0-based indexing). These numbers form "chains" of one number pointing at the index of the next number. If there are numbers "missing", then there must also be some numbers that are "too big", and the answer lies along the chain that led up to that one. | |
| Feb 29 at 10:05 | answer | added | Ingix | timeline score: 6 | |
| Feb 29 at 3:25 | history | became hot network question | |||
| Feb 28 at 21:08 | comment | added | Peilonrayz♦ | IMO your edit invalidates the answer: "The only clue the code presented offers as to what it is all about is the name of the sole public instance method." and "document everything important, and everything "externally visible"". I have rolled back your edit, please see the link in greybeard's comment for more information. | |
| Feb 28 at 21:06 | history | rollback | Peilonrayz♦ |
Rollback to Revision 4
|
|
| Feb 28 at 21:01 | comment | added | greybeard | I don't think your edit invalidates anything in the existing answer, but generally, be careful with edits once an answer is posted. | |
| Feb 28 at 20:57 | history | edited | ccot | CC BY-SA 4.0 |
added 457 characters in body
|
| Feb 28 at 20:50 | history | edited | ccot | CC BY-SA 4.0 |
added 457 characters in body
|
| Feb 28 at 20:30 | history | edited | ccot | CC BY-SA 4.0 |
added 24 characters in body
|
| Feb 28 at 20:19 | answer | added | greybeard | timeline score: 9 | |
| Feb 28 at 19:23 | history | edited | Sᴀᴍ Onᴇᴌᴀ♦ | CC BY-SA 4.0 |
update formatting, tags
|
| S Feb 28 at 19:16 | review | First questions | |||
| Feb 28 at 19:23 | |||||
| S Feb 28 at 19:16 | history | asked | ccot | CC BY-SA 4.0 |