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[0]â€¦nums[i]).

Return the running sum of nums.

Equivalent to compute prefix-sum.

1 | class Solution: |

# 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.

1 | class Solution: |

# Q3.[**FAILED**] 5455. Minimum Number of Days to Make m Bouquets

click header to review question

## Note

- Spent a lot of time to understand the question.
- Did not catch the requirement of
`adjacent flowers`

at 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]`

.

1 | class Solution: |

# 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`

.

1 | class TreeAncestor: |

# Summary

- Ready question more carefully. Catch all requirement before coding.
- Be more clear on when will
`binary search`

can be applied to`guess and find answer`

. Be familiar with this tool. - Learnt new technique -
`Binary Lifting`