Ranking: 2148 / 13794 😭
Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums…nums[i]).
Return the running sum of nums.
Equivalent to compute prefix-sum.
Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.
Start removal from element with least frequency. The will maximum the unique characters we can remove.
Q3.[FAILED] 5455. Minimum Number of Days to Make m Bouquets
click header to review question
- Spent a lot of time to understand the question.
- Did not catch the requirement of
adjacent flowersat the beginning.
Use binary search to guess answer when
- Answer is in a known range.
- Easy to determine the correctness of a guess.
- Each guess can reduce the range of answer. Most likely, the range looks like
[False, False, False, True, True].
Q4. [FAILED] 5456. Kth Ancestor of a Tree Node
You are given a tree with n nodes numbered from 0 to n-1 in the form of a parent array where parent[i] is the parent of node i. The root of the tree is node 0.
Implement the function getKthAncestor(int node, int k) to return the k-th ancestor of the given node. If there is no such ancestor, return -1.
The k-th ancestor of a tree node is the k-th node in the path from that node to the root.
Binary Lifting is a
dynamic programming approach where we pre-compute an array
memo[1, log(n)][1, n] where
2^i-th ancestor of node
Binary Lifting can also be used to solve
Lowest Common Ancestor of two nodes in a tree.
- Ready question more carefully. Catch all requirement before coding.
- Be more clear on when will
binary searchcan be applied to
guess and find answer. Be familiar with this tool.
- Learnt new technique -