leetcode – Page 3 – My Programming Notes

Tag Archives: leetcode

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]

C# || How To Determine If String Halves Are Alike Using C#

January 02, 2023 admin No comments

The following is a module with functions which demonstrates how to determine if string halves are alike using C#.

1. Halves Are A like – Problem Statement

You are given a string s of even length. Split this string into two halves of equal lengths, and let a be the first half and b be the second half.

Two strings are alike if they have the same number of vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’, ‘A’, ‘E’, ‘I’, ‘O’, ‘U’). Notice that s contains uppercase and lowercase letters.

Return true if a and b are alike. Otherwise, return false.

Example 1:

Input: s = "book" Output: true Explanation: a = "bo" and b = "ok". a has 1 vowel and b has 1 vowel. Therefore, they are alike.

Example 2:

Input: s = "textbook" Output: false Explanation: a = "text" and b = "book". a has 1 vowel whereas b has 2. Therefore, they are not alike. Notice that the vowel o is counted twice.

2. Halves Are A like – Solution

The following is a solution which demonstrates how to determine if string halves are alike.





		
		
			2. Halves Are A like - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 2, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to determine if string halves are alike
// ============================================================================
public class Solution {
    public bool HalvesAreAlike(string s) {
        // Get first half count
        int firstHalfVowel = 0;
        for (int index = 0; index < s.Length / 2; ++index) {
            if (IsVowel(s[index])) {
                ++firstHalfVowel;
            }
        }

        // Get second half count
        int secondHalfVowel = 0;
        for (int index = s.Length / 2 ; index < s.Length && secondHalfVowel <= firstHalfVowel; ++index) {
            if (IsVowel(s[index])) {
                ++secondHalfVowel;
            }
        }
        return firstHalfVowel == secondHalfVowel;
    }

    private static bool IsVowel(char ch) {
        ch = char.ToLower(ch);
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
    }
}// 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 2, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to determine if string halves are alike
// ============================================================================
public class Solution {
    public bool HalvesAreAlike(string s) {
        // Get first half count
        int firstHalfVowel = 0;
        for (int index = 0; index < s.Length / 2; ++index) {
            if (IsVowel(s[index])) {
                ++firstHalfVowel;
            }
        }
 
        // Get second half count
        int secondHalfVowel = 0;
        for (int index = s.Length / 2 ; index < s.Length && secondHalfVowel <= firstHalfVowel; ++index) {
            if (IsVowel(s[index])) {
                ++secondHalfVowel;
            }
        }
        return firstHalfVowel == secondHalfVowel;
    }
 
    private static bool IsVowel(char ch) {
        ch = char.ToLower(ch);
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
    }
}// 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:

true false

C# || How To Find The Maximum Profit In Job Scheduling Using C#

January 01, 2023 admin No comments

The following is a module with functions which demonstrates how to find the maximum profit in job scheduling using C#.

1. Job Scheduling – Problem Statement

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70] Output: 120 Explanation: The subset chosen is the first and fourth job. Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60] Output: 150 Explanation: The subset chosen is the first, fourth and fifth job. Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4] Output: 6

2. Job Scheduling – Solution

The following is a solution which demonstrates how to find the maximum profit in job scheduling.





		
		
			2. Job Scheduling - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find maximum profit in job scheduling
// ============================================================================
public class Solution {
    public int JobScheduling(int[] startTime, int[] endTime, int[] profit) {
        if (startTime == null || startTime.Length == 0) {
            return 0;
        }

        var jobs = new List<Job>();
        for (int index = 0; index < startTime.Length; ++index) {
            jobs.Add(new Job(startTime[index], endTime[index], profit[index]));
        }

        jobs.Sort((a, b) => a.Start - b.Start);

        return DFS(jobs, 0, new Dictionary<int, int>());
    }

    private int DFS(List<Job> jobs, int currentJobIndex, Dictionary<int, int> maxProfits) {
        if (currentJobIndex >= jobs.Count) {
            return 0;
        }

        if (maxProfits.ContainsKey(currentJobIndex)) {
            return maxProfits[currentJobIndex];
        }

        int next = BinarySearch(jobs, currentJobIndex);
        int inc = jobs[currentJobIndex].Profit + (next == -1 ? 0 : DFS(jobs, next, maxProfits));
        int exc = DFS(jobs, currentJobIndex + 1, maxProfits);

        int maxProfit = Math.Max(inc, exc);
        maxProfits[currentJobIndex] =  maxProfit;
        return maxProfit;
    }

    private int BinarySearch(List<Job> jobs, int currentJobIndex) {
        int lo = currentJobIndex;
        int high = jobs.Count - 1;
        int result = -1;

        while (lo <= high) {
            int mid = lo + (high - lo) / 2;

            if (jobs[currentJobIndex].End <= jobs[mid].Start) {
                result = mid;
                high = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return result;
    }

    class Job {
        public int Start { get; set; }
        public int End { get; set; }
        public int Profit { get; set; }

        public Job(int startTime, int endTime, int profit) {
            Start = startTime;
            End = endTime;
            Profit = profit;
        }
    }
}// 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find maximum profit in job scheduling
// ============================================================================
public class Solution {
    public int JobScheduling(int[] startTime, int[] endTime, int[] profit) {
        if (startTime == null || startTime.Length == 0) {
            return 0;
        }
 
        var jobs = new List<Job>();
        for (int index = 0; index < startTime.Length; ++index) {
            jobs.Add(new Job(startTime[index], endTime[index], profit[index]));
        }
 
        jobs.Sort((a, b) => a.Start - b.Start);
 
        return DFS(jobs, 0, new Dictionary<int, int>());
    }
 
    private int DFS(List<Job> jobs, int currentJobIndex, Dictionary<int, int> maxProfits) {
        if (currentJobIndex >= jobs.Count) {
            return 0;
        }
 
        if (maxProfits.ContainsKey(currentJobIndex)) {
            return maxProfits[currentJobIndex];
        }
 
        int next = BinarySearch(jobs, currentJobIndex);
        int inc = jobs[currentJobIndex].Profit + (next == -1 ? 0 : DFS(jobs, next, maxProfits));
        int exc = DFS(jobs, currentJobIndex + 1, maxProfits);
 
        int maxProfit = Math.Max(inc, exc);
        maxProfits[currentJobIndex] =  maxProfit;
        return maxProfit;
    }
 
    private int BinarySearch(List<Job> jobs, int currentJobIndex) {
        int lo = currentJobIndex;
        int high = jobs.Count - 1;
        int result = -1;
 
        while (lo <= high) {
            int mid = lo + (high - lo) / 2;
 
            if (jobs[currentJobIndex].End <= jobs[mid].Start) {
                result = mid;
                high = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return result;
    }
 
    class Job {
        public int Start { get; set; }
        public int End { get; set; }
        public int Profit { get; set; }
 
        public Job(int startTime, int endTime, int profit) {
            Start = startTime;
            End = endTime;
            Profit = profit;
        }
    }
}// 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:

120 150 6

C# || Contains Duplicate II – How To Determine Two Distinct Indices In Array Equal To Target Value Using C#

December 25, 2022 admin No comments

The following is a module with functions which demonstrates how to determine two distinct indices in array equal to target value using C#.

1. Contains Nearby Duplicate – Problem Statement

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i – j) <= k.

Example 1:

Input: nums = [1,2,3,1], k = 3 Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1 Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2 Output: false

2. Contains Nearby Duplicate – Solution

The following are two solutions which demonstrates how to determine two distinct indices in array equal to target value.





		
		
			2. Contains Nearby Duplicate - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 25, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to determine two indices equal to target value
// ============================================================================
public class Solution {
    public bool ContainsNearbyDuplicate(int[] nums, int k) {
        var set = new HashSet<int>();
        for (int index = 0; index < nums.Length; ++index){
            if (index > k) {
                set.Remove(nums[index - k - 1]);
            }
            if (!set.Add(nums[index])) {
                return true;
            }
        }
        return false;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 25, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to determine two indices equal to target value
// ============================================================================
public class Solution {
    public bool ContainsNearbyDuplicate(int[] nums, int k) {
        var set = new HashSet<int>();
        for (int index = 0; index < nums.Length; ++index){
            if (index > k) {
                set.Remove(nums[index - k - 1]);
            }
            if (!set.Add(nums[index])) {
                return true;
            }
        }
        return false;
    }
}// 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:

true true false

C# || How To Find The Nearest Exit From Entrance In Maze Using C#

December 01, 2022 admin No comments

The following is a module with functions which demonstrates how to find the nearest exit from the entrance in a maze using C#.

1. Nearest Exit – Problem Statement

You are given an m x n matrix maze (0-indexed) with empty cells (represented as ‘.’) and walls (represented as ‘+’). You are also given the entrance of the maze, where entrance = [entrance_row, entrance_col] denotes the row and column of the cell you are initially standing at.

In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.

Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.

Example 1:

Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2] Output: 1 Explanation: There are 3 exits in this maze at [1,0], [0,2], and [2,3]. Initially, you are at the entrance cell [1,2]. - You can reach [1,0] by moving 2 steps left. - You can reach [0,2] by moving 1 step up. It is impossible to reach [2,3] from the entrance. Thus, the nearest exit is [0,2], which is 1 step away.

Example 2:

Input: maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0] Output: 2 Explanation: There is 1 exit in this maze at [1,2]. [1,0] does not count as an exit since it is the entrance cell. Initially, you are at the entrance cell [1,0]. - You can reach [1,2] by moving 2 steps right. Thus, the nearest exit is [1,2], which is 2 steps away.

Example 3:

Input: maze = [[".","+"]], entrance = [0,0] Output: -1 Explanation: There are no exits in this maze.

2. Nearest Exit – Solution

The following is a solution which demonstrates how find the nearest exit from the entrance in a maze.





		
		
			2. Nearest Exit - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 1, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find nearest exit from entrance in maze
// ============================================================================
public class Solution {
    public int NearestExit(char[][] maze, int[] entrance) {
        int rows = maze.Length;
        int cols = maze[0].Length;
        var directions = new List<KeyValuePair<int, int>>() {
            // Direction coordinates: (y, x)
            new KeyValuePair<int, int>(1, 0),
            new KeyValuePair<int, int>(-1, 0),
            new KeyValuePair<int, int>(0, 1),
            new KeyValuePair<int, int>(0, -1)
        };
        char VISITED = '+';
        char NOT_VISITED = '.';

        // Mark the entrance as visited since its not a exit.
        int startRow = entrance[0];
        int startCol = entrance[1];
        maze[startRow][startCol] = VISITED;

        // Start BFS from the entrance, and use a queue `queue` to store all
        // the cells to be visited.
        var queue = new Queue<int[]>();
        queue.Enqueue(new int[]{startRow, startCol, 0});

        while (queue.Count > 0) {
            int[] currState = queue.Dequeue();
            int currRow = currState[0];
            int currCol = currState[1];
            int currDistance = currState[2];

            // For the current cell, check its four neighbor cells.
            foreach (var dir in directions) {
                int nextRow = currRow + dir.Key;
                int nextCol = currCol + dir.Value;

                // If there exists an unvisited empty neighbor:
                if (IsValidCell(maze, nextRow, nextCol) && maze[nextRow][nextCol] == NOT_VISITED) {
                    // If this empty cell is an exit, return distance + 1.
                    if (nextRow == 0 || nextRow == rows - 1 || nextCol == 0 || nextCol == cols - 1) {
                        return currDistance + 1;
                    }

                    // Otherwise, add this cell to 'queue' and mark it as visited.
                    maze[nextRow][nextCol] = VISITED;
                    queue.Enqueue(new int[]{nextRow, nextCol, currDistance + 1});
                }
            }
        }

        // If we finish iterating without finding an exit, return -1.
        return -1;
    }

    private bool IsValidCell(char[][] grid, int row, int col) {
        return row >= 0 && row < grid.Length && col >= 0 && col < grid[row].Length;
    }
}// 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 1, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find nearest exit from entrance in maze
// ============================================================================
public class Solution {
    public int NearestExit(char[][] maze, int[] entrance) {
        int rows = maze.Length;
        int cols = maze[0].Length;
        var directions = new List<KeyValuePair<int, int>>() {
            // Direction coordinates: (y, x)
            new KeyValuePair<int, int>(1, 0),
            new KeyValuePair<int, int>(-1, 0),
            new KeyValuePair<int, int>(0, 1),
            new KeyValuePair<int, int>(0, -1)
        };
        char VISITED = '+';
        char NOT_VISITED = '.';
 
        // Mark the entrance as visited since its not a exit.
        int startRow = entrance[0];
        int startCol = entrance[1];
        maze[startRow][startCol] = VISITED;
 
        // Start BFS from the entrance, and use a queue `queue` to store all
        // the cells to be visited.
        var queue = new Queue<int[]>();
        queue.Enqueue(new int[]{startRow, startCol, 0});
 
        while (queue.Count > 0) {
            int[] currState = queue.Dequeue();
            int currRow = currState[0];
            int currCol = currState[1];
            int currDistance = currState[2];
 
            // For the current cell, check its four neighbor cells.
            foreach (var dir in directions) {
                int nextRow = currRow + dir.Key;
                int nextCol = currCol + dir.Value;
 
                // If there exists an unvisited empty neighbor:
                if (IsValidCell(maze, nextRow, nextCol) && maze[nextRow][nextCol] == NOT_VISITED) {
                    // If this empty cell is an exit, return distance + 1.
                    if (nextRow == 0 || nextRow == rows - 1 || nextCol == 0 || nextCol == cols - 1) {
                        return currDistance + 1;
                    }
 
                    // Otherwise, add this cell to 'queue' and mark it as visited.
                    maze[nextRow][nextCol] = VISITED;
                    queue.Enqueue(new int[]{nextRow, nextCol, currDistance + 1});
                }
            }
        }
 
        // If we finish iterating without finding an exit, return -1.
        return -1;
    }
 
    private bool IsValidCell(char[][] grid, int row, int col) {
        return row >= 0 && row < grid.Length && col >= 0 && col < grid[row].Length;
    }
}// 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 -1

C# || How To Design A Time Based Key-Value Store To Retrieve Timestamps Using C#

November 01, 2022 admin No comments

The following is a module with functions which demonstrates how to design a time based key-value store to retrieve timestamps using C#.

1. Time Map – Problem Statement

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key’s value at a certain timestamp.

Implement the TimeMap class:

TimeMap() Initializes the object of the data structure.
void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns “”.

Example 1:

Input ["TimeMap", "set", "get", "get", "set", "get", "get"] [[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]] Output [null, null, "bar", "bar", null, "bar2", "bar2"]
Explanation TimeMap timeMap = new TimeMap(); timeMap.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1. timeMap.get("foo", 1); // return "bar" timeMap.get("foo", 3); // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar". timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4. timeMap.get("foo", 4); // return "bar2" timeMap.get("foo", 5); // return "bar2"

2. Time Map – Solution

The following is a solution which demonstrates how to design a time based key-value store to retrieve timestamps.





		
		
			2. Time Map - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 1, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to design a time map
// ============================================================================
/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.Set(key,value,timestamp);
 * string param_2 = obj.Get(key,timestamp);
 */
public class TimeMap {
    private class Data {
        public string value;
        public int timestamp;
        public Data(string value, int timestamp) {
            this.value = value;
            this.timestamp = timestamp;
        }
    }

    private Dictionary<string, List<Data>> map;

    public TimeMap() {
        map = new Dictionary<string, List<Data>>();
    }

    public void Set(string key, string value, int timestamp) {
        if (!map.ContainsKey(key)) {
            map.Add(key, new List<Data>());
        }
        map[key].Add(new Data(value, timestamp));
    }

    public string Get(string key, int timestamp) {
        if (!map.ContainsKey(key)) {
             return "";
        }
        return BinarySearch(map[key], timestamp);
    }
    
    string BinarySearch(List<Data> bucket, int target) {
        int low = 0, high = bucket.Count;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (bucket[mid].timestamp <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (high == 0) {
            return "";
        }
        return (bucket[high - 1].timestamp <= target) ? bucket[high - 1].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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 1, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to design a time map
// ============================================================================
/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.Set(key,value,timestamp);
 * string param_2 = obj.Get(key,timestamp);
 */
public class TimeMap {
    private class Data {
        public string value;
        public int timestamp;
        public Data(string value, int timestamp) {
            this.value = value;
            this.timestamp = timestamp;
        }
    }
 
    private Dictionary<string, List<Data>> map;
 
    public TimeMap() {
        map = new Dictionary<string, List<Data>>();
    }
 
    public void Set(string key, string value, int timestamp) {
        if (!map.ContainsKey(key)) {
            map.Add(key, new List<Data>());
        }
        map[key].Add(new Data(value, timestamp));
    }
 
    public string Get(string key, int timestamp) {
        if (!map.ContainsKey(key)) {
             return "";
        }
        return BinarySearch(map[key], timestamp);
    }
    
    string BinarySearch(List<Data> bucket, int target) {
        int low = 0, high = bucket.Count;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (bucket[mid].timestamp <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (high == 0) {
            return "";
        }
        return (bucket[high - 1].timestamp <= target) ? bucket[high - 1].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,"bar","bar",null,"bar2","bar2"]

C# || How To Return The Top K Frequent Words In Array Of Strings Using C#

October 23, 2022 admin No comments

The following is a module with functions which demonstrates how to get the top K frequent words in an array of strings using C#.

1. Top K Frequent – Problem Statement

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Example 1:

Input: words = ["i","love","leetcode","i","love","coding"], k = 2 Output: ["i","love"] Explanation: "i" and "love" are the two most frequent words. Note that "i" comes before "love" due to a lower alphabetical order.

Example 2:

Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4 Output: ["the","is","sunny","day"] Explanation: "the", "is", "sunny" and "day" are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.

2. Top K Frequent – Solution

The following are two solutions which demonstrates how to get the top K frequent words in an array of strings.





		
		
			2. Top K Frequent - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 23, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Determines how to get the top K frequent words in array
// ============================================================================
public class Solution {
    public IList<string> TopKFrequent(string[] words, int k) {
        // Use a map to get the frequency of each word
        var frequency = new Dictionary<string, int>();
        foreach (var word in words) {
            frequency[word] = frequency.GetValueOrDefault(word, 0) + 1;
        }

        // Get the frequency map as a list and sort
        var frequencyList = frequency.ToList();
        frequencyList.Sort((a, b) => {
            // If words have the same frequency, sort
            // by their lexicographical order
            if (a.Value == b.Value) {
                return string.Compare(a.Key, b.Key);
            }
            // Sort by the frequency from highest to lowest
            return b.Value - a.Value;
        });

        // Get the results
        var result = new List<string>();
        for (int index = 0; index < frequencyList.Count; ++index) {
            result.Add(frequencyList[index].Key);
            if (result.Count == k) {
                break;
            }
        }
        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
30
31
32
33
34
35
36
37
38
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 23, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Determines how to get the top K frequent words in array
// ============================================================================
public class Solution {
    public IList<string> TopKFrequent(string[] words, int k) {
        // Use a map to get the frequency of each word
        var frequency = new Dictionary<string, int>();
        foreach (var word in words) {
            frequency[word] = frequency.GetValueOrDefault(word, 0) + 1;
        }
 
        // Get the frequency map as a list and sort
        var frequencyList = frequency.ToList();
        frequencyList.Sort((a, b) => {
            // If words have the same frequency, sort
            // by their lexicographical order
            if (a.Value == b.Value) {
                return string.Compare(a.Key, b.Key);
            }
            // Sort by the frequency from highest to lowest
            return b.Value - a.Value;
        });
 
        // Get the results
        var result = new List<string>();
        for (int index = 0; index < frequencyList.Count; ++index) {
            result.Add(frequencyList[index].Key);
            if (result.Count == k) {
                break;
            }
        }
        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:

["i","love"] ["the","is","sunny","day"]

C# || Two Sum IV – How To Get Two Numbers In Binary Search Tree Equal To Target Value Using C#

October 09, 2022 admin No comments

The following is a module with functions which demonstrates how to get two numbers in a binary search tree equal to target value using C#.

1. Find Target – Problem Statement

Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9 Output: true

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28 Output: false

2. Find Target – Solution

The following are two solutions which demonstrates how to get two numbers in a binary search tree equal to target value.

Both solutions use a set to keep track of the items already seen.

Each time a new node is encountered, we subtract the target value from the current node value. If the difference amount from subtracting the two numbers exists in the set, a 2 sum combination exists in the tree

1. Recursive

The following solution uses Depth First Search when looking for the target value.





		
		
			2. Find Target - Solution - Recursive
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 9, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public bool FindTarget(TreeNode root, int k) {
        return Traverse(root, k, new HashSet<int>());
    }

    private bool Traverse(TreeNode node, int k, HashSet<int> seen) {
        if (node == null) {
            return false;
        }
        // Get remaining value
        var remaining = k - node.val;

        // Check if remaining value has been seen
        if (seen.Contains(remaining)) {
            return true;
        }
        // Add current node value to items seen
        seen.Add(node.val);

        // Keep traversing left and right looking for 2 sum
        return Traverse(node.left, k, seen) || Traverse(node.right, k, seen);
    }
}// 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 9, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public bool FindTarget(TreeNode root, int k) {
        return Traverse(root, k, new HashSet<int>());
    }
 
    private bool Traverse(TreeNode node, int k, HashSet<int> seen) {
        if (node == null) {
            return false;
        }
        // Get remaining value
        var remaining = k - node.val;
 
        // Check if remaining value has been seen
        if (seen.Contains(remaining)) {
            return true;
        }
        // Add current node value to items seen
        seen.Add(node.val);
 
        // Keep traversing left and right looking for 2 sum
        return Traverse(node.left, k, seen) || Traverse(node.right, k, seen);
    }
}// http://programmingnotes.org/

2. Iterative

The following solution uses Breadth First Search when looking for the target value.





		
		
			2. Find Target - Solution - Iterative
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 9, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public bool FindTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        // Declare stack
        var stack = new Stack<TreeNode>();

        // Keep track of values seen
        var seen = new HashSet<int>();

        // Add root to stack
        stack.Push(root);

        // Loop through items on the stack
        while (stack.Count > 0) {
            // Get current node
            var node = stack.Pop();

            // Get remaining value
            var remaining = k - node.val;

            // Check if remaining value has been seen
            if (seen.Contains(remaining)) {
                return true;
            } else {
                // Keep traversing left and right looking for 2 sum
                if (node.left != null) {
                    stack.Push(node.left);
                }
                if (node.right != null) {
                    stack.Push(node.right);
                }
            }
            // Add current node value to items seen
            seen.Add(node.val);
        }
        return false;
    }
}// 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 9, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public bool FindTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        // Declare stack
        var stack = new Stack<TreeNode>();
 
        // Keep track of values seen
        var seen = new HashSet<int>();
 
        // Add root to stack
        stack.Push(root);
 
        // Loop through items on the stack
        while (stack.Count > 0) {
            // Get current node
            var node = stack.Pop();
 
            // Get remaining value
            var remaining = k - node.val;
 
            // Check if remaining value has been seen
            if (seen.Contains(remaining)) {
                return true;
            } else {
                // Keep traversing left and right looking for 2 sum
                if (node.left != null) {
                    stack.Push(node.left);
                }
                if (node.right != null) {
                    stack.Push(node.right);
                }
            }
            // Add current node value to items seen
            seen.Add(node.val);
        }
        return false;
    }
}// 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:

true false

C# || Counting Bits – How To Return The Number Of 1’s In Binary Representation Of X Using C#

October 02, 2022 admin No comments

The following is a module with functions which demonstrates how to return the number of 1’s in binary representation of X using C#.

1. Count Bits – Problem Statement

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1‘s in the binary representation of i.

Example 1:

Input: n = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10

Example 2:

Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101

2. Count Bits – Solution

The following is a solution which demonstrates how return the number of 1’s in binary representation of X.

In this problem, we can see a pattern start to form.

When the current n is even, we can get the answer by dividing by 2 (e.g result[n] = result[n / 2])

When the current n is odd, we can get the answer by getting the result at previous index and adding 1 (e.g result[n] = result[n – 1] + 1)





		
		
			2. Level Order - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 2, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to return binary representation of X
// ============================================================================
public class Solution {
    public int[] CountBits(int n) {
        var result = new int[n + 1];
        result[0] = 0;

        for (int index = 1; index < result.Length; ++index) {
            if (index % 2 == 0) {
                result[index] = result[index / 2];
            } else {
                result[index] = result[index - 1] + 1;
            }
        }
        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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 2, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to return binary representation of X
// ============================================================================
public class Solution {
    public int[] CountBits(int n) {
        var result = new int[n + 1];
        result[0] = 0;
 
        for (int index = 1; index < result.Length; ++index) {
            if (index % 2 == 0) {
                result[index] = result[index / 2];
            } else {
                result[index] = result[index - 1] + 1;
            }
        }
        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:

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

Tag Archives: leetcode

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#

C# || How To Determine If String Halves Are Alike Using C#

C# || How To Find The Maximum Profit In Job Scheduling Using C#

C# || Contains Duplicate II – How To Determine Two Distinct Indices In Array Equal To Target Value Using C#

C# || How To Find The Nearest Exit From Entrance In Maze Using C#

C# || How To Design A Time Based Key-Value Store To Retrieve Timestamps Using C#

C# || How To Return The Top K Frequent Words In Array Of Strings Using C#

C# || Two Sum IV – How To Get Two Numbers In Binary Search Tree Equal To Target Value Using C#

C# || Counting Bits – How To Return The Number Of 1’s In Binary Representation Of X Using C#

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories