0%

Ranking: 2148 / 13794 😭

# Q1. 5453. Running Sum of 1d Array

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.

# Q2. 5454. Least Number of Unique Integers after K Removals

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

## Note

1. Spent a lot of time to understand the question.
2. Did not catch the requirement of `adjacent flowers` at the beginning.

Use binary search to guess answer when

1. Answer is in a known range.
2. Easy to determine the correctness of a guess.
3. 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.

## [NEW TECHNIQUE] Binary Lifting

Binary Lifting is a `dynamic programming` approach where we pre-compute an array `memo[1, log(n)][1, n]` where `memo[i][j]` contains `2^i-th` ancestor of node `j`.

`Binary Lifting` can also be used to solve `Lowest Common Ancestor of two nodes in a tree`.

# Summary

1. Ready question more carefully. Catch all requirement before coding.
2. Be more clear on when will `binary search` can be applied to `guess and find answer`. Be familiar with this tool.
3. Learnt new technique - `Binary Lifting`