D-Lite

Each square contributes area based on how the line cuts through it
If line is at y = h and square has bottom at y, top at y + l:

Below: contributes min(h - y, l) of its height (clamped to [0, l])
Above: contributes max(y + l - h, 0) of its height


Since area = height × side_length, I can think in terms of "total height below" vs "total height above"

Approach:

D-Lite

Based on hints offered on leetcode, we can just move diagonally as possible before optimising to move vertical or horizontal. But diagonal will reduce the slow rate of movement as much as possible. 
Checking the discussions showed a mathematical formula: time = max(|x1 - x2|, |y1-y2|)

```
use std::cmp::max;

impl Solution {
    pub fn min_time_to_visit_all_points(points: Vec<Vec<i32>>) -> i32 {
        if points.len() <= 1 {
            return 0;

D-Lite

	So I knew it is going to be a DFS approach, going down the tree following the root. To quickly help refresh my memory, I did the max depth of a tree LC, and got the most optimal answer in a single pass: https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
- Base case: If node is None, return 0 
- Recursively get the max depth of left and right subtrees 
- Return the maximum of the two depths + 1 (for current node) 
- Single pass solution with O(n) time complexity
```
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,

D-Lite

 Instead of trying every possible combination (which would be exponential), we use dynamic programming to build the solution step by step. At each step, we decide whether to include the current pair of elements or skip them.


You can build the solution gradually by considering one pair of elements at a time.
The secret is to realize that the optimal answer for the first i elements of nums1 and first j elements of nums2 depends on four simple choices at each step:
* Take just the current pair and start fresh
* Take the current pair and add it to what we had before
* Skip the current element from nums1
* Skip the current element from nums2

D-Lite

My initial thought is doing a DFS pass through the tree. Things to take note of:
- I will go through the tree and calculate the total sum of the tree.
- Knowing the sum of a subtree, the 2nd subtree will therefore be total sum - subtree sum.
- Record the sum of every subtree.
- Maximise S * (Totalsum-S) for all S (Subtree)
- Then we can know the max sum by combining subtrees.
```
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {

D-Lite

This is a classic tree transversal problem. The type of tree is not significant here. My go to is a level order (breadth first) transversal, either recursively or iteratively.
- Calculate sum
- Compare the sum and return the max
- If 2 levels have the same max sum, return the smallest level number
- The max sum itself can be negative
- Initialize max_sum at neg infinity

```
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]

D-Lite

My first approach was to go round all at once, in a greedy approach way. But it was figuring the movement of the negative signs around the matrix. 
Watching neetcode helped.
Now, we just sum all numbers as absolute. We also keep track of negative numbers on the go
Then at the end, if we check the modulo of the number of negative numbers, and it remains 1, we can then negate the minimum absolute value and double subtract it from the total sum we had earlier.
```
use std::cmp;

impl Solution {
    pub fn max_matrix_sum(matrix: Vec<Vec<i32>>) -> i64 {
        let mut total_sum: i64 = 0;

D-Lite

Initial approach is to follow through with all numbers, ensuring once their divisor is > 4, they are dismissed immediately.
Further check down the line shows we can find the square root of this numbers, and divide from 1 to the √num. If perfect square, we can multiply divisor by 2 then -1 or if not perfect , we can multiply by 2 and add 0.

Some feedbacks received also showed we can use other mathematical derivatives like:
numbers with 4 divisors have unique features:
a. n = p³ (cube of a prime, divisors: 1, p, p², p³) => e.g 8 = 2^3
		Divisors: 1, 2, 4, 8 (which is 1, 2¹, 2², 2³)
b. n = p × q => sum of 2 dinstinct prime numbers. =>  21 = 3 × 7
		Divisors: 1, 3, 7, 21
		

D-Lite

Dynamic dp problem. I had the base case in mind, but the loop required some mathematics. 
Watching this page over and over again did the magic: https://www.youtube.com/watch?v=W-WvItFiWX8

impl Solution {
    pub fn num_of_ways(n: i32) -> i32 {
        let modu = 1_000_000_007i64;
        
        if n == 1 {
            return 12;
        }

D-Lite

My initial approach was to keep an hashmap of scores. The [number, no_of_times]. After then, I can loop over the nums array, and add to my hashmap.
	Then after, I convert to a Vec of tuples, sort descending, to get the most frequent element first and return it.
	
```
use std::collections::HashMap;

impl Solution {
	pub fn repeated_n_times(nums: Vec<i32>) -> i32 {
			let mut scores = HashMap::with_capacity(nums.len());