leetcode – My Programming Notes

Tag Archives: leetcode

C# || How To Find Mode In Binary Search Tree Using C#

October 01, 2024 admin No comments

The following is a module with functions which demonstrates how to find mode in binary search tree using C#.

1. Find Mode – Problem Statement

Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.

If the tree has more than one mode, return them in any order.

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.

Example 1:

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

Example 2:

Input: root = [0] Output: [0]

2. Find Mode – Solution

The following is a solution which demonstrates how to find mode in binary search tree.





		
		
			2. Find Mode - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find mode in binary search tree
// ============================================================================
/**
 * 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[] FindMode(TreeNode root) {
        int maxStreak = 0;
        int currStreak = 0;
        int currNum = 0;
        var ans = new List<int>();

        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                // Find the friend
                TreeNode friend = curr.left;
                while (friend.right != null) {
                    friend = friend.right;
                }

                friend.right = curr;

                // Delete the edge after using it
                TreeNode left = curr.left;
                curr.left = null;
                curr = left;
            } else {
                // Handle the current node
                int num = curr.val;
                if (num == currNum) {
                    currStreak++;
                } else {
                    currStreak = 1;
                    currNum = num;
                }

                if (currStreak > maxStreak) {
                    ans = new List<int>();
                    maxStreak = currStreak;
                }

                if (currStreak == maxStreak) {
                    ans.Add(num);
                }

                curr = curr.right;
            }
        }


        int[] result = new int[ans.Count];
        for (int i = 0; i < ans.Count; i++) {
            result[i] = ans[i];
        }

        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
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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find mode in binary search tree
// ============================================================================
/**
 * 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[] FindMode(TreeNode root) {
        int maxStreak = 0;
        int currStreak = 0;
        int currNum = 0;
        var ans = new List<int>();
 
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                // Find the friend
                TreeNode friend = curr.left;
                while (friend.right != null) {
                    friend = friend.right;
                }
 
                friend.right = curr;
 
                // Delete the edge after using it
                TreeNode left = curr.left;
                curr.left = null;
                curr = left;
            } else {
                // Handle the current node
                int num = curr.val;
                if (num == currNum) {
                    currStreak++;
                } else {
                    currStreak = 1;
                    currNum = num;
                }
 
                if (currStreak > maxStreak) {
                    ans = new List<int>();
                    maxStreak = currStreak;
                }
 
                if (currStreak == maxStreak) {
                    ans.Add(num);
                }
 
                curr = curr.right;
            }
        }
 
 
        int[] result = new int[ans.Count];
        for (int i = 0; i < ans.Count; i++) {
            result[i] = ans[i];
        }
 
        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:

[2] [0]

C# || How To Find The Winner Of Array Game Using C#

September 01, 2024 admin No comments

The following is a module with functions which demonstrates how to find the winner of array game using C#.

1. Get Winner – Problem Statement

Given an integer array arr of distinct integers and an integer k.

A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of the game, we compare arr[0] with arr[1], the larger integer wins and remains at position 0, and the smaller integer moves to the end of the array. The game ends when an integer wins k consecutive rounds.

Return the integer which will win the game.

It is guaranteed that there will be a winner of the game.

Example 1:

Input: arr = [2,1,3,5,4,6,7], k = 2 Output: 5 Explanation: Let's see the rounds of the game: Round | arr | winner | win_count 1 | [2,1,3,5,4,6,7] | 2 | 1 2 | [2,3,5,4,6,7,1] | 3 | 1 3 | [3,5,4,6,7,1,2] | 5 | 1 4 | [5,4,6,7,1,2,3] | 5 | 2 So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

Example 2:

Input: arr = [3,2,1], k = 10 Output: 3 Explanation: 3 will win the first 10 rounds consecutively.

2. Get Winner – Solution

The following is a solution which demonstrates how to find the winner of array game.





		
		
			2. Get Winner - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Sep 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the winner of array game
// ============================================================================
public class Solution {
    public int GetWinner(int[] arr, int k) {
        int maxElement = arr[0];
        for (int index = 1; index < arr.Length; ++index) {
            maxElement = Math.Max(maxElement, arr[index]);
        }

        int curr = arr[0];
        int winstreak = 0;

        for (int index = 1; index < arr.Length; ++index) {
            int opponent = arr[index];

            if (curr > opponent) {
                ++winstreak;
            } else {
                curr = opponent;
                winstreak = 1;
            }

            if (winstreak == k || curr == maxElement) {
                return curr;
            }
        }

        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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Sep 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the winner of array game
// ============================================================================
public class Solution {
    public int GetWinner(int[] arr, int k) {
        int maxElement = arr[0];
        for (int index = 1; index < arr.Length; ++index) {
            maxElement = Math.Max(maxElement, arr[index]);
        }
 
        int curr = arr[0];
        int winstreak = 0;
 
        for (int index = 1; index < arr.Length; ++index) {
            int opponent = arr[index];
 
            if (curr > opponent) {
                ++winstreak;
            } else {
                curr = opponent;
                winstreak = 1;
            }
 
            if (winstreak == k || curr == maxElement) {
                return curr;
            }
        }
 
        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:

5 3

C# || How To Design Seat Reservation Manager Using C#

August 01, 2024 admin No comments

The following is a module with functions which demonstrates how to design a seat reservation manager using C#.

1. Seat Manager – Problem Statement

Design a system that manages the reservation state of n seats that are numbered from 1 to n.

Implement the SeatManager class:

SeatManager(int n) Initializes a SeatManager object that will manage n seats numbered from 1 to n. All seats are initially available.
int reserve() Fetches the smallest-numbered unreserved seat, reserves it, and returns its number.
void unreserve(int seatNumber) Unreserves the seat with the given seatNumber.

Example 1:

Input ["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"] [[5], [], [], [2], [], [], [], [], [5]] Output [null, 1, 2, null, 2, 3, 4, 5, null]
Explanation SeatManager seatManager = new SeatManager(5); // Initializes a SeatManager with 5 seats. seatManager.reserve(); // All seats are available, so return the lowest numbered seat, which is 1. seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2. seatManager.unreserve(2); // Unreserve seat 2, so now the available seats are [2,3,4,5]. seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2. seatManager.reserve(); // The available seats are [3,4,5], so return the lowest of them, which is 3. seatManager.reserve(); // The available seats are [4,5], so return the lowest of them, which is 4. seatManager.reserve(); // The only available seat is seat 5, so return 5. seatManager.unreserve(5); // Unreserve seat 5, so now the available seats are [5].

2. Seat Manager – Solution

The following is a solution which demonstrates how to design a seat reservation manager.





		
		
			2. Seat Manager - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Aug 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to design a seat reservation manager
// ============================================================================
/**
 * Your SeatManager object will be instantiated and called as such:
 * SeatManager obj = new SeatManager(n);
 * int param_1 = obj.Reserve();
 * obj.Unreserve(seatNumber);
 */
public class SeatManager {
    // Marker to point to unreserved seats.
    int marker;

    // Sorted set to store all unreserved seats.
    SortedSet<int> availableSeats;

    public SeatManager(int n) {
        // Set marker to the first unreserved seat.
        marker = 1;
        // Initialize the sorted set.
        availableSeats = new SortedSet<int>();
    }

    public int Reserve() {
        // If the sorted set has any element in it, then,
        // get the smallest-numbered unreserved seat from it.
        if (availableSeats.Count > 0) {
            int firstSeatNumber = availableSeats.First();
            availableSeats.Remove(firstSeatNumber);
            return firstSeatNumber;
        }

        // Otherwise, the marker points to the smallest-numbered seat.
        int seatNumber = marker;
        marker++;
        return seatNumber;
    }

    public void Unreserve(int seatNumber) {
        // Push the unreserved seat in the sorted set.
        availableSeats.Add(seatNumber);
    }
}// 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:   Aug 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to design a seat reservation manager
// ============================================================================
/**
 * Your SeatManager object will be instantiated and called as such:
 * SeatManager obj = new SeatManager(n);
 * int param_1 = obj.Reserve();
 * obj.Unreserve(seatNumber);
 */
public class SeatManager {
    // Marker to point to unreserved seats.
    int marker;
 
    // Sorted set to store all unreserved seats.
    SortedSet<int> availableSeats;
 
    public SeatManager(int n) {
        // Set marker to the first unreserved seat.
        marker = 1;
        // Initialize the sorted set.
        availableSeats = new SortedSet<int>();
    }
 
    public int Reserve() {
        // If the sorted set has any element in it, then,
        // get the smallest-numbered unreserved seat from it.
        if (availableSeats.Count > 0) {
            int firstSeatNumber = availableSeats.First();
            availableSeats.Remove(firstSeatNumber);
            return firstSeatNumber;
        }
 
        // Otherwise, the marker points to the smallest-numbered seat.
        int seatNumber = marker;
        marker++;
        return seatNumber;
    }
 
    public void Unreserve(int seatNumber) {
        // Push the unreserved seat in the sorted set.
        availableSeats.Add(seatNumber);
    }
}// 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,1,2,null,2,3,4,5,null]

C# || How To Restore Array From Adjacent Pairs Using C#

July 28, 2024 admin No comments

The following is a module with functions which demonstrates how to restore the array from adjacent pairs using C#.

1. Restore Array – Problem Statement

There is an integer array nums that consists of n unique elements, but you have forgotten it. However, you do remember every pair of adjacent elements in nums.

You are given a 2D integer array adjacentPairs of size n – 1 where each adjacentPairs[i] = [u_i, v_i] indicates that the elements u_i and v_i are adjacent in nums.

It is guaranteed that every adjacent pair of elements nums[i] and nums[i+1] will exist in adjacentPairs, either as [nums[i], nums[i+1]] or [nums[i+1], nums[i]]. The pairs can appear in any order.

Return the original array nums. If there are multiple solutions, return any of them.

Example 1:

Input: adjacentPairs = [[2,1],[3,4],[3,2]] Output: [1,2,3,4] Explanation: This array has all its adjacent pairs in adjacentPairs. Notice that adjacentPairs[i] may not be in left-to-right order.

Example 2:

Input: adjacentPairs = [[4,-2],[1,4],[-3,1]] Output: [-2,4,1,-3] Explanation: There can be negative numbers. Another solution is [-3,1,4,-2], which would also be accepted.

Example 3:

Input: adjacentPairs = [[100000,-100000]] Output: [100000,-100000]

2. Restore Array – Solution

The following is a solution which demonstrates how to restore the array from adjacent pairs.





		
		
			2. Restore Array - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jul 28, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to restore the array from adjacent pairs
// ============================================================================
public class Solution {
    public int[] RestoreArray(int[][] adjacentPairs) {
        var graph = new Dictionary<int, List<int>>();

        foreach (int[] edge in adjacentPairs) {
            int x = edge[0];
            int y = edge[1];

            if (!graph.ContainsKey(x)) {
                graph[x] = new List<int>();
            }

            if (!graph.ContainsKey(y)) {
                graph[y] = new List<int>();
            }

            graph[x].Add(y);
            graph[y].Add(x);
        }

        int root = 0;
        foreach (int num in graph.Keys) {
            if (graph[num].Count == 1) {
                root = num;
                break;
            }
        }

        int curr = root;
        int[] ans = new int[graph.Count];
        ans[0] = root;
        int i = 1;
        int prev = int.MaxValue;

        while (i < graph.Count) {
            foreach (int neighbor in graph[curr]) {
                if (neighbor != prev) {
                    ans[i] = neighbor;
                    i++;
                    prev = curr;
                    curr = neighbor;
                    break;
                }
            }
        }

        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
49
50
51
52
53
54
55
56
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jul 28, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to restore the array from adjacent pairs
// ============================================================================
public class Solution {
    public int[] RestoreArray(int[][] adjacentPairs) {
        var graph = new Dictionary<int, List<int>>();
 
        foreach (int[] edge in adjacentPairs) {
            int x = edge[0];
            int y = edge[1];
 
            if (!graph.ContainsKey(x)) {
                graph[x] = new List<int>();
            }
 
            if (!graph.ContainsKey(y)) {
                graph[y] = new List<int>();
            }
 
            graph[x].Add(y);
            graph[y].Add(x);
        }
 
        int root = 0;
        foreach (int num in graph.Keys) {
            if (graph[num].Count == 1) {
                root = num;
                break;
            }
        }
 
        int curr = root;
        int[] ans = new int[graph.Count];
        ans[0] = root;
        int i = 1;
        int prev = int.MaxValue;
 
        while (i < graph.Count) {
            foreach (int neighbor in graph[curr]) {
                if (neighbor != prev) {
                    ans[i] = neighbor;
                    i++;
                    prev = curr;
                    curr = neighbor;
                    break;
                }
            }
        }
 
        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,2,3,4] [-2,4,1,-3] [100000,-100000]

C# || How To Design Graph With Shortest Path Calculator Using C#

June 01, 2024 admin No comments

The following is a module with functions which demonstrates how to design graph with shortest path calculator using C#.

1. Graph – Problem Statement

There is a directed weighted graph that consists of n nodes numbered from 0 to n – 1. The edges of the graph are initially represented by the given array edges where edges[i] = [from_i, to_i, edgeCost_i] meaning that there is an edge from from_i to to_i with the cost edgeCost_i.

Implement the Graph class:

Graph(int n, int[][] edges) initializes the object with n nodes and the given edges.
addEdge(int[] edge) adds an edge to the list of edges where edge = [from, to, edgeCost]. It is guaranteed that there is no edge between the two nodes before adding this one.
int shortestPath(int node1, int node2) returns the minimum cost of a path from node1 to node2. If no path exists, return -1. The cost of a path is the sum of the costs of the edges in the path.

Example 1:

Input ["Graph", "shortestPath", "shortestPath", "addEdge", "shortestPath"] [[4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]], [3, 2], [0, 3], [[1, 3, 4]], [0, 3]] Output [null, 6, -1, null, 6]
Explanation Graph g = new Graph(4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]); g.shortestPath(3, 2); // return 6. The shortest path from 3 to 2 in the first diagram above is 3 -> 0 -> 1 -> 2 with a total cost of 3 + 2 + 1 = 6. g.shortestPath(0, 3); // return -1. There is no path from 0 to 3. g.addEdge([1, 3, 4]); // We add an edge from node 1 to node 3, and we get the second diagram above. g.shortestPath(0, 3); // return 6. The shortest path from 0 to 3 now is 0 -> 1 -> 3 with a total cost of 2 + 4 = 6.

2. Graph – Solution

The following is a solution which demonstrates how to design graph with shortest path calculator.





		
		
			2. Graph - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jun 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to design graph shortest path calculator
// ============================================================================
/**
 * Your Graph object will be instantiated and called as such:
 * Graph obj = new Graph(n, edges);
 * obj.AddEdge(edge);
 * int param_2 = obj.ShortestPath(node1,node2);
 */
public class Graph {
    List<List<KeyValuePair<int, int>>> adjList;

    public Graph(int n, int[][] edges) {
        adjList = new List<List<KeyValuePair<int, int>>>();
        for (int i = 0; i < n; i++) {
            adjList.Add(new List<KeyValuePair<int, int>>());
        }
        foreach (int[] e in edges) {
            AddEdge(e);
        }
    }

    public void AddEdge(int[] edge) {
        adjList[edge[0]].Add(new KeyValuePair<int, int>(edge[1], edge[2]));
    }

