Quickslect [O(n)?] beats 98.72% (Runtime) and 100.0% (Memory)
Intuition\nWhy sort the entire list when we can already absorb any asteroids with a smaller mass than our planet? Could we just do multiple passes absorbing sma
# Intuition\nWhy sort the entire list when we can already absorb any asteroids with a smaller mass than our planet? Could we just do multiple passes absorbing smaller asteroids until no more asteroids can be absorbed? Whenever we reach that condition, if the number of remaining asteroids is 0, we can destroy / absorb all of them. Otherwise, we can\'t.\n\n# Approach\nUse a quick-select-like partitioning process to absorb asteroids that are smaller than or equal to a running mass total.\n\n1. Set a partition int to the first position in the array (0), and a variable that holds the index of the previous array to -1 (a sentinel value)\n2. While the previous partition and latest partition don\'t match\n    1. Loop through all of the esteroids from the start of the partition to the end of the list\n        - If asteroid mass <= running mass total\n            1. Add asteroid mass to running mass total\n            2. Swap asteroid mass with mass at left edge of partition\n            3. Increment partition index\n    1. If partition is now beyond the right side of the asteroids array, `return true`\n    2. If partition index is the same as the last time we tried to absorb asteroids, `return false`\n    3. Otherwise\n        - save new partition for future reference\n        - increment partition  \n\n# Complexity\n- Time complexity:\n    Assuming $$i \\in \\mathbb{Z}\\space [0, n)$$ where $$n=|asteroids|$$:\n    - $$O(n^2)$$\u2014rare situation where asteroids is a geometrically decreasing list where $$ asteroids[i] = 2^{(n-1)-i}mass$$ from $$asteroids[0] = 2^{n-1} mass$$ to $$asteroids[n-1] = 2^{0}mass = mass$$\n    - $$\\Omega(n)$$ \u2014 another rare situation where $$asteroids[i] <= mass$$\n    - Likely average $$O(n\\log n)$$ or $$O(n)$$ amoratized \u2014 need a more formal analysis to prove this one using the [master theoroem](https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)).\n- Space complexity:\n  $$O(1)$$ \u2014 uses two ints to keep track of current and previous partition indices and one unsigned long for running mass total.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    bool asteroidsDestroyed(int mass, vector<int>& asteroids) {\n        // lame sauce\n        ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);\n\n        // Use a quick-select-like partition operation\n        // to move elements that are smaller than mass to the beginning of the array\n        // while you do that, add that smaller mass to running mass variable\n        // if you get to a point in the array where the mass is "sorted", return false\n        // if you reach the end of the array, return true\n        int partIndex = 0;\n        int previousPart = -1;\n        unsigned long m = mass;\n\n        // first partition move smaller masses to left\n        while (true) {\n            for (int i = partIndex; i < asteroids.size(); i++) {\n                if (asteroids[i] <= m) {\n                    m += asteroids[i];\n                    swap(asteroids[partIndex], asteroids[i]);\n                    partIndex++;\n                }\n            }\n            if (partIndex == asteroids.size()) return true;\n            if (partIndex == previousPart) return false;\n\n            previousPart = partIndex;\n        }\n\n        return false;\n    }\n};\n```
['Quickselect', 'C++']