Elegant C++ Solution O(N) space time with detailed explanation.
struct Solution {\n        int nthUglyNumber(int n) {\n            vector <int> results (1,1);\n            int i = 0, j = 0, k = 0;\n            while (results
    struct Solution {\n        int nthUglyNumber(int n) {\n            vector <int> results (1,1);\n            int i = 0, j = 0, k = 0;\n            while (results.size() < n)\n            {\n                results.push_back(min(results[i] * 2, min(results[j] * 3, results[k] * 5)));\n                if (results.back() == results[i] * 2) ++i;\n                if (results.back() == results[j] * 3) ++j;\n                if (results.back() == results[k] * 5) ++k;\n            }\n            return results.back();\n        }\n    };\n\n**Explanation:**\n\nThe key is to realize each number can be and have to be generated by a former number multiplied by 2, 3 or 5\ne.g. \n1 2 3 4 5 6 8 9 10 12 15..\nwhat is next?\nit must be x * 2 or y * 3 or z * 5, where x, y, z is an existing number.\n\nHow do we determine x, y, z then?\napparently, you can just *traverse the sequence generated by far* from 1 ... 15, until you find such x, y, z that x * 2, y * 3, z * 5 is just bigger than 15. In this case x=8, y=6, z=4. Then you compare x * 2, y * 3, z * 5 so you know next number will be x * 2 = 8 * 2 = 16.\nk, now you have 1,2,3,4,....,15, 16,\n\nThen what is next?\nYou wanna do the same process again to find the new x, y, z, but you realize, wait, do I have to \n*traverse the sequence generated by far* again? \n\nNO! since you know last time, x=8, y=6, z=4 and x=8 was used to generate 16, so this time, you can immediately know the new_x = 9 (the next number after 8 is 9 in the generated sequence), y=6, z=4.\nThen you need to compare new_x * 2, y * 3, z * 5. You know next number is 9 * 2 = 18;\n\nAnd you also know, the next x will be 10 since new_x = 9 was used this time.\nBut what is next y? apparently, if y=6, 6*3 = 18, which is already generated in this round. So you also need to update next y from 6 to 8.\n\nBased on the idea above, you can actually generated x,y,z from very beginning, and update x, y, z accordingly. It ends up with a O(n) solution.
[]