    public int ShortestPath(int node1, int node2) {
        int n = adjList.Count;
        var pq = new PriorityQueue<List<int>, List<int>>(
            Comparer<List<int>>.Create((a, b) => a[0].CompareTo(b[0]))
        );

        int[] costForNode = new int[n];
        Array.Fill(costForNode, int.MaxValue);
        costForNode[node1] = 0;

        var root = new List<int>() { 0, node1 };
        pq.Enqueue(root, root);

        while (pq.Count > 0) {
            var curr = pq.Dequeue();
            int currCost = curr[0];
            int currNode = curr[1];

            if (currCost > costForNode[currNode]) {
                continue;
            }
            if (currNode == node2) {
                return currCost;
            }
            foreach (var neighbor in adjList[currNode]) {
                int neighborNode = neighbor.Key;
                int cost = neighbor.Value;
                int newCost = currCost + cost;

                if (newCost < costForNode[neighborNode]) {
                    costForNode[neighborNode] = newCost;
                    var newPath = new List<int>() { newCost, neighborNode };
                    pq.Enqueue(newPath, newPath);
                }
            }
        }

        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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jun 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to design graph shortest path calculator
// ============================================================================
/**
 * Your Graph object will be instantiated and called as such:
 * Graph obj = new Graph(n, edges);
 * obj.AddEdge(edge);
 * int param_2 = obj.ShortestPath(node1,node2);
 */
public class Graph {
    List<List<KeyValuePair<int, int>>> adjList;
 
    public Graph(int n, int[][] edges) {
        adjList = new List<List<KeyValuePair<int, int>>>();
        for (int i = 0; i < n; i++) {
            adjList.Add(new List<KeyValuePair<int, int>>());
        }
        foreach (int[] e in edges) {
            AddEdge(e);
        }
    }
 
    public void AddEdge(int[] edge) {
        adjList[edge[0]].Add(new KeyValuePair<int, int>(edge[1], edge[2]));
    }
 
    public int ShortestPath(int node1, int node2) {
        int n = adjList.Count;
        var pq = new PriorityQueue<List<int>, List<int>>(
            Comparer<List<int>>.Create((a, b) => a[0].CompareTo(b[0]))
        );
 
        int[] costForNode = new int[n];
        Array.Fill(costForNode, int.MaxValue);
        costForNode[node1] = 0;
 
        var root = new List<int>() { 0, node1 };
        pq.Enqueue(root, root);
 
        while (pq.Count > 0) {
            var curr = pq.Dequeue();
            int currCost = curr[0];
            int currNode = curr[1];
 
            if (currCost > costForNode[currNode]) {
                continue;
            }
            if (currNode == node2) {
                return currCost;
            }
            foreach (var neighbor in adjList[currNode]) {
                int neighborNode = neighbor.Key;
                int cost = neighbor.Value;
                int newCost = currCost + cost;
 
                if (newCost < costForNode[neighborNode]) {
                    costForNode[neighborNode] = newCost;
                    var newPath = new List<int>() { newCost, neighborNode };
                    pq.Enqueue(newPath, newPath);
                }
            }
        }
 
        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:

[null,6,-1,null,6]

C# || How To Find Largest 3 Same Digit Number In String Using C#

May 23, 2024 admin No comments

The following is a module with functions which demonstrates how to find the largest 3 same digit number in a string using C#.

1. Largest Good Integer – Problem Statement

You are given a string num representing a large integer. An integer is good if it meets the following conditions:

It is a substring of num with length 3.
It consists of only one unique digit.

Return the maximum good integer as a string or an empty string “” if no such integer exists.

Note:

A substring is a contiguous sequence of characters within a string.
There may be leading zeroes in num or a good integer.

Example 1:

Input: num = "6777133339" Output: "777" Explanation: There are two distinct good integers: "777" and "333". "777" is the largest, so we return "777".

Example 2:

Input: num = "2300019" Output: "000" Explanation: "000" is the only good integer.

Example 3:

Input: num = "42352338" Output: "" Explanation: No substring of length 3 consists of only one unique digit. Therefore, there are no good integers.

2. Largest Good Integer – Solution

The following is a solution which demonstrates how to find the largest 3 same digit number in a string.





		
		
			2. Largest Good Integer - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   May 23, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find largest odd number in a string
// ============================================================================
public class Solution {
    public string LargestGoodInteger(string num) {
        // Assign 'maxDigit' to the NUL character (smallest ASCII value character)
        char maxDigit = '\0';

        // Iterate on characters of the num string.
        for (int index = 0; index <= num.Length - 3; ++index) {
            // If 3 consecutive characters are the same,
            // store the character in 'maxDigit' if it's bigger than what it already stores.
            if (num[index] == num[index + 1] && num[index] == num[index + 2]) {
                maxDigit = (char) Math.Max(maxDigit, num[index]);
            }
        }

        // If 'maxDigit' is NUL, return an empty string; otherwise, return a string of size 3 with 'maxDigit' characters.
        return maxDigit == '\0' ? "" : new string(new char[]{maxDigit, maxDigit, maxDigit});
    }
}// 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   May 23, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find largest odd number in a string
// ============================================================================
public class Solution {
    public string LargestGoodInteger(string num) {
        // Assign 'maxDigit' to the NUL character (smallest ASCII value character)
        char maxDigit = '\0';
 
        // Iterate on characters of the num string.
        for (int index = 0; index <= num.Length - 3; ++index) {
            // If 3 consecutive characters are the same,
            // store the character in 'maxDigit' if it's bigger than what it already stores.
            if (num[index] == num[index + 1] && num[index] == num[index + 2]) {
                maxDigit = (char) Math.Max(maxDigit, num[index]);
            }
        }
 
        // If 'maxDigit' is NUL, return an empty string; otherwise, return a string of size 3 with 'maxDigit' characters.
        return maxDigit == '\0' ? "" : new string(new char[]{maxDigit, maxDigit, maxDigit});
    }
}// 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:

"777" "000" ""

C# || How To Find Largest Odd Number In String Using C#

April 13, 2024 admin No comments

The following is a module with functions which demonstrates how to find the largest odd number in a string using C#.

1. Largest Odd Number – Problem Statement

You are given a string num, representing a large integer. Return the largest-valued odd integer (as a string) that is a non-empty substring of num, or an empty string “” if no odd integer exists.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: num = "52" Output: "5" Explanation: The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.

Example 2:

Input: num = "4206" Output: "" Explanation: There are no odd numbers in "4206".

Example 3:

Input: num = "35427" Output: "35427" Explanation: "35427" is already an odd number.

2. Largest Odd Number – Solution

The following is a solution which demonstrates how to find the largest odd number in a string.





		
		
			2. Largest Odd Number - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Apr 13, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find largest odd number in a string
// ============================================================================
public class Solution {
    public string LargestOddNumber(string num) {
        for (int index = num.Length - 1; index >= 0; --index) {
            if (Convert.ToInt32(num[index]) % 2 != 0) {
                return num.Substring(0, index + 1);
            }
        }
        return "";
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Apr 13, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find largest odd number in a string
// ============================================================================
public class Solution {
    public string LargestOddNumber(string num) {
        for (int index = num.Length - 1; index >= 0; --index) {
            if (Convert.ToInt32(num[index]) % 2 != 0) {
                return num.Substring(0, index + 1);
            }
        }
        return "";
    }
}// 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:

"5" "" "35427"

C# || How To Determine If A Binary Tree Is Even Odd Tree Using C#

March 01, 2024 admin No comments

The following is a module with functions which demonstrates how to determine if a binary tree is an even odd tree using C#.

1. Is Even Odd Tree – Problem Statement

A binary tree is named Even-Odd if it meets the following conditions:

The root of the binary tree is at level index 0, its children are at level index 1, their children are at level index 2, etc.
For every even-indexed level, all nodes at the level have odd integer values in strictly increasing order (from left to right).
For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).

Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.

Example 1:

Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2] Output: true Explanation: The node values on each level are: Level 0: [1] Level 1: [10,4] Level 2: [3,7,9] Level 3: [12,8,6,2] Since levels 0 and 2 are all odd and increasing and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.

Example 2:

Input: root = [5,4,2,3,3,7] Output: false Explanation: The node values on each level are: Level 0: [5] Level 1: [4,2] Level 2: [3,3,7] Node values in level 2 must be in strictly increasing order, so the tree is not Even-Odd.

Example 3:

Input: root = [5,9,1,3,5,7] Output: false Explanation: Node values in the level 1 should be even integers.

2. Is Even Odd Tree – Solution

The following is a solution which demonstrates how to determine if a binary tree is an even odd tree.

This solution uses breadth-first search.





		
		
			2. Is Even Odd Tree - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Mar 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to determine an even odd tree
// ============================================================================
/**
 * 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 bool IsEvenOddTree(TreeNode root) {
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);

        var isEvenLevel = true;
        while (queue.Count > 0) {
            int previousValue = isEvenLevel ? int.MinValue : int.MaxValue;
            for (var size = queue.Count - 1; size >= 0; --size) {
                var currentNode = queue.Dequeue();

                if (isEvenLevel) {
                    if (IsEven(currentNode.val) || previousValue >= currentNode.val) {
                        return false;
                    }
                } else {
                    if (!IsEven(currentNode.val) || previousValue <= currentNode.val) {
                        return false;
                    }
                }
                if (currentNode.left != null) {
                    queue.Enqueue(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.Enqueue(currentNode.right);
                }
                previousValue = currentNode.val;
            }
            isEvenLevel = !isEvenLevel;
        }
        return true;
    }

    private bool IsEven(int value) {
        return value % 2 == 0;
    }
}// 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Mar 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to determine an even odd tree
// ============================================================================
/**
 * 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 bool IsEvenOddTree(TreeNode root) {
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
 
        var isEvenLevel = true;
        while (queue.Count > 0) {
            int previousValue = isEvenLevel ? int.MinValue : int.MaxValue;
            for (var size = queue.Count - 1; size >= 0; --size) {
                var currentNode = queue.Dequeue();
 
                if (isEvenLevel) {
                    if (IsEven(currentNode.val) || previousValue >= currentNode.val) {
                        return false;
                    }
                } else {
                    if (!IsEven(currentNode.val) || previousValue <= currentNode.val) {
                        return false;
                    }
                }
                if (currentNode.left != null) {
                    queue.Enqueue(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.Enqueue(currentNode.right);
                }
                previousValue = currentNode.val;
            }
            isEvenLevel = !isEvenLevel;
        }
        return true;
    }
 
    private bool IsEven(int value) {
        return value % 2 == 0;
    }
}// 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 false

C# || How To Group People Given The Group Size They Belong To Using C#

February 14, 2024 admin No comments

The following is a module with functions which demonstrates how to group people given the group size they belong to using C#.

1. Group The People – Problem Statement

There are n people that are split into some unknown number of groups. Each person is labeled with a unique ID from 0 to n – 1.

You are given an integer array groupSizes, where groupSizes[i] is the size of the group that person i is in. For example, if groupSizes[1] = 3, then person 1 must be in a group of size 3.

Return a list of groups such that each person i is in a group of size groupSizes[i].

Each person should appear in exactly one group, and every person must be in a group. If there are multiple answers, return any of them. It is guaranteed that there will be at least one valid solution for the given input.

Example 1:

Input: groupSizes = [3,3,3,3,3,1,3] Output: [[5],[0,1,2],[3,4,6]] Explanation: The first group is [5]. The size is 1, and groupSizes[5] = 1. The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3. The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3. Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2:

Input: groupSizes = [2,1,3,3,3,2] Output: [[1],[0,5],[2,3,4]]

2. Group The People – Solution

The following is a solution which demonstrates how to group people given the group size they belong to.





		
		
			2. Group The People - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Feb 14, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to group people given group they belong to
// ============================================================================
public class Solution {
    public IList<IList<int>> GroupThePeople(int[] groupSizes) {
        var ans = new List<IList<int>>();

        // A map from group size to the list of indices that are there in the group.
        var szToGroup = new Dictionary<int, List<int>>();
        for (int i = 0; i < groupSizes.Length; i++) {
            if (!szToGroup.ContainsKey(groupSizes[i])) {
                szToGroup.Add(groupSizes[i], new List<int>());
            }

            var group = szToGroup[groupSizes[i]];
            group.Add(i);

            // When the list size equals the group size, empty it and store it in the answer.
            if (group.Count == groupSizes[i]) {
                ans.Add(group);
                szToGroup.Remove(groupSizes[i]);
            }
        }

        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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Feb 14, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to group people given group they belong to
// ============================================================================
public class Solution {
    public IList<IList<int>> GroupThePeople(int[] groupSizes) {
        var ans = new List<IList<int>>();
 
        // A map from group size to the list of indices that are there in the group.
        var szToGroup = new Dictionary<int, List<int>>();
        for (int i = 0; i < groupSizes.Length; i++) {
            if (!szToGroup.ContainsKey(groupSizes[i])) {
                szToGroup.Add(groupSizes[i], new List<int>());
            }
 
            var group = szToGroup[groupSizes[i]];
            group.Add(i);
 
            // When the list size equals the group size, empty it and store it in the answer.
            if (group.Count == groupSizes[i]) {
                ans.Add(group);
                szToGroup.Remove(groupSizes[i]);
            }
        }
 
        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:

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

C# || How To Find Minimum Deletions To Make Character Frequencies Unique Using C#

February 01, 2024 admin No comments

The following is a module with functions which demonstrates how to find the minimum deletions to make character frequencies unique using C#.

1. Min Deletions – Problem Statement

A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return the minimum number of characters you need to delete to make s good.

The frequency of a character in a string is the number of times it appears in the string. For example, in the string “aab”, the frequency of ‘a’ is 2, while the frequency of ‘b’ is 1.

Example 1:

Input: s = "aab" Output: 0 Explanation: s is already good.

Example 2:

Input: s = "aaabbbcc" Output: 2 Explanation: You can delete two 'b's resulting in the good string "aaabcc". Another way it to delete one 'b' and one 'c' resulting in the good string "aaabbc".

Example 3:

Input: s = "ceabaacb" Output: 2 Explanation: You can delete both 'c's resulting in the good string "eabaab". Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).

2. Min Deletions – Solution

The following is a solution which demonstrates how to find the minimum deletions to make character frequencies unique.





		
		
			2. Min Operations - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Feb 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find minimum deletions to make unique
// ============================================================================
public class Solution {
    public int MinDeletions(string s) {
        // Store the frequency of each character
        int[] frequency = new int[26];
        for (int i = 0; i < s.Length; i++) {
            frequency[s[i] - 'a']++;
        }

        Array.Sort(frequency);

        int deleteCount = 0;
        // Maximum frequency the current character can have
        int maxFreqAllowed = s.Length;

        // Iterate over the frequencies in descending order
        for (int i = 25; i >= 0 && frequency[i] > 0; i--) {
            // Delete characters to make the frequency equal the maximum frequency allowed
            if (frequency[i] > maxFreqAllowed) {
                deleteCount += frequency[i] - maxFreqAllowed;
                frequency[i] = maxFreqAllowed;
            }
            // Update the maximum allowed frequency
            maxFreqAllowed = Math.Max(0, frequency[i] - 1);
        }

        return deleteCount;
    }
}// 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Feb 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find minimum deletions to make unique
// ============================================================================
public class Solution {
    public int MinDeletions(string s) {
        // Store the frequency of each character
        int[] frequency = new int[26];
        for (int i = 0; i < s.Length; i++) {
            frequency[s[i] - 'a']++;
        }
 
        Array.Sort(frequency);
 
        int deleteCount = 0;
        // Maximum frequency the current character can have
        int maxFreqAllowed = s.Length;
 
        // Iterate over the frequencies in descending order
        for (int i = 25; i >= 0 && frequency[i] > 0; i--) {
            // Delete characters to make the frequency equal the maximum frequency allowed
            if (frequency[i] > maxFreqAllowed) {
                deleteCount += frequency[i] - maxFreqAllowed;
                frequency[i] = maxFreqAllowed;
            }
            // Update the maximum allowed frequency
            maxFreqAllowed = Math.Max(0, frequency[i] - 1);
        }
 
        return deleteCount;
    }
}// 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 2

C# || Reconstruct Itinerary – How To Reconstruct Itinerary In Order Using C#

January 01, 2024 admin No comments

The following is a module with functions which demonstrates how to reconstruct itinerary in order using C#.

1. Find Itinerary – Problem Statement

You are given a list of airline tickets where tickets[i] = [from_i, to_i] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from “JFK”, thus, the itinerary must begin with “JFK”. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Example 1:

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] Output: ["JFK","MUC","LHR","SFO","SJC"]

Example 2:

Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Output: ["JFK","ATL","JFK","SFO","ATL","SFO"] Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.

2. Find Itinerary – Solution

The following is a solution which demonstrates how to reconstruct itinerary in order.





		
		
			2. Find Itinerary - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to reconstruct itinerary in order
// ============================================================================
public class Solution {
    public IList<string> FindItinerary(IList<IList<string>> tickets) {
        var map = new Dictionary<string, List<string>>();

        for (int index = 0; index < tickets.Count; ++index) {
            List<string> ticket = tickets[index].ToList();
            string from = ticket[0];
            string to = ticket[1];
            if (!map.ContainsKey(from)) {
                map[from] = new List<string>();
            }
            map[from].Add(to);
        }

        foreach (List<string> list in map.Values) {
            list.Sort();
        }

        var result = new List<string>();
        string start = "JFK";
        result.Add(start);
        DFS(map, start, result, tickets.Count);
        return result;
    }

    private bool DFS(Dictionary<string, List<string>> map, string cur, List<string> result, int totalTicket) {
        if (result.Count == totalTicket + 1) {
            return true;
        }

        if (!map.ContainsKey(cur)) {
            return false;
        }

        List<string> nextList = map[cur];

        for (int index = 0; index < nextList.Count; ++index) {
            string next = nextList[index];
            if (next == null) {
                continue;
            }

            nextList[index] = null;
            result.Add(next);
            if (DFS(map, next, result, totalTicket)) {
                return true;
            }
            // back track
            result.RemoveAt(result.Count - 1);
            nextList[index] = next;
        }

        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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 1, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to reconstruct itinerary in order
// ============================================================================
public class Solution {
    public IList<string> FindItinerary(IList<IList<string>> tickets) {
        var map = new Dictionary<string, List<string>>();
 
        for (int index = 0; index < tickets.Count; ++index) {
            List<string> ticket = tickets[index].ToList();
            string from = ticket[0];
            string to = ticket[1];
            if (!map.ContainsKey(from)) {
                map[from] = new List<string>();
            }
            map[from].Add(to);
        }
 
        foreach (List<string> list in map.Values) {
            list.Sort();
        }
 
        var result = new List<string>();
        string start = "JFK";
        result.Add(start);
        DFS(map, start, result, tickets.Count);
        return result;
    }
 
    private bool DFS(Dictionary<string, List<string>> map, string cur, List<string> result, int totalTicket) {
        if (result.Count == totalTicket + 1) {
            return true;
        }
 
        if (!map.ContainsKey(cur)) {
            return false;
        }
 
        List<string> nextList = map[cur];
 
        for (int index = 0; index < nextList.Count; ++index) {
            string next = nextList[index];
            if (next == null) {
                continue;
            }
 
            nextList[index] = null;
            result.Add(next);
            if (DFS(map, next, result, totalTicket)) {
                return true;
            }
            // back track
            result.RemoveAt(result.Count - 1);
            nextList[index] = next;
        }
 
        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:

["JFK","MUC","LHR","SFO","SJC"] ["JFK","ATL","JFK","SFO","ATL","SFO"]

C# || How To Find Minimum Operations To Reduce X To Zero Using C#

December 25, 2023 admin No comments

The following is a module with functions which demonstrates how to find the minimum number of operations to reduce X to zero using C#.

1. Min Operations – Problem Statement

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return the minimum number of operations to reduce x to exactly 0 if it is possible, otherwise, return -1.

Example 1:

Input: nums = [1,1,4,2,3], x = 5 Output: 2 Explanation: The optimal solution is to remove the last two elements to reduce x to zero.

Example 2:

Input: nums = [5,6,7,8,9], x = 4 Output: -1

Example 3:

Input: nums = [3,2,20,1,1,3], x = 10 Output: 5 Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.

2. Min Operations – Solution

The following is a solution which demonstrates how to find the minimum number of operations to reduce X to zero.





		
		
			2. Min Operations - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 25, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the minimum operations reduce X
// ============================================================================
public class Solution {
    public int MinOperations(int[] nums, int x) {
        var target = -x;
        foreach (int num in nums) {
            target += num;
        }

        // since all elements are positive, we have to take all of them
        if (target == 0) {
            return nums.Length;
        }

        var map = new Dictionary<int, int>();
        map[0] = -1;
        var sum = 0;
        var res = int.MinValue;

        for (var index = 0; index < nums.Length; ++index) {
            sum += nums[index];
            if (map.ContainsKey(sum - target)) {
                res = Math.Max(res, index - map[sum - target]);
            }
            // no need to check containsKey since sum is unique
            map[sum] = index;
        }

        return res == int.MinValue ? -1 : nums.Length - res;
    }
}// 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:   Dec 25, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the minimum operations reduce X
// ============================================================================
public class Solution {
    public int MinOperations(int[] nums, int x) {
        var target = -x;
        foreach (int num in nums) {
            target += num;
        }
 
        // since all elements are positive, we have to take all of them
        if (target == 0) {
            return nums.Length;
        }
 
        var map = new Dictionary<int, int>();
        map[0] = -1;
        var sum = 0;
        var res = int.MinValue;
 
        for (var index = 0; index < nums.Length; ++index) {
            sum += nums[index];
            if (map.ContainsKey(sum - target)) {
                res = Math.Max(res, index - map[sum - target]);
            }
            // no need to check containsKey since sum is unique
            map[sum] = index;
        }
 
        return res == int.MinValue ? -1 : nums.Length - res;
    }
}// 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:

2 -1 5

C# || How To Sort An Array By Parity Using C#

December 01, 2023 admin No comments

The following is a module with functions which demonstrates how to sort an array by parity using C#.

1. Sort Array By Parity – Problem Statement

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

Example 1:

Input: nums = [3,1,2,4] Output: [2,4,3,1] Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Example 2:

Input: nums = [0] Output: [0]

2. Sort Array By Parity – Solution

The following is a solution which demonstrates how to sort an array by parity.





		
		
			2. Sort Array By Parity - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to sort an array by parity
// ============================================================================
public class Solution {
    public int[] SortArrayByParity(int[] nums) {
        var startIndex = 0;
        var endIndex = nums.Length -1;

        while (startIndex < endIndex) {
            if (IsOdd(nums[startIndex])) {
                var temp = nums[startIndex];
                nums[startIndex] = nums[endIndex];
                nums[endIndex] = temp;
                --endIndex;
            } else {
                ++startIndex;
            }
        }
        return nums;
    }

    private bool IsOdd(int num) {
        return num % 2 != 0;
    }
}// 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:   Dec 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to sort an array by parity
// ============================================================================
public class Solution {
    public int[] SortArrayByParity(int[] nums) {
        var startIndex = 0;
        var endIndex = nums.Length -1;
 
        while (startIndex < endIndex) {
            if (IsOdd(nums[startIndex])) {
                var temp = nums[startIndex];
                nums[startIndex] = nums[endIndex];
                nums[endIndex] = temp;
                --endIndex;
            } else {
                ++startIndex;
            }
        }
        return nums;
    }
 
    private bool IsOdd(int num) {
        return num % 2 != 0;
    }
}// 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,2,1,3] [0]

C# || Parallel Courses III – How To Find Minimum Number Months To Complete All Courses Using C#

November 01, 2023 admin No comments

The following is a module with functions which demonstrates how to find the minimum number of months needed to complete all courses using C#.

1. Minimum Time – Problem Statement

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given a 2D integer array relations where relations[j] = [prevCourse_j, nextCourse_j] denotes that course prevCourse_j has to be completed before course nextCourse_j (prerequisite relationship). Furthermore, you are given a 0-indexed integer array time where time[i] denotes how many months it takes to complete the (i+1)^th course.

You must find the minimum number of months needed to complete all the courses following these rules:

You may start taking a course at any time if the prerequisites are met.
Any number of courses can be taken at the same time.

Return the minimum number of months needed to complete all the courses.

Note: The test cases are generated such that it is possible to complete every course (i.e., the graph is a directed acyclic graph).

Example 1:

Input: n = 3, relations = [[1,3],[2,3]], time = [3,2,5] Output: 8 Explanation: The figure above represents the given graph and the time required to complete each course. We start course 1 and course 2 simultaneously at month 0. Course 1 takes 3 months and course 2 takes 2 months to complete respectively. Thus, the earliest time we can start course 3 is at month 3, and the total time required is 3 + 5 = 8 months.

Example 2:

Input: n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5] Output: 12 Explanation: The figure above represents the given graph and the time required to complete each course. You can start courses 1, 2, and 3 at month 0. You can complete them after 1, 2, and 3 months respectively. Course 4 can be taken only after course 3 is completed, i.e., after 3 months. It is completed after 3 + 4 = 7 months. Course 5 can be taken only after courses 1, 2, 3, and 4 have been completed, i.e., after max(1,2,3,7) = 7 months. Thus, the minimum time needed to complete all the courses is 7 + 5 = 12 months.

2. Minimum Time – Solution

The following is a solution which demonstrates how to find the minimum number of months needed to complete all courses.





		
		
			2. Minimum Time - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the minimum months complete courses
// ============================================================================
public class Solution {
    public int MinimumTime(int n, int[][] relations, int[] time) {
        var graph = new Dictionary<int, List<int>>();
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }

        int[] indegree = new int[n];
        foreach (int[] edge in relations) {
            int x = edge[0] - 1;
            int y = edge[1] - 1;
            graph[x].Add(y);
            indegree[y]++;
        }

        var queue = new Queue<int>();
        int[] maxTime = new int[n];

        for (int node = 0; node < n; node++) {
            if (indegree[node] == 0) {
                queue.Enqueue(node);
                maxTime[node] = time[node];
            }
        }

        while (queue.Count > 0) {
            int node = queue.Dequeue();
            foreach (int neighbor in graph[node]) {
                maxTime[neighbor] = Math.Max(maxTime[neighbor], maxTime[node] + time[neighbor]);
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.Enqueue(neighbor);
                }
            }
        }

        int ans = 0;
        for (int node = 0; node < n; node++) {
            ans = Math.Max(ans, maxTime[node]);
        }

        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
49
50
51
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the minimum months complete courses
// ============================================================================
public class Solution {
    public int MinimumTime(int n, int[][] relations, int[] time) {
        var graph = new Dictionary<int, List<int>>();
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
 
        int[] indegree = new int[n];
        foreach (int[] edge in relations) {
            int x = edge[0] - 1;
            int y = edge[1] - 1;
            graph[x].Add(y);
            indegree[y]++;
        }
 
        var queue = new Queue<int>();
        int[] maxTime = new int[n];
 
        for (int node = 0; node < n; node++) {
            if (indegree[node] == 0) {
                queue.Enqueue(node);
                maxTime[node] = time[node];
            }
        }
 
        while (queue.Count > 0) {
            int node = queue.Dequeue();
            foreach (int neighbor in graph[node]) {
                maxTime[neighbor] = Math.Max(maxTime[neighbor], maxTime[node] + time[neighbor]);
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.Enqueue(neighbor);
                }
            }
        }
 
        int ans = 0;
        for (int node = 0; node < n; node++) {
            ans = Math.Max(ans, maxTime[node]);
        }
 
        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:

8 12

Tag Archives: leetcode

C# || How To Find Mode In Binary Search Tree Using C#

C# || How To Find The Winner Of Array Game Using C#

C# || How To Design Seat Reservation Manager Using C#

C# || How To Restore Array From Adjacent Pairs Using C#

C# || How To Design Graph With Shortest Path Calculator Using C#

C# || How To Find Largest 3 Same Digit Number In String Using C#

C# || How To Find Largest Odd Number In String Using C#

C# || How To Determine If A Binary Tree Is Even Odd Tree Using C#

C# || How To Group People Given The Group Size They Belong To Using C#

C# || How To Find Minimum Deletions To Make Character Frequencies Unique Using C#

C# || Reconstruct Itinerary – How To Reconstruct Itinerary In Order Using C#

C# || How To Find Minimum Operations To Reduce X To Zero Using C#

C# || How To Sort An Array By Parity Using C#

C# || Parallel Courses III – How To Find Minimum Number Months To Complete All Courses Using C#

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories