Oversized folders: hints, no solution
Medium · Trees
A file system is stored as a binary tree of folders: every folder holds at most two sub-folders, a left one and a right one. The value of a node is the total size in megabytes of the files sitting directly in that folder, not counting its sub-folders.
The tree is given in level order: the root first, then the children of each present node from left to right, with null standing for a missing child. Nodes below a missing child are not listed.
The total size of a folder is its own file size plus the total sizes of all folders below it. Given the tree and a limit, return the positions in the input list of every folder whose total size is strictly greater than the limit, in ascending order. Positions are zero-based and count the null entries too, so the root is at position 0.
Examples
- Input
- sizes = [5, 3, 8, 2, null, 1, 4], limit = 9
- Output
- [0, 2]
- Note
- Folder 0 totals 23 and folder 2 totals 13; folder 1 totals 5, which is not above 9.
- Input
- sizes = [7, null, 7], limit = 7
- Output
- [0]
- Note
- The root totals 14. The child totals exactly 7, which is not above the limit.
Constraints
- 0 <= number of folders <= 2000
- File sizes are integers from 0 to 1000
- limit is an integer from 0 to 2000000
Hint 1: a nudge
For one folder, what other numbers do you need before you can say whether it is over the limit?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.