leetcode – Page 2 – My Programming Notes

Tag Archives: leetcode

C# || How To Find Largest Value In Each Binary Tree Row Using C#

October 28, 2023 admin No comments

The following is a module with functions which demonstrates how to find the largest value in each binary tree row using C#.

1. Largest Values – Problem Statement

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Example 1:

Input: root = [1,3,2,5,3,null,9] Output: [1,3,9]

Example 2:

Input: root = [1,2,3] Output: [1,3]

2. Largest Values – Solution

The following is a solution which demonstrates how to find the largest value in each binary tree row.





		
		
			2. Largest Values - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 28, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the largest value binary tree row
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<int> LargestValues(TreeNode root) {
        if (root == null) {
            return new List<int>();
        }

        var ans = new List<int>();
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);

        while (queue.Count > 0) {
            int currMax = int.MinValue;
            for (int i = queue.Count -1; i >= 0; --i) {
                var node = queue.Dequeue();
                currMax = Math.Max(currMax, node.val);

                if (node.left != null) {
                    queue.Enqueue(node.left);
                }
                if (node.right != null) {
                    queue.Enqueue(node.right);
                }
            }
            ans.Add(currMax);
        }
        return ans;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 28, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the largest value binary tree row
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<int> LargestValues(TreeNode root) {
        if (root == null) {
            return new List<int>();
        }
 
        var ans = new List<int>();
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
 
        while (queue.Count > 0) {
            int currMax = int.MinValue;
            for (int i = queue.Count -1; i >= 0; --i) {
                var node = queue.Dequeue();
                currMax = Math.Max(currMax, node.val);
 
                if (node.left != null) {
                    queue.Enqueue(node.left);
                }
                if (node.right != null) {
                    queue.Enqueue(node.right);
                }
            }
            ans.Add(currMax);
        }
        return ans;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[1,3,9] [1,3]

C# || How To Find The Minimum Speed To Arrive On Time Using C#

September 01, 2023 admin No comments

The following is a module with functions which demonstrates how to find the minimum speed to arrive on time using C#.

1. Min Speed On Time – Problem Statement

You are given a floating-point number hour, representing the amount of time you have to reach the office. To commute to the office, you must take n trains in sequential order. You are also given an integer array dist of length n, where dist[i] describes the distance (in kilometers) of the i^th train ride.

Each train can only depart at an integer hour, so you may need to wait in between each train ride.

For example, if the 1^st train ride takes 1.5 hours, you must wait for an additional 0.5 hours before you can depart on the 2^nd train ride at the 2 hour mark.

Return the minimum positive integer speed (in kilometers per hour) that all the trains must travel at for you to reach the office on time, or -1 if it is impossible to be on time.

Tests are generated such that the answer will not exceed 10⁷ and hour will have at most two digits after the decimal point.

Example 1:

Input: dist = [1,3,2], hour = 6 Output: 1 Explanation: At speed 1: - The first train ride takes 1/1 = 1 hour. - Since we are already at an integer hour, we depart immediately at the 1 hour mark. The second train takes 3/1 = 3 hours. - Since we are already at an integer hour, we depart immediately at the 4 hour mark. The third train takes 2/1 = 2 hours. - You will arrive at exactly the 6 hour mark.

Example 2:

Input: dist = [1,3,2], hour = 2.7 Output: 3 Explanation: At speed 3: - The first train ride takes 1/3 = 0.33333 hours. - Since we are not at an integer hour, we wait until the 1 hour mark to depart. The second train ride takes 3/3 = 1 hour. - Since we are already at an integer hour, we depart immediately at the 2 hour mark. The third train takes 2/3 = 0.66667 hours. - You will arrive at the 2.66667 hour mark.

Example 3:

Input: dist = [1,3,2], hour = 1.9 Output: -1 Explanation: It is impossible because the earliest the third train can depart is at the 2 hour mark.

2. Min Speed On Time – Solution

The following is a solution which demonstrates how to find the minimum speed to arrive on time.





		
		
			2. Min Speed On Time - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Sep 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the minimum speed to arrive on time
// ============================================================================
public class Solution {
    public int MinSpeedOnTime(int[] dist, double hour) {
        int left = 1;
        int right = 10000000;
        int minSpeed = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // Move to the left half.
            if (TimeRequired(dist, mid) <= hour) {
                minSpeed = mid;
                right = mid - 1;
            } else {
                // Move to the right half.
                left = mid + 1;
            }
        }
        return minSpeed;
    }

    double TimeRequired(int[] dist, int speed) {
        double time = 0.0;
        for (int i = 0 ; i < dist.Length; i++) {
            double t = (double) dist[i] / (double) speed;
            // Round off to the next integer, if not the last ride.
            time += (i == dist.Length - 1 ? t : Math.Ceiling(t));
        }
        return time;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Sep 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the minimum speed to arrive on time
// ============================================================================
public class Solution {
    public int MinSpeedOnTime(int[] dist, double hour) {
        int left = 1;
        int right = 10000000;
        int minSpeed = -1;
 
        while (left <= right) {
            int mid = left + (right - left) / 2;
 
            // Move to the left half.
            if (TimeRequired(dist, mid) <= hour) {
                minSpeed = mid;
                right = mid - 1;
            } else {
                // Move to the right half.
                left = mid + 1;
            }
        }
        return minSpeed;
    }
 
    double TimeRequired(int[] dist, int speed) {
        double time = 0.0;
        for (int i = 0 ; i < dist.Length; i++) {
            double t = (double) dist[i] / (double) speed;
            // Round off to the next integer, if not the last ride.
            time += (i == dist.Length - 1 ? t : Math.Ceiling(t));
        }
        return time;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

1 3 -1

C# || How To Find The Minimum ASCII Delete Sum for Two Strings Using C#

August 28, 2023 admin No comments

The following is a module with functions which demonstrates how to find the minimum ASCII delete sum for two strings using C#.

1. Minimum Delete Sum – Problem Statement

Given two strings s1 and s2, return the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:

Input: s1 = "sea", s2 = "eat" Output: 231 Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum. Deleting "t" from "eat" adds 116 to the sum. At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.

Example 2:

Input: s1 = "delete", s2 = "leet" Output: 403 Explanation: Deleting "dee" from "delete" to turn the string into "let", adds 100[d] + 101[e] + 101[e] to the sum. Deleting "e" from "leet" adds 101[e] to the sum. At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403. If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.

2. Minimum Delete Sum – Solution

The following is a solution which demonstrates how to find the minimum ASCII delete sum for two strings.





		
		
			2. Minimum Delete Sum - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Aug 28, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find minimum ASCII delete sum two string
// ============================================================================
public class Solution {
    public int MinimumDeleteSum(string s1, string s2) {
        // Make sure s2 is smaller string
        if (s1.Length < s2.Length) {
            return MinimumDeleteSum(s2, s1);
        }

        // Case for empty s1
        int m = s1.Length, n = s2.Length;
        int[] currRow = new int[n + 1];
        for (int j = 1; j <= n; j++) {
            currRow[j] = currRow[j - 1] + s2[j - 1];
        }

        // Compute answer row-by-row
        for (int i = 1; i <= m; i++) {

            int diag = currRow[0];
            currRow[0] += s1[i - 1];

            for (int j = 1; j <= n; j++) {

                int answer;

                // If characters are the same, the answer is top-left-diagonal value
                if (s1[i - 1] == s2[j - 1]) {
                    answer = diag;
                }

                // Otherwise, the answer is minimum of top and left values with
                // deleted character's ASCII value
                else {
                    answer = Math.Min(
                        s1[i - 1] + currRow[j],
                        s2[j - 1] + currRow[j - 1]
                    );
                }

                // Before overwriting currRow[j] with answer, save it in diag
                // for the next column
                diag = currRow[j];
                currRow[j] = answer;
            }
        }

        // Return the answer
        return currRow[n];
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Aug 28, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find minimum ASCII delete sum two string
// ============================================================================
public class Solution {
    public int MinimumDeleteSum(string s1, string s2) {
        // Make sure s2 is smaller string
        if (s1.Length < s2.Length) {
            return MinimumDeleteSum(s2, s1);
        }
 
        // Case for empty s1
        int m = s1.Length, n = s2.Length;
        int[] currRow = new int[n + 1];
        for (int j = 1; j <= n; j++) {
            currRow[j] = currRow[j - 1] + s2[j - 1];
        }
 
        // Compute answer row-by-row
        for (int i = 1; i <= m; i++) {
 
            int diag = currRow[0];
            currRow[0] += s1[i - 1];
 
            for (int j = 1; j <= n; j++) {
 
                int answer;
 
                // If characters are the same, the answer is top-left-diagonal value
                if (s1[i - 1] == s2[j - 1]) {
                    answer = diag;
                }
 
                // Otherwise, the answer is minimum of top and left values with
                // deleted character's ASCII value
                else {
                    answer = Math.Min(
                        s1[i - 1] + currRow[j],
                        s2[j - 1] + currRow[j - 1]
                    );
                }
 
                // Before overwriting currRow[j] with answer, save it in diag
                // for the next column
                diag = currRow[j];
                currRow[j] = answer;
            }
        }
 
        // Return the answer
        return currRow[n];
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

231 403

C# || Fruit Into Baskets – How To Find The Maximum Number Of Fruits Using C#

July 28, 2023 admin No comments

The following is a module with functions which demonstrates how to find the maximum number of fruits using C#.

1. Total Fruit – Problem Statement

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the i^th tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array fruits, return the maximum number of fruits you can pick.

Example 1:

Input: fruits = [1,2,1] Output: 3 Explanation: We can pick from all 3 trees.

Example 2:

Input: fruits = [0,1,2,2] Output: 3 Explanation: We can pick from trees [1,2,2]. If we had started at the first tree, we would only pick from trees [0,1].

Example 3:

Input: fruits = [1,2,3,2,2] Output: 4 Explanation: We can pick from trees [2,3,2,2]. If we had started at the first tree, we would only pick from trees [1,2].

2. Total Fruit – Solution

The following is a solution which demonstrates how to find the maximum number of fruits.





		
		
			2. Total Fruit - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jul 28, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the maximum number of fruits
// ============================================================================
public class Solution {
    public int TotalFruit(int[] fruits) {
        // We use a hash map 'basket' to store the number of each type of fruit.
        var basket = new Dictionary<int, int>();
        int left = 0;
        int maxPicked = 0;

        // Add fruit from the right index (right) of the window.
        for (int right = 0; right < fruits.Length; ++right) {
            basket[fruits[right]] =  basket.GetValueOrDefault(fruits[right], 0) + 1;

            // If the current window has more than 2 types of fruit,
            // we remove fruit from the left index (left) of the window,
            // until the window has only 2 types of fruit.
            while (basket.Count > 2) {
                basket[fruits[left]] = basket[fruits[left]] - 1;
                if (basket[fruits[left]] == 0) {
                    basket.Remove(fruits[left]);
                }
                ++left;
            }

            // Update maxPicked.
            maxPicked = Math.Max(maxPicked, right - left + 1);
        }

        // Return maxPicked as the maximum number of fruits we can collect.
        return maxPicked;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jul 28, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the maximum number of fruits
// ============================================================================
public class Solution {
    public int TotalFruit(int[] fruits) {
        // We use a hash map 'basket' to store the number of each type of fruit.
        var basket = new Dictionary<int, int>();
        int left = 0;
        int maxPicked = 0;
 
        // Add fruit from the right index (right) of the window.
        for (int right = 0; right < fruits.Length; ++right) {
            basket[fruits[right]] =  basket.GetValueOrDefault(fruits[right], 0) + 1;
 
            // If the current window has more than 2 types of fruit,
            // we remove fruit from the left index (left) of the window,
            // until the window has only 2 types of fruit.
            while (basket.Count > 2) {
                basket[fruits[left]] = basket[fruits[left]] - 1;
                if (basket[fruits[left]] == 0) {
                    basket.Remove(fruits[left]);
                }
                ++left;
            }
 
            // Update maxPicked.
            maxPicked = Math.Max(maxPicked, right - left + 1);
        }
 
        // Return maxPicked as the maximum number of fruits we can collect.
        return maxPicked;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

3 3 4

C# || How To Find The Minimum Rounds To Complete All Tasks Using C#

July 01, 2023 admin No comments

The following is a module with functions which demonstrates how to find the minimum rounds to complete all tasks using C#.

1. Minimum Rounds – Problem Statement

You are given a 0-indexed integer array tasks, where tasks[i] represents the difficulty level of a task. In each round, you can complete either 2 or 3 tasks of the same difficulty level.

Return the minimum rounds required to complete all the tasks, or -1 if it is not possible to complete all the tasks.

Example 1:

Input: tasks = [2,2,3,3,2,4,4,4,4,4] Output: 4 Explanation: To complete all the tasks, a possible plan is: - In the first round, you complete 3 tasks of difficulty level 2. - In the second round, you complete 2 tasks of difficulty level 3. - In the third round, you complete 3 tasks of difficulty level 4. - In the fourth round, you complete 2 tasks of difficulty level 4. It can be shown that all the tasks cannot be completed in fewer than 4 rounds, so the answer is 4.

Example 2:

Input: tasks = [2,3,3] Output: -1 Explanation: There is only 1 task of difficulty level 2, but in each round, you can only complete either 2 or 3 tasks of the same difficulty level. Hence, you cannot complete all the tasks, and the answer is -1.

2. Minimum Rounds – Solution

The following is a solution which demonstrates how to find the minimum rounds to complete all tasks.





		
		
			2. Minimum Rounds - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jul 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find minimum rounds to complete tasks
// ============================================================================
public class Solution {
    public int MinimumRounds(int[] tasks) {
        var freq = new Dictionary<int, int>();
        // Store the frequencies in the map.
        foreach (var task in tasks) {
            freq[task] = freq.GetValueOrDefault(task, 0) + 1;
        }

        int minimumRounds = 0;
        // Iterate over the task's frequencies.
        foreach (int count in freq.Values) {
            // If the frequency is 1, it's not possible to complete tasks.
            if (count == 1) {
                return - 1;
            }

            if (count % 3 == 0) {
                // Group all the task in triplets.
                minimumRounds += count / 3;
            } else {
                // If count % 3 = 1; (count / 3 - 1) groups of triplets and 2 pairs.
                // If count % 3 = 2; (count / 3) groups of triplets and 1 pair.
                minimumRounds += (count / 3) + 1;
            }
        }

        return minimumRounds;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jul 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find minimum rounds to complete tasks
// ============================================================================
public class Solution {
    public int MinimumRounds(int[] tasks) {
        var freq = new Dictionary<int, int>();
        // Store the frequencies in the map.
        foreach (var task in tasks) {
            freq[task] = freq.GetValueOrDefault(task, 0) + 1;
        }
 
        int minimumRounds = 0;
        // Iterate over the task's frequencies.
        foreach (int count in freq.Values) {
            // If the frequency is 1, it's not possible to complete tasks.
            if (count == 1) {
                return - 1;
            }
 
            if (count % 3 == 0) {
                // Group all the task in triplets.
                minimumRounds += count / 3;
            } else {
                // If count % 3 = 1; (count / 3 - 1) groups of triplets and 2 pairs.
                // If count % 3 = 2; (count / 3) groups of triplets and 1 pair.
                minimumRounds += (count / 3) + 1;
            }
        }
 
        return minimumRounds;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

4 -1

C# || How To Design A Least Frequently Used (LFU) Cache Using C#

June 01, 2023 admin No comments

The following is a module with functions which demonstrates how to design a least frequently used (LFU) cache using C#.

1. LFU Cache – Problem Statement

Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:

LFUCache(int capacity) Initializes the object with the capacity of the data structure.
int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.
void put(int key, int value) Update the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.

To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.

When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]] Output [null, null, null, 1, null, -1, 3, null, -1, 3, 4]
Explanation // cnt(x) = the use counter for key x // cache=[] will show the last used order for tiebreakers (leftmost element is most recent) LFUCache lfu = new LFUCache(2); lfu.put(1, 1); // cache=[1,_], cnt(1)=1 lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1 lfu.get(1); // return 1 // cache=[1,2], cnt(2)=1, cnt(1)=2 lfu.put(3, 3); // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2. // cache=[3,1], cnt(3)=1, cnt(1)=2 lfu.get(2); // return -1 (not found) lfu.get(3); // return 3 // cache=[3,1], cnt(3)=2, cnt(1)=2 lfu.put(4, 4); // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1. // cache=[4,3], cnt(4)=1, cnt(3)=2 lfu.get(1); // return -1 (not found) lfu.get(3); // return 3 // cache=[3,4], cnt(4)=1, cnt(3)=3 lfu.get(4); // return 4 // cache=[4,3], cnt(4)=2, cnt(3)=3

2. LFU Cache – Solution

The following is a solution which demonstrates how to design a least frequently used (LFU) cache.





		
		
			2. LFU Cache - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jun 1, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to design a least frequently used cache
// ============================================================================
/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.Get(key);
 * obj.Put(key,value);
 */
public class LFUCache {
    // key: original key, value: frequency and original value.
    private Dictionary<int, Pair<int, Pair<int, int>>> cache;
    // key: frequency, value: All keys that have the same frequency.
    private Dictionary<int, List<Pair<int, int>>> frequencies;
    private int minf;
    private int capacity;

    public LFUCache(int capacity) {
        cache = new Dictionary<int, Pair<int, Pair<int, int>>>();
        frequencies = new Dictionary<int, List<Pair<int, int>>>();
        minf = 0;
        this.capacity = capacity;
    }

    public void Insert(int key, int frequency, int value) {
        if (!frequencies.ContainsKey(frequency)) {
            frequencies[frequency] = new List<Pair<int, int>>();
        }
        frequencies[frequency].Add(new Pair<int, int>(key, value));
        cache[key] = new Pair<int, Pair<int, int>>(frequency, frequencies[frequency].Last());
    }

    public int Get(int key) {
        if (!cache.ContainsKey(key)) {
            return -1;
        }
        var pair = cache[key];
        int f = pair.Key;
        var kv = pair.Value;
        frequencies[f].Remove(kv);
        if (frequencies[f].Count == 0 && minf == f) {
            ++minf;
        }
        Insert(key, f + 1, kv.Value);
        return kv.Value;
    }

    public void Put(int key, int value) {
        if (capacity <= 0) {
            return;
        }
        if (cache.ContainsKey(key)) {
            var it = cache[key];
            it.Value.Value = value;
            Get(key);
            return;
        }
        if (capacity == cache.Count) {
            cache.Remove(frequencies[minf].First().Key);
            frequencies[minf].RemoveAt(0);
        }
        minf = 1;
        Insert(key, 1, value);
    }

    private class Pair<TKey, TValue> {
        public TKey Key;
        public TValue Value;

        public Pair(TKey key, TValue value) {
            Key = key;
            Value = value;
        }
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jun 1, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to design a least frequently used cache
// ============================================================================
/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.Get(key);
 * obj.Put(key,value);
 */
public class LFUCache {
    // key: original key, value: frequency and original value.
    private Dictionary<int, Pair<int, Pair<int, int>>> cache;
    // key: frequency, value: All keys that have the same frequency.
    private Dictionary<int, List<Pair<int, int>>> frequencies;
    private int minf;
    private int capacity;
 
    public LFUCache(int capacity) {
        cache = new Dictionary<int, Pair<int, Pair<int, int>>>();
        frequencies = new Dictionary<int, List<Pair<int, int>>>();
        minf = 0;
        this.capacity = capacity;
    }
 
    public void Insert(int key, int frequency, int value) {
        if (!frequencies.ContainsKey(frequency)) {
            frequencies[frequency] = new List<Pair<int, int>>();
        }
        frequencies[frequency].Add(new Pair<int, int>(key, value));
        cache[key] = new Pair<int, Pair<int, int>>(frequency, frequencies[frequency].Last());
    }
 
    public int Get(int key) {
        if (!cache.ContainsKey(key)) {
            return -1;
        }
        var pair = cache[key];
        int f = pair.Key;
        var kv = pair.Value;
        frequencies[f].Remove(kv);
        if (frequencies[f].Count == 0 && minf == f) {
            ++minf;
        }
        Insert(key, f + 1, kv.Value);
        return kv.Value;
    }
 
    public void Put(int key, int value) {
        if (capacity <= 0) {
            return;
        }
        if (cache.ContainsKey(key)) {
            var it = cache[key];
            it.Value.Value = value;
            Get(key);
            return;
        }
        if (capacity == cache.Count) {
            cache.Remove(frequencies[minf].First().Key);
            frequencies[minf].RemoveAt(0);
        }
        minf = 1;
        Insert(key, 1, value);
    }
 
    private class Pair<TKey, TValue> {
        public TKey Key;
        public TValue Value;
 
        public Pair(TKey key, TValue value) {
            Key = key;
            Value = value;
        }
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[null,null,null,1,null,-1,3,null,-1,3,4]

C# || How To Find The Minimum Fuel Cost To Report To The Capital Using C#

May 24, 2023 admin No comments

The following is a module with functions which demonstrates how to find the minimum fuel cost to report to the capital using C#.

1. Minimum Fuel Cost – Problem Statement

There is a tree (i.e., a connected, undirected graph with no cycles) structure country network consisting of n cities numbered from 0 to n – 1 and exactly n – 1 roads. The capital city is city 0. You are given a 2D integer array roads where roads[i] = [a_i, b_i] denotes that there exists a bidirectional road connecting cities a_i and b_i.

There is a meeting for the representatives of each city. The meeting is in the capital city.

There is a car in each city. You are given an integer seats that indicates the number of seats in each car.

A representative can use the car in their city to travel or change the car and ride with another representative. The cost of traveling between two cities is one liter of fuel.

Return the minimum number of liters of fuel to reach the capital city.

Example 1:

Input: roads = [[0,1],[0,2],[0,3]], seats = 5 Output: 3 Explanation: - Representative₁ goes directly to the capital with 1 liter of fuel. - Representative₂ goes directly to the capital with 1 liter of fuel. - Representative₃ goes directly to the capital with 1 liter of fuel. It costs 3 liters of fuel at minimum. It can be proven that 3 is the minimum number of liters of fuel needed.

Example 2:

Input: roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2 Output: 7 Explanation: - Representative₂ goes directly to city 3 with 1 liter of fuel. - Representative₂ and representative₃ go together to city 1 with 1 liter of fuel. - Representative₂ and representative₃ go together to the capital with 1 liter of fuel. - Representative₁ goes directly to the capital with 1 liter of fuel. - Representative₅ goes directly to the capital with 1 liter of fuel. - Representative₆ goes directly to city 4 with 1 liter of fuel. - Representative₄ and representative₆ go together to the capital with 1 liter of fuel. It costs 7 liters of fuel at minimum. It can be proven that 7 is the minimum number of liters of fuel needed.

Example 3:

Input: roads = [], seats = 1 Output: 0 Explanation: No representatives need to travel to the capital city.

2. Minimum Fuel Cost – Solution

The following is a solution which demonstrates how to find the minimum fuel cost to report to the capital.





		
		
			2. Minimum Fuel Cost - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   May 24, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find minimum fuel cost to the capital
// ============================================================================
public class Solution {
    public long MinimumFuelCost(int[][] roads, int seats) {
        int n = roads.Length + 1;
        var adj = new Dictionary<int, List<int>>();
        int[] degree = new int[n];

        foreach (int[] road in roads) {
            if (!adj.ContainsKey(road[0])) {
                adj[road[0]] = new List<int>();
            }
            adj[road[0]].Add(road[1]);

            if (!adj.ContainsKey(road[1])) {
                adj[road[1]] = new List<int>();
            }
            adj[road[1]].Add(road[0]);

            ++degree[road[0]];
            ++degree[road[1]];
        }

        return BFS(n, adj, degree, seats);
    }

    public long BFS(int n, Dictionary<int, List<int>> adj, int[] degree, int seats) {
        var q = new Queue<int>();
        for (int i = 1; i < n; i++) {
            if (degree[i] == 1) {
                q.Enqueue(i);
            }
        }

        int[] representatives = new int[n];
        Array.Fill(representatives, 1);
        long fuel = 0;

        while (q.Count > 0) {
            int node = q.Dequeue();
            fuel += (long)Math.Ceiling((double) representatives[node] / seats);

            foreach (int neighbor in adj[node]) {
                --degree[neighbor];
                representatives[neighbor] += representatives[node];
                if (degree[neighbor] == 1 && neighbor != 0) {
                    q.Enqueue(neighbor);
                }
            }
        }
        return fuel;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   May 24, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find minimum fuel cost to the capital
// ============================================================================
public class Solution {
    public long MinimumFuelCost(int[][] roads, int seats) {
        int n = roads.Length + 1;
        var adj = new Dictionary<int, List<int>>();
        int[] degree = new int[n];
 
        foreach (int[] road in roads) {
            if (!adj.ContainsKey(road[0])) {
                adj[road[0]] = new List<int>();
            }
            adj[road[0]].Add(road[1]);
 
            if (!adj.ContainsKey(road[1])) {
                adj[road[1]] = new List<int>();
            }
            adj[road[1]].Add(road[0]);
 
            ++degree[road[0]];
            ++degree[road[1]];
        }
 
        return BFS(n, adj, degree, seats);
    }
 
    public long BFS(int n, Dictionary<int, List<int>> adj, int[] degree, int seats) {
        var q = new Queue<int>();
        for (int i = 1; i < n; i++) {
            if (degree[i] == 1) {
                q.Enqueue(i);
            }
        }
 
        int[] representatives = new int[n];
        Array.Fill(representatives, 1);
        long fuel = 0;
 
        while (q.Count > 0) {
            int node = q.Dequeue();
            fuel += (long)Math.Ceiling((double) representatives[node] / seats);
 
            foreach (int neighbor in adj[node]) {
                --degree[neighbor];
                representatives[neighbor] += representatives[node];
                if (degree[neighbor] == 1 && neighbor != 0) {
                    q.Enqueue(neighbor);
                }
            }
        }
        return fuel;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

3 7 0

C# || How To Find The Minimum Time To Collect All Apples In A Tree Using C#

May 23, 2023 admin No comments

The following is a module with functions which demonstrates how to find the minimum time to collect all apples in a tree using C#.

1. Min Time – Problem Statement

Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend 1 second to walk over one edge of the tree. Return the minimum time in seconds you have to spend to collect all apples in the tree, starting at vertex 0 and coming back to this vertex.

The edges of the undirected tree are given in the array edges, where edges[i] = [a_i, b_i] means that exists an edge connecting the vertices a_i and b_i. Additionally, there is a boolean array hasApple, where hasApple[i] = true means that vertex i has an apple; otherwise, it does not have any apple.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false] Output: 8 Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.

Example 2:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false] Output: 6 Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.

Example 3:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false] Output: 0

2. Min Time – Solution

The following is a solution which demonstrates how to find the cheapest flights within K stops.





		
		
			2. Min Time - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   May 23, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find minimum time to collect apples
// ============================================================================
public class Solution {
    public int MinTime(int n, int[][] edges, IList<bool> hasApple) {
        var adj = new Dictionary<int, List<int>>();
        foreach (int[] edge in edges) {
            int a = edge[0];
            int b = edge[1];
            if (!adj.ContainsKey(a)) {
                adj[a] = new List<int>();
            }
            if (!adj.ContainsKey(b)) {
                adj[b] = new List<int>();
            }
            adj[a].Add(b);
            adj[b].Add(a);
        }
        return DFS(0, -1, adj, hasApple);
    }

    public int DFS(int node, int parent, Dictionary<int, List<int>> adj, IList<bool> hasApple) {
        if (!adj.ContainsKey(node)) {
            return 0;
        }

        int totalTime = 0;
        foreach (int child in adj[node]) {
            if (child == parent) {
                continue;
            }
            int childTime = DFS(child, node, adj, hasApple);
            // childTime > 0 indicates subtree of child has apples. Since the root node of the
            // subtree does not contribute to the time, even if it has an apple, we have to check it
            // independently.
            if (childTime > 0 || hasApple[child]) {
                totalTime += childTime + 2;
            }
        }
        return totalTime;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   May 23, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find minimum time to collect apples
// ============================================================================
public class Solution {
    public int MinTime(int n, int[][] edges, IList<bool> hasApple) {
        var adj = new Dictionary<int, List<int>>();
        foreach (int[] edge in edges) {
            int a = edge[0];
            int b = edge[1];
            if (!adj.ContainsKey(a)) {
                adj[a] = new List<int>();
            }
            if (!adj.ContainsKey(b)) {
                adj[b] = new List<int>();
            }
            adj[a].Add(b);
            adj[b].Add(a);
        }
        return DFS(0, -1, adj, hasApple);
    }
 
    public int DFS(int node, int parent, Dictionary<int, List<int>> adj, IList<bool> hasApple) {
        if (!adj.ContainsKey(node)) {
            return 0;
        }
 
        int totalTime = 0;
        foreach (int child in adj[node]) {
            if (child == parent) {
                continue;
            }
            int childTime = DFS(child, node, adj, hasApple);
            // childTime > 0 indicates subtree of child has apples. Since the root node of the
            // subtree does not contribute to the time, even if it has an apple, we have to check it
            // independently.
            if (childTime > 0 || hasApple[child]) {
                totalTime += childTime + 2;
            }
        }
        return totalTime;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

8 6 0

C# || How To Sort An Array O(nlog(n)) Using C#

May 01, 2023 admin No comments

The following is a module with functions which demonstrates how to sort an array O(nlog(n)) complexity using C#.

1. Sort Array – Problem Statement

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

Example 1:

Input: nums = [5,2,3,1] Output: [1,2,3,5] Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Example 2:

Input: nums = [5,1,1,2,0,0] Output: [0,0,1,1,2,5] Explanation: Note that the values of nums are not necessairly unique.

2. Sort Array – Solution

The following is a solution which demonstrates how to sort an array O(nlog(n)) complexity using C#.





		
		
			2. Sort Array - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   May 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to sort an array O(nlog(n))
// ============================================================================
public class Solution {
    public int[] SortArray(int[] nums) {
        RadixSort(nums);
        return nums;
    }

    // Radix sort function.
    private void RadixSort(int[] arr) {
        // Find the absolute maximum element to find max number of digits.
        int maxElement = arr[0];
        foreach (int val in arr) {
            maxElement = Math.Max(Math.Abs(val), maxElement);
        }
        int maxDigits = 0;
        while (maxElement > 0) {
            maxDigits += 1;
            maxElement /= 10;
        }

        // Radix sort, least significant digit place to most significant.
        int placeValue = 1;
        for (int digit = 0; digit < maxDigits; ++digit) {
            BucketSort(arr, placeValue);
            placeValue *= 10;
        }

        // Seperate out negatives and reverse them.
        List<int> negatives = new List<int>();
        List<int> positives = new List<int>();
        foreach (int val in arr) {
            if (val < 0) {
                negatives.Add(val);
            } else {
                positives.Add(val);
            }
        }
        negatives.Reverse();

        // Final 'answer' will be 'negative' elements, then 'positive' elements.
        int index = 0;
        foreach (int val in negatives) {
            arr[index++] = val;
        }
        foreach (int val in positives) {
            arr[index++] = val;
        }
    }

    // Bucket sort function for each place value digit.
    private void BucketSort(int[] arr, int placeValue) {
        int bucketSize = 10;
        List<List<int>> buckets = new List<List<int>>();
        for (int digit = 0; digit < bucketSize; ++digit) {
            buckets.Add(new List<int>());
        }

        // Store the respective number based on its digit.
        foreach (int val in arr) {
            int digit = Math.Abs(val) / placeValue;
            digit = digit % bucketSize;
            buckets[digit].Add(val);
        }

        // Overwrite 'arr' in sorted order of current place digits.
        int index = 0;
        for (int digit = 0; digit < bucketSize; ++digit) {
            foreach (int val in buckets[digit]) {
                arr[index++] = val;
            }
        }
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   May 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to sort an array O(nlog(n))
// ============================================================================
public class Solution {
    public int[] SortArray(int[] nums) {
        RadixSort(nums);
        return nums;
    }
 
    // Radix sort function.
    private void RadixSort(int[] arr) {
        // Find the absolute maximum element to find max number of digits.
        int maxElement = arr[0];
        foreach (int val in arr) {
            maxElement = Math.Max(Math.Abs(val), maxElement);
        }
        int maxDigits = 0;
        while (maxElement > 0) {
            maxDigits += 1;
            maxElement /= 10;
        }
 
        // Radix sort, least significant digit place to most significant.
        int placeValue = 1;
        for (int digit = 0; digit < maxDigits; ++digit) {
            BucketSort(arr, placeValue);
            placeValue *= 10;
        }
 
        // Seperate out negatives and reverse them.
        List<int> negatives = new List<int>();
        List<int> positives = new List<int>();
        foreach (int val in arr) {
            if (val < 0) {
                negatives.Add(val);
            } else {
                positives.Add(val);
            }
        }
        negatives.Reverse();
 
        // Final 'answer' will be 'negative' elements, then 'positive' elements.
        int index = 0;
        foreach (int val in negatives) {
            arr[index++] = val;
        }
        foreach (int val in positives) {
            arr[index++] = val;
        }
    }
 
    // Bucket sort function for each place value digit.
    private void BucketSort(int[] arr, int placeValue) {
        int bucketSize = 10;
        List<List<int>> buckets = new List<List<int>>();
        for (int digit = 0; digit < bucketSize; ++digit) {
            buckets.Add(new List<int>());
        }
 
        // Store the respective number based on its digit.
        foreach (int val in arr) {
            int digit = Math.Abs(val) / placeValue;
            digit = digit % bucketSize;
            buckets[digit].Add(val);
        }
 
        // Overwrite 'arr' in sorted order of current place digits.
        int index = 0;
        for (int digit = 0; digit < bucketSize; ++digit) {
            foreach (int val in buckets[digit]) {
                arr[index++] = val;
            }
        }
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[1,2,3,5] [0,0,1,1,2,5]

C# || How To Find The Cheapest Flights Within K Stops Using C#

April 01, 2023 admin No comments

The following is a module with functions which demonstrates how to find the cheapest flights within K stops using C#.

1. Find Cheapest Price – Problem Statement

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from_i, to_i, price_i] indicates that there is a flight from city from_i to city to_i with cost price_i.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Example 1:

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1 Output: 700 Explanation: The graph is shown above. The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700. Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Example 2:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 Output: 200 Explanation: The graph is shown above. The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

Example 3:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0 Output: 500 Explanation: The graph is shown above. The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

2. Find Cheapest Price – Solution

The following is a solution which demonstrates how to find the cheapest flights within K stops.





		
		
			2. Find Cheapest Price - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Apr 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find cheapest flights in k stops
// ============================================================================
public class Solution {
    public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        var adj = new Dictionary<int, List<int[]>>();
        foreach (int[] i in flights) {
            if (!adj.ContainsKey(i[0])) {
                adj[i[0]] = new List<int[]>();
            }
            adj[i[0]].Add(new int[] { i[1], i[2] });
        }

        int[] stops = new int[n];
        Array.Fill(stops, int.MaxValue);
        var pq = new PriorityQueue<int[], int[]>(Comparer<int[]>.Create((a, b) => a[0] - b[0]));

        // {dist_from_src_node, node, number_of_stops_from_src_node}
        var distance = new int[] { 0, src, 0 };
        pq.Enqueue(distance, distance);

        while (pq.Count > 0) {
            int[] temp = pq.Dequeue();
            int dist = temp[0];
            int node = temp[1];
            int steps = temp[2];
            // We have already encountered a path with a lower cost and fewer stops,
            // or the number of stops exceeds the limit.
            if (steps > stops[node] || steps > k + 1) {
                continue;
            }
            stops[node] = steps;
            if (node == dst) {
                return dist;
            }
            if (!adj.ContainsKey(node)) {
                continue;
            }
            foreach (int[] a in adj[node]) {
                var newDistance = new int[] { dist + a[1], a[0], steps + 1 };
                pq.Enqueue(newDistance, newDistance);
            }
        }
        return -1;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Apr 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find cheapest flights in k stops
// ============================================================================
public class Solution {
    public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        var adj = new Dictionary<int, List<int[]>>();
        foreach (int[] i in flights) {
            if (!adj.ContainsKey(i[0])) {
                adj[i[0]] = new List<int[]>();
            }
            adj[i[0]].Add(new int[] { i[1], i[2] });
        }
 
        int[] stops = new int[n];
        Array.Fill(stops, int.MaxValue);
        var pq = new PriorityQueue<int[], int[]>(Comparer<int[]>.Create((a, b) => a[0] - b[0]));
 
        // {dist_from_src_node, node, number_of_stops_from_src_node}
        var distance = new int[] { 0, src, 0 };
        pq.Enqueue(distance, distance);
 
        while (pq.Count > 0) {
            int[] temp = pq.Dequeue();
            int dist = temp[0];
            int node = temp[1];
            int steps = temp[2];
            // We have already encountered a path with a lower cost and fewer stops,
            // or the number of stops exceeds the limit.
            if (steps > stops[node] || steps > k + 1) {
                continue;
            }
            stops[node] = steps;
            if (node == dst) {
                return dist;
            }
            if (!adj.ContainsKey(node)) {
                continue;
            }
            foreach (int[] a in adj[node]) {
                var newDistance = new int[] { dist + a[1], a[0], steps + 1 };
                pq.Enqueue(newDistance, newDistance);
            }
        }
        return -1;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

700 200 500

C# || Daily Temperatures – How To Find The Number Of Days Until Warmer Temperature Using C#

March 01, 2023 admin No comments

The following is a module with functions which demonstrates how to find the number of days until warmer temperature using C#.

1. Daily Temperatures – Problem Statement

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i^th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73] Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60] Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90] Output: [1,1,0]

2. Daily Temperatures – Solution

The following is a solution which demonstrates how to find the number of days until warmer temperature.

This solution uses the monotonic stack approach.





		
		
			2. Daily Temperatures - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Mar 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find number of days until warmer temperature
// ============================================================================
public class Solution {
    public int[] DailyTemperatures(int[] temperatures) {
        // Stack used to save the array index of each item
        var stack = new Stack<int>();
        var result = new int[temperatures.Length];

        // Go through items in the array
        for (int currentIndex = 0; currentIndex < temperatures.Length; ++currentIndex) {
            // Compare the item at the top of the stack to the current array item.
            // If the item at the top of stack is less than current array item,
            // save the distance between the array indexes in the result array.
            while (stack.Count > 0 && temperatures[stack.Peek()] < temperatures[currentIndex]) {
                // Get the distance between the two array indexes
                var previousIndex = stack.Pop();
                result[previousIndex] = currentIndex - previousIndex;
            }
            // Save the array index for this item to the stack
            stack.Push(currentIndex);
        }
        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Mar 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find number of days until warmer temperature
// ============================================================================
public class Solution {
    public int[] DailyTemperatures(int[] temperatures) {
        // Stack used to save the array index of each item
        var stack = new Stack<int>();
        var result = new int[temperatures.Length];
 
        // Go through items in the array
        for (int currentIndex = 0; currentIndex < temperatures.Length; ++currentIndex) {
            // Compare the item at the top of the stack to the current array item.
            // If the item at the top of stack is less than current array item,
            // save the distance between the array indexes in the result array.
            while (stack.Count > 0 && temperatures[stack.Peek()] < temperatures[currentIndex]) {
                // Get the distance between the two array indexes
                var previousIndex = stack.Pop();
                result[previousIndex] = currentIndex - previousIndex;
            }
            // Save the array index for this item to the stack
            stack.Push(currentIndex);
        }
        return result;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[1,1,4,2,1,1,0,0] [1,1,1,0] [1,1,0]

C# || How To Find Maximum Difference Between Node and Ancestor In Binary Tree Using C#

February 14, 2023 admin No comments

The following is a module with functions which demonstrates how to find the maximum difference between node and ancestor in binary tree using C#.

1. Max Ancestor Diff – Problem Statement

Given the root of a binary tree, find the maximum value v for which there exist different nodes a and b where v = |a.val – b.val| and a is an ancestor of b.

A node a is an ancestor of b if either: any child of a is equal to b or any child of a is an ancestor of b.

Example 1:

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13] Output: 7 Explanation: We have various ancestor-node differences, some of which are given below : |8 - 3| = 5 |3 - 7| = 4 |8 - 1| = 7 |10 - 13| = 3 Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.

Example 2:

Input: root = [1,null,2,null,0,3] Output: 3

2. Max Ancestor Diff – Solution

The following is a solution which demonstrates how to find the maximum difference between node and ancestor in binary tree.





		
		
			2. Max Ancestor Diff - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Feb 14, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find maximum difference node and ancestor
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int MaxAncestorDiff(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Traverse(root, root.val, root.val);
    }

    public int Traverse(TreeNode node, int curMax, int curMin) {
        // if encounter leaves, return the max-min along the path
        if (node == null) {
            return curMax - curMin;
        }
        // else, update max and min
        // and return the max of left and right subtrees
        curMax = Math.Max(curMax, node.val);
        curMin = Math.Min(curMin, node.val);
        int left = Traverse(node.left, curMax, curMin);
        int right = Traverse(node.right, curMax, curMin);
        return Math.Max(left, right);
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Feb 14, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find maximum difference node and ancestor
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int MaxAncestorDiff(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Traverse(root, root.val, root.val);
    }
 
    public int Traverse(TreeNode node, int curMax, int curMin) {
        // if encounter leaves, return the max-min along the path
        if (node == null) {
            return curMax - curMin;
        }
        // else, update max and min
        // and return the max of left and right subtrees
        curMax = Math.Max(curMax, node.val);
        curMin = Math.Min(curMin, node.val);
        int left = Traverse(node.left, curMax, curMin);
        int right = Traverse(node.right, curMax, curMin);
        return Math.Max(left, right);
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

7 3

C# || How To Remove Stones To Minimize The Total Using C#

February 01, 2023 admin No comments

The following is a module with functions which demonstrates how to remove stones to minimize the total using C#.

1. Min Stone Sum – Problem Statement

You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the i^th pile, and an integer k. You should apply the following operation exactly k times:

Choose any piles[i] and remove floor(piles[i] / 2) stones from it.

Notice that you can apply the operation on the same pile more than once.

Return the minimum possible total number of stones remaining after applying the k operations.

floor(x) is the greatest integer that is smaller than or equal to x (i.e., rounds x down).

Example 1:

Input: piles = [5,4,9], k = 2 Output: 12 Explanation: Steps of a possible scenario are: - Apply the operation on pile 2. The resulting piles are [5,4,5]. - Apply the operation on pile 0. The resulting piles are [3,4,5]. The total number of stones in [3,4,5] is 12.

Example 2:

Input: piles = [4,3,6,7], k = 3 Output: 12 Explanation: Steps of a possible scenario are: - Apply the operation on pile 2. The resulting piles are [4,3,3,7]. - Apply the operation on pile 3. The resulting piles are [4,3,3,4]. - Apply the operation on pile 0. The resulting piles are [2,3,3,4]. The total number of stones in [2,3,3,4] is 12.

2. Min Stone Sum – Solution

The following is a solution which demonstrates how to remove stones to minimize the total.





		
		
			2. Min Stone Sum - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Feb 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to remove stones to minimize the total
// ============================================================================
public class Solution {
    public int MinStoneSum(int[] piles, int k) {
        var heap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
        int totalSum = 0;

        foreach (int num in piles) {
            heap.Enqueue(num, num);
            totalSum += num;
        }

        for (int index = 0; index < k; ++index) {
            int currentValue = heap.Dequeue();
            int removeFromTotal = currentValue / 2;
            int newValue = currentValue - removeFromTotal;
            heap.Enqueue(newValue, newValue);
            totalSum -= removeFromTotal;
        }

        return totalSum;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Feb 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to remove stones to minimize the total
// ============================================================================
public class Solution {
    public int MinStoneSum(int[] piles, int k) {
        var heap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
        int totalSum = 0;
 
        foreach (int num in piles) {
            heap.Enqueue(num, num);
            totalSum += num;
        }
 
        for (int index = 0; index < k; ++index) {
            int currentValue = heap.Dequeue();
            int removeFromTotal = currentValue / 2;
            int newValue = currentValue - removeFromTotal;
            heap.Enqueue(newValue, newValue);
            totalSum -= removeFromTotal;
        }
 
        return totalSum;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

12 12

C# || Single-Threaded CPU – How To Find The Order CPU Will Process Tasks Using C#

January 27, 2023 admin No comments

The following is a module with functions which demonstrates how to find the order CPU will process tasks using C#.

1. Get Order – Problem Statement

You are given n tasks labeled from 0 to n – 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTime_i, processingTime_i] means that the i^th task will be available to process at enqueueTime_i and will take processingTime_ito finish processing.

You have a single-threaded CPU that can process at most one task at a time and will act in the following way:

If the CPU is idle and there are no available tasks to process, the CPU remains idle.
If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
Once a task is started, the CPU will process the entire task without stopping.
The CPU can finish a task then start a new one instantly.

Return the order in which the CPU will process the tasks.

Example 1:

Input: tasks = [[1,2],[2,4],[3,2],[4,1]] Output: [0,2,3,1] Explanation: The events go as follows: - At time = 1, task 0 is available to process. Available tasks = {0}. - Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}. - At time = 2, task 1 is available to process. Available tasks = {1}. - At time = 3, task 2 is available to process. Available tasks = {1, 2}. - Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}. - At time = 4, task 3 is available to process. Available tasks = {1, 3}. - At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}. - At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}. - At time = 10, the CPU finishes task 1 and becomes idle.

Example 2:

Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]] Output: [4,3,2,0,1] Explanation: The events go as follows: - At time = 7, all the tasks become available. Available tasks = {0,1,2,3,4}. - Also at time = 7, the idle CPU starts processing task 4. Available tasks = {0,1,2,3}. - At time = 9, the CPU finishes task 4 and starts processing task 3. Available tasks = {0,1,2}. - At time = 13, the CPU finishes task 3 and starts processing task 2. Available tasks = {0,1}. - At time = 18, the CPU finishes task 2 and starts processing task 0. Available tasks = {1}. - At time = 28, the CPU finishes task 0 and starts processing task 1. Available tasks = {}. - At time = 40, the CPU finishes task 1 and becomes idle.

2. Get Order – Solution

The following is a solution which demonstrates how to find the order CPU will process tasks.





		
		
			2. Get Order - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 27, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the order CPU will process tasks
// ============================================================================
public class Solution {
    private const int ENQUEUE_TIME = 0;
    private const int PROCESSING_TIME = 1;
    private const int INDEX = 2;

    public int[] GetOrder(int[][] tasks) {
        // Sort based on min task processing time or min task index.
        // Store enqueue time, processing time, task index.
        var nextTask = new PriorityQueue<int[], int[]>(Comparer<int[]>.Create((a, b) => (a[PROCESSING_TIME] != b[PROCESSING_TIME] ? (a[PROCESSING_TIME] - b[PROCESSING_TIME]) : (a[INDEX] - b[INDEX]))));

        // Store task enqueue time, processing time, index.
        int[][] sortedTasks = new int[tasks.Length][];
        for (int index = 0; index < sortedTasks.Length; ++index) {
            sortedTasks[index] = new int[3];
        }
        for (int index = 0; index < tasks.Length; ++index) {
            sortedTasks[index][ENQUEUE_TIME] = tasks[index][ENQUEUE_TIME];
            sortedTasks[index][PROCESSING_TIME] = tasks[index][PROCESSING_TIME];
            sortedTasks[index][INDEX] = index;
        }

        Array.Sort(sortedTasks, (a, b) => a[ENQUEUE_TIME] - b[ENQUEUE_TIME]);
        int[] tasksProcessingOrder = new int[tasks.Length];

        long currentTime = 0;
        int taskIndex = 0;
        int ansIndex = 0;

        // Stop when no tasks are left in array and heap.
        while (taskIndex < tasks.Length || nextTask.Count > 0) {
            if (nextTask.Count == 0 && currentTime < sortedTasks[taskIndex][ENQUEUE_TIME]) {
                // When the heap is empty, try updating currentTime to next task's enqueue time.
                currentTime = sortedTasks[taskIndex][ENQUEUE_TIME];
            }

            // Push all the tasks whose enqueueTime <= currtTime into the heap.
            while (taskIndex < tasks.Length && currentTime >= sortedTasks[taskIndex][ENQUEUE_TIME]) {
                nextTask.Enqueue(sortedTasks[taskIndex], sortedTasks[taskIndex]);
                ++taskIndex;
            }

            int[] task = nextTask.Dequeue();
            int processTime = task[PROCESSING_TIME];
            int index = task[INDEX];

            // Complete this task and increment currentTime.
            currentTime += processTime;
            tasksProcessingOrder[ansIndex++] = index;
        }

        return tasksProcessingOrder;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 27, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the order CPU will process tasks
// ============================================================================
public class Solution {
    private const int ENQUEUE_TIME = 0;
    private const int PROCESSING_TIME = 1;
    private const int INDEX = 2;
 
    public int[] GetOrder(int[][] tasks) {
        // Sort based on min task processing time or min task index.
        // Store enqueue time, processing time, task index.
        var nextTask = new PriorityQueue<int[], int[]>(Comparer<int[]>.Create((a, b) => (a[PROCESSING_TIME] != b[PROCESSING_TIME] ? (a[PROCESSING_TIME] - b[PROCESSING_TIME]) : (a[INDEX] - b[INDEX]))));
 
        // Store task enqueue time, processing time, index.
        int[][] sortedTasks = new int[tasks.Length][];
        for (int index = 0; index < sortedTasks.Length; ++index) {
            sortedTasks[index] = new int[3];
        }
        for (int index = 0; index < tasks.Length; ++index) {
            sortedTasks[index][ENQUEUE_TIME] = tasks[index][ENQUEUE_TIME];
            sortedTasks[index][PROCESSING_TIME] = tasks[index][PROCESSING_TIME];
            sortedTasks[index][INDEX] = index;
        }
 
        Array.Sort(sortedTasks, (a, b) => a[ENQUEUE_TIME] - b[ENQUEUE_TIME]);
        int[] tasksProcessingOrder = new int[tasks.Length];
 
        long currentTime = 0;
        int taskIndex = 0;
        int ansIndex = 0;
 
        // Stop when no tasks are left in array and heap.
        while (taskIndex < tasks.Length || nextTask.Count > 0) {
            if (nextTask.Count == 0 && currentTime < sortedTasks[taskIndex][ENQUEUE_TIME]) {
                // When the heap is empty, try updating currentTime to next task's enqueue time.
                currentTime = sortedTasks[taskIndex][ENQUEUE_TIME];
            }
 
            // Push all the tasks whose enqueueTime <= currtTime into the heap.
            while (taskIndex < tasks.Length && currentTime >= sortedTasks[taskIndex][ENQUEUE_TIME]) {
                nextTask.Enqueue(sortedTasks[taskIndex], sortedTasks[taskIndex]);
                ++taskIndex;
            }
 
            int[] task = nextTask.Dequeue();
            int processTime = task[PROCESSING_TIME];
            int index = task[INDEX];
 
            // Complete this task and increment currentTime.
            currentTime += processTime;
            tasksProcessingOrder[ansIndex++] = index;
        }
 
        return tasksProcessingOrder;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[0,2,3,1] [4,3,2,0,1]

Tag Archives: leetcode

C# || How To Find Largest Value In Each Binary Tree Row Using C#

C# || How To Find The Minimum Speed To Arrive On Time Using C#

C# || How To Find The Minimum ASCII Delete Sum for Two Strings Using C#

C# || Fruit Into Baskets – How To Find The Maximum Number Of Fruits Using C#

C# || How To Find The Minimum Rounds To Complete All Tasks Using C#

C# || How To Design A Least Frequently Used (LFU) Cache Using C#

C# || How To Find The Minimum Fuel Cost To Report To The Capital Using C#

C# || How To Find The Minimum Time To Collect All Apples In A Tree Using C#

C# || How To Sort An Array O(nlog(n)) Using C#

C# || How To Find The Cheapest Flights Within K Stops Using C#

C# || Daily Temperatures – How To Find The Number Of Days Until Warmer Temperature Using C#

C# || How To Find Maximum Difference Between Node and Ancestor In Binary Tree Using C#

C# || How To Remove Stones To Minimize The Total Using C#

C# || Single-Threaded CPU – How To Find The Order CPU Will Process Tasks Using C#

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories