Posts

Classic Dynamic Programming X

-
Image
Very classic DP solution for this problem  Climbing Stairs II - LeetCode  with the typical hints: 1/ Min/Max problem 2/ Exponentially intractable with brute-force 3/ If you have the solutions for [0.....N-1], you can derive a formula for the solution for [N] One thing that you can do now that you have access to all LLM out there is to still continue to solve LC problems but use them to keep: A/ Improve your prompt engineering B/ Learn the capabilities of each of these models C/ Understand the solutions that they come up with, and how they might be different than yours My code is down below, along with the PROMPT used for the different models. Cheers, ACC. Code: public int ClimbStairs(int n, int[] costs) { int[] dp = new int[n + 1]; dp[0] = 0; for (int i = 1; i <= n; i++) { dp[i] = Int32.MaxValue; for (int j = 1; j <= 3; j++) { int indexFrom = i - j; int indexTo = i; if (indexFrom >= 0) ...
Post a Comment
Read more

1600 LCs

-
Image
Happy to complete my 1600th LeetCode problem. I picked a Medium one to mark this milestone: remove from a linked list elements in a given array. Use a hash set to store the elements of the array for quick look-up. Deal with the head of the list separately, then the body. Code is down below, cheers, ACC. Delete Nodes From Linked List Present in Array - LeetCode ou are given an array of integers  nums  and the  head  of a linked list. Return the  head  of the modified linked list after  removing  all nodes from the linked list that have a value that exists in  nums .   Example 1: Input:   nums = [1,2,3], head = [1,2,3,4,5] Output:   [4,5] Explanation: Remove the nodes with values 1, 2, and 3. Example 2: Input:   nums = [1], head = [1,2,1,2,1,2] Output:   [2,2,2] Explanation: Remove the nodes with value 1. Example 3: Input:   nums = [5], head = [1,2,3,4] Output:   [1,2,3,4] Explanation: No node has value 5. ...
Post a Comment
Read more

The power of pruning in backtracking V

-
Image
Backtracking is a great technique in algorithms, but it needs to be accompanied by aggressive pruning or else it may quickly become intractable. This was an interesting problem, and the small input numbers (10^5 and k<=5) tells me that the authors knew that this could quickly become intractable, even with pruning. The pruning here primarily happens in two occasions: first during the base case (k==0), second when the product becomes larger than n. Comparing my solution with Sonnet 4's and ChatGPT 5's (and I gave them all the hints too), there is a small gain in my solution compared to theirs. It was surprising to see that Anthropic's one didn't make use of pruning as well as mine's or ChatGPT 5's. Code is down below, cheers, ACC. Balanced K-Factor Decomposition - LeetCode Given two integers  n  and  k , split the number  n  into exactly  k  positive integers such that the  product  of these integers is equal to  n . Return  any ...
1 comment
Read more