• 437. Path Sum III

Coding up brute force is a good starting point but a better starting point is just typing out or writing up what you need to keep track of to solve it as a human. Add “digital” constraints like only looking at one variable at a time and then try to solve and see where you have repeated work and things like that which could cause the optimal solution to fall out. In the example problem once I looked at Deepti manually solve it, the solution became obvious and I wasn’t stuck anymore.

Source: Taken from Hint #2 for problem.

• 2364. Count Number of Bad Pairs
• 2845. Count of Interesting Subarrays

Check to see if formulas in question can be rearranged into one that is easier to optimize for

Notice that (j - i != nums[j] - nums[i]) is the same as (nums[i] - i != nums[j] - j).

Inspired by: https://www.youtube.com/watch?v=TjthKf7Mc_8

• 33. Search in Rotated Sorted Array
• 34. Find First and Last Position of Element in Sorted Array
• 704. Binary Search

When you need binary search consider using partition_point function from rust std. If it’s not allowed manually implement as below.

/// Returns the index of the partition point according to the given predicate (the index of the first element of the second partition).
/// See <https://doc.rust-lang.org/std/primitive.slice.html#method.partition_point> for more info
fn partition_point<T>(arr: &[T], is_left_half: impl Fn(&T) -> bool) -> usize {
    let mut size = arr.len();
    if size == 0 {
        return 0;
    }
    let mut base = 0usize;
    while size > 1 {
        let half = size / 2;
        let mid = base + half;
        base = if is_left_half(&arr[mid]) { mid } else { base };
        size -= half;
    }
    if is_left_half(&arr[base]) {
        base + 1
    } else {
        base
    }
}

• 46. Permutations

Sometimes brute force is what the question wants. I prefer Heap’s Algorithm but it’s too difficult to memorize. So instead I think the iterative solution from the video is the easiest to remember without feeling too icky

/// Based on https://www.youtube.com/watch?v=FZe0UqISmUw
pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut result = vec![vec![]];

    // For each number insert it into each position in the previous solutions
    // Including at the end
    for num in nums {
        let mut new_result = vec![];
        for prev_result_val in result {
            for i in 0..=prev_result_val.len() {
                let mut clone = prev_result_val.clone();
                clone.insert(i, num);
                new_result.push(clone);
            }
        }
        result = new_result;
    }

    result
}

• 78. Subsets

Note that this is not subarrays. Similarly to permutations an iterative approach can be used to just add all numbers to the end only instead of all positions like permutations.

pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
    // Based on editorial and https://www.youtube.com/watch?v=z3xEwMA5Rn8
    let mut result = vec![vec![]];
    for num in nums {
        let n = result.len();
        for i in 0..n {
            let mut next = result[i].clone();
            next.push(num);
            result.push(next);
        }
    }
    result
}