You are given approaches, an array of objects { name, timeComplexity, spaceComplexity }, and a constraint object { n, memoryMB }. Return the names of the approaches that fit the budget, in their original order.
- A complexity string is one of
"O(1)", "O(log n)", "O(n)", "O(n log n)", "O(n^2)", "O(n^3)", "O(2^n)", "O(n!)" - Turn it into a number by substituting
constraint.n, with logarithms base 2 — so "O(n log n)" at n = 1000 is 1000 * Math.log2(1000) - Time budget: the machine does
1e8 basic operations per second and you have 1 second, so the approach fits on time when its value is <= 1e8 - Memory budget: each unit of space costs 8 bytes and 1 MB is
1e6 bytes, so the approach fits on memory when units * 8 <= constraint.memoryMB * 1e6 - Both budgets must hold. Comparisons are
<=, so landing exactly on the budget counts as fitting O(2^n) and O(n!) overflow to enormous values for even modest n — that is fine, they simply do not fit- An empty
approaches array returns an empty array