Tag Archives: c-sharp
C# || How To Find The Difference Between Two Strings Using C#
The following is a module with functions which demonstrates how to find the difference between two strings using C#.
1. Find The Difference – Problem Statement
You are given two strings s and t.
String t is generated by random shuffling string s and then add one more letter at a random position.
Return the letter that was added to t.
Example 1:
Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.
Example 2:
Input: s = "", t = "y"
Output: "y"
2. Find The Difference – Solution
The following is a solution which demonstrates how to find the difference between two strings.
|
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: Feb 6, 2022 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find the difference between two strings // ============================================================================ public class Solution { public char FindTheDifference(string s, string t) { var result = ' '; // Create a map with the frequency each character has been seen from the first string var seen = new Dictionary<char, int>(); foreach (var letter in s) { seen[letter] = (seen.ContainsKey(letter) ? seen[letter] : 0) + 1; } // Decrease the frequency of the characters we've seen from the second string foreach (var letter in t) { // Either we havent seen this character, or its frequency has reached 0 if (!seen.ContainsKey(letter) || seen[letter] == 0) { result = letter; break; } // Decrease the frequency --seen[letter]; } 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:
"e"
"y"
C# || How To Get Total Sum Root To Leaf Binary Numbers In Binary Tree Using C#
The following is a module with functions which demonstrates how to get the total sum root to leaf binary numbers in a binary tree using C#.
1. Sum Root To Leaf – Problem Statement
You are given the root of a binary tree where each node has a value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit.
- For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.
For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return the sum of these numbers.
The test cases are generated so that the answer fits in a 32-bits integer.
A leaf node is a node with no children.
Example 1:
Input: root = [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
Example 2:
Input: root = [0]
Output: 0
2. Sum Root To Leaf – Solution
The following is a solution which demonstrates how to get the total sum root to leaf binary numbers in a binary tree.
This solution uses Depth First Search to explore items at each level.
|
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 |
// ============================================================================ // Author: Kenneth Perkins // Date: Jan 10, 2022 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to get sum root to leaf binary numbers // ============================================================================ /** * 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 SumRootToLeaf(TreeNode root) { return Traverse(root, 0); } private int Traverse(TreeNode node, int currentSum) { if (node == null) { return 0; } // Calculate current sum currentSum = (currentSum * 2) + node.val; // We have reached a leaf node if (node.left == null && node.right == null) { return currentSum; } // Keep traversing left and right calculating the sum return Traverse(node.left, currentSum) + Traverse(node.right, currentSum); } }// 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:
22
0
C# || Jump Game III – How To Check If You Can Reach Target Value In Array Using C#
The following is a module with functions which demonstrates how to check if you can reach a target value in an array using C#.
1. Can Reach – Problem Statement
Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i – arr[i], check if you can reach to any index with value 0.
Notice that you can not jump outside of the array at any time.
Example 1:
Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation:
All possible ways to reach at index 3 with value 0 are:
index 5 -> index 4 -> index 1 -> index 3
index 5 -> index 6 -> index 4 -> index 1 -> index 3
Example 2:
Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true
Explanation:
One possible way to reach at index 3 with value 0 is:
index 0 -> index 4 -> index 1 -> index 3
Example 3:
Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.
2. Can Reach – Solution
The following are two solutions which demonstrates how to check if you can reach a target value in an array.
The following solution uses Depth First Search when looking for the target value.
|
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: Dec 8, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Determines if a target value can be reached in an array // ============================================================================ public class Solution { public bool CanReach(int[] arr, int start) { var visited = new bool[arr.Length]; return DFS(arr, start, visited); } public bool DFS(int[] arr, int currentIndex, bool[] visited) { // Make sure parameters are in bounds if (currentIndex < 0 || currentIndex >= arr.Length) { return false; } // Check to see if the index has been visited if (visited[currentIndex]) { return false; } // Check to see if we found the target value if (arr[currentIndex] == 0) { return true; } // Mark current index as visited visited[currentIndex] = true; // Keep searching forwards and backwards var forwards = currentIndex + arr[currentIndex]; var backwards = currentIndex - arr[currentIndex]; return DFS(arr, backwards, visited) || DFS(arr, forwards, visited); } }// http://programmingnotes.org/ |
The following solution uses Breadth First Search when looking for the target value.
|
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: Dec 8, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Determines if a target value can be reached in an array // ============================================================================ public class Solution { public bool CanReach(int[] arr, int start) { var visited = new bool[arr.Length]; var queue = new Queue<int>(); queue.Enqueue(start); while (queue.Count > 0) { var currentIndex = queue.Dequeue(); // Check to see if we found the target value if (arr[currentIndex] == 0) { return true; } // Mark current index as visited visited[currentIndex] = true; // Keep searching forwards and backwards var forwards = currentIndex + arr[currentIndex]; var backwards = currentIndex - arr[currentIndex]; var directions = new List<int>{forwards, backwards}; foreach (var direction in directions) { if (direction >= 0 && direction < arr.Length && !visited[direction]) { queue.Enqueue(direction); } } } 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# || Maximum Product Subarray – How To Find Largest Product In Contiguous Subarray Using C#
The following is a module with functions which demonstrates how to find the largest product in a contiguous subarray using C#.
1. Max Product – Problem Statement
Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
It is guaranteed that the answer will fit in a 32-bit integer.
A subarray is a contiguous subsequence of the array.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
2. Max Product – Solution
The following is a solution which demonstrates how to find the largest product in a contiguous subarray.
This solution is inspired by Kadane’s algorithm to find the result.
The idea here is similar to the ‘Maximum Subarray‘ problem.
In this solution, we have two values:
- The current cumulative maximum product up to current element
- The current cumulative minimum product up to current element
Each loop iteration, these values are updated by either multiplying the new element at the current index with the existing product, or starting fresh from current index.
When a negative number is encountered, the current max and current min values are swapped, because multiplying a negative number makes a big number smaller, and multiplying a negative number makes small number bigger. So their intent is redefined by swapping.
|
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 |
// ============================================================================ // Author: Kenneth Perkins // Date: Dec 2, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find maximum product contiguous subarray // ============================================================================ public class Solution { public int MaxProduct(int[] nums) { // Store the result var result = nums[0]; // The current maximum and minimum product of the subarray var currentMin = nums[0]; var currentMax = nums[0]; for (int index = 1; index < nums.Length; ++index) { // Swap current max/min because multiplying // a negative number makes a big number smaller, // and multiplying a negative number makes small number bigger. // So their intent is redefined by swapping if (nums[index] < 0) { var temp = currentMax; currentMax = currentMin; currentMin = temp; } // Determine the max/min product for the current number. // It is either the current number itself // or the max/min by the previous values times the current one currentMax = Math.Max(nums[index], currentMax * nums[index]); currentMin = Math.Min(nums[index], currentMin * nums[index]); // Keep track of the current max result result = Math.Max(result, currentMax); } 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:
6
0
C# || Maximum Subarray – How To Find Largest Sum In Contiguous Subarray Using C#
The following is a module with functions which demonstrates how to find the largest sum in a contiguous subarray using C#.
1. Max Sub Array – Problem Statement
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1]
Output: 1
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
2. Max Sub Array – Solution
The following is a solution which demonstrates how to find the largest sum in a contiguous subarray.
This solution uses Kadane’s algorithm to find the result.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// ============================================================================ // Author: Kenneth Perkins // Date: Dec 2, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find maximum sum in contiguous subarray // ============================================================================ public class Solution { public int MaxSubArray(int[] nums) { var result = nums[0]; var current = result; for (int index = 1; index < nums.Length; ++index) { current = Math.Max(nums[index], nums[index] + current); result = Math.Max(result, current); } 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:
6
1
23
C# || String To Integer (atoi) – How To Convert String To Signed Integer Using C#
The following is a module with functions which demonstrates how to convert a string to 32-bit signed integer using C#.
1. My Atoi – Problem Statement
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).
The algorithm for myAtoi(string s) is as follows:
- Read in and ignore any leading whitespace.
- Check if the next character (if not already at the end of the string) is ‘-‘ or ‘+’. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
- Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
- Convert these digits into an integer (i.e. “123” -> 123, “0032” -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
- If the integer is out of the 32-bit signed integer range [-231, 231 – 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 – 1 should be clamped to 231 – 1.
- Return the integer as the final result.
Note:
- Only the space character ‘ ‘ is considered a whitespace character.
- Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.
Example 1:
Input: s = "42"
Output: 42
Explanation: The underlined characters are what is read in, the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
^
Step 3: "42" ("42" is read in)
^
The parsed integer is 42.
Since 42 is in the range [-231, 231 - 1], the final result is 42.
Example 2:
Input: s = " -42"
Output: -42
Explanation:
Step 1: " -42" (leading whitespace is read and ignored)
^
Step 2: " -42" ('-' is read, so the result should be negative)
^
Step 3: " -42" ("42" is read in)
^
The parsed integer is -42.
Since -42 is in the range [-231, 231 - 1], the final result is -42.
Example 3:
Input: s = "4193 with words"
Output: 4193
Explanation:
Step 1: "4193 with words" (no characters read because there is no leading whitespace)
^
Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')
^
Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)
^
The parsed integer is 4193.
Since 4193 is in the range [-231, 231 - 1], the final result is 4193.
Example 4:
Input: s = "words and 987"
Output: 0
Explanation:
Step 1: "words and 987" (no characters read because there is no leading whitespace)
^
Step 2: "words and 987" (no characters read because there is neither a '-' nor '+')
^
Step 3: "words and 987" (reading stops immediately because there is a non-digit 'w')
^
The parsed integer is 0 because no digits were read.
Since 0 is in the range [-231, 231 - 1], the final result is 0.
Example 5:
Input: s = "-91283472332"
Output: -2147483648
Explanation:
Step 1: "-91283472332" (no characters read because there is no leading whitespace)
^
Step 2: "-91283472332" ('-' is read, so the result should be negative)
^
Step 3: "-91283472332" ("91283472332" is read in)
^
The parsed integer is -91283472332.
Since -91283472332 is less than the lower bound of the range [-231, 231 - 1], the final result is clamped to -231 = -2147483648.
2. My Atoi – Solution
The following is a solution which demonstrates how to convert a string to 32-bit signed integer.
|
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: Nov 30, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to convert string to integer // ============================================================================ public class Solution { public int MyAtoi(string s) { // 1. Advance leading whitespace var index = 0; while (index < s.Length && char.IsWhiteSpace(s[index])) { ++index; } // 2. Determine if number is positive or negative var sign = 1; if (index < s.Length && (s[index] == '-' || s[index] == '+')) { if (s[index] == '-') { sign = -1; } ++index; } // 3. Convert char digits to numeric value var result = 0; while (index < s.Length && char.IsDigit(s[index])) { var digit = CharToInt(s[index]); // Check for overflow if (result > (int.MaxValue - digit) / 10) { return sign == -1 ? int.MinValue : int.MaxValue; } result = (result * 10) + digit; ++index; } return result * sign; } private static int CharToInt(char ch) { return ch - '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:
42
-42
4193
0
-2147483648
C# || Maximal Rectangle – How To Find Largest Rectangle Area Using C#
The following is a module with functions which demonstrates how to find the largest rectangle area containing only 1’s using C#.
1. Maximal Rectangle – Problem Statement
Given a rows x cols binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing only 1‘s and return its area.
Example 1:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.
Example 2:
Input: matrix = []
Output: 0
Example 3:
Input: matrix = [["0"]]
Output: 0
Example 4:
Input: matrix = [["1"]]
Output: 1
Example 5:
Input: matrix = [["0","0"]]
Output: 0
2. Maximal Rectangle – Solution
The following is a solution which demonstrates how to find the largest rectangle area containing only 1’s.
This solution uses the monotonic stack approach.
|
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: Nov 30, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find the largest rectangle area // ============================================================================ public class Solution { public int MaximalRectangle(char[][] matrix) { if (matrix.Length == 0) { return 0; } var result = 0; var histogram = new int[matrix[0].Length + 1]; for (int row = 0; row < matrix.Length; ++row) { var stack = new Stack<int>(); for (int col = 0; col <= matrix[row].Length; ++col) { // Set value if (col < matrix[row].Length) { if (matrix[row][col] == '1') { histogram[col] += 1; } else { histogram[col] = 0; } } // Compute area while (stack.Count > 0 && histogram[stack.Peek()] >= histogram[col]) { var area = histogram[stack.Pop()] * (stack.Count == 0 ? col : (col - stack.Peek() - 1)); result = Math.Max(result, area); } stack.Push(col); } } 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:
6
0
0
1
0
C# || How To Find The Largest Component Size By Common Factor Using C#
The following is a module with functions which demonstrates how to find the largest component size by common factor using C#.
1. Largest Component Size – Problem Statement
You are given an integer array of unique positive integers nums. Consider the following graph:
- There are nums.length nodes, labeled nums[0] to nums[nums.length – 1],
- There is an undirected edge between nums[i] and nums[j] if nums[i] and nums[j] share a common factor greater than 1.
Return the size of the largest connected component in the graph.
Example 1:
Input: nums = [4,6,15,35]
Output: 4
Example 2:
Input: nums = [20,50,9,63]
Output: 2
Example 3:
Input: nums = [2,3,6,7,4,12,21,39]
Output: 8
2. Largest Component Size – Solution
The following is a solution which demonstrates how to find the largest component size by common factor.
The following solution uses a union find set to group connections together.
|
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 |
// ============================================================================ // Author: Kenneth Perkins // Date: Nov 28, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find largest common factor // ============================================================================ public class Solution { public int LargestComponentSize(int[] nums) { var set = new UnionFindSet(nums.Max() + 1); // Calculate primes set for all elements foreach (var num in nums) { for (var k = 2; k * k <= num; ++k) { if (num % k == 0) { set.Union(num, k); set.Union(num, num / k); } } } // Count the apperance of parents, return the maxium one. // All connected nodes will point to same parent var map = new Dictionary<int, int>(); var result = 1; foreach (var num in nums) { var count = set.Find(num); map[count] = (map.ContainsKey(count) ? map[count] : 0) + 1; result = Math.Max(result, map[count]); } return result; } public class UnionFindSet { private int[] parent; public UnionFindSet(int size) { parent = new int[size]; for (int i = 0; i < parent.Length; ++i) { parent[i] = i; } } public void Union(int x, int y) { parent[Find(x)] = parent[Find(y)]; } public int Find(int x) { if (parent[x] != x) { parent[x] = Find(parent[x]); } return parent[x]; } } }// 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
8
C# || Accounts Merge – How To Merge A List Of Emails Using C#
The following is a module with functions which demonstrates how to merge a list of emails using C#.
1. Accounts Merge – Problem Statement
Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.
Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.
After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.
Example 1:
Input: accounts = [["John","[email protected]","[email protected]"],["John","[email protected]","[email protected]"],["Mary","[email protected]"],["John","[email protected]"]]
Output: [["John","[email protected]","[email protected]","[email protected]"],["Mary","[email protected]"],["John","[email protected]"]]
Explanation:
The first and second John's are the same person as they have the common email "[email protected]".
The third John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [['Mary', '[email protected]'], ['John', '[email protected]'],
['John', '[email protected]', '[email protected]', '[email protected]']] would still be accepted.
Example 2:
Input: accounts = [["Gabe","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Ethan","[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]","[email protected]"]]
Output: [["Ethan","[email protected]","[email protected]","[email protected]"],["Gabe","[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]","[email protected]"]]
2. Accounts Merge – Solution
The following is a solution which demonstrates how to merge a list of emails.
The following solution uses a union find set to group accounts with matching emails together.
|
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 80 81 82 83 84 85 86 87 |
// ============================================================================ // Author: Kenneth Perkins // Date: Nov 28, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to merge a list of emails // ============================================================================ public class Solution { public IList<IList<string>> AccountsMerge(IList<IList<string>> accounts) { var set = new UnionFindSet(accounts.Count); // Map email to their component index var emailComponents = new Dictionary<string, int>(); for (int i = 0; i < accounts.Count; ++i) { var account = accounts[i]; for (int j = 1; j < account.Count; ++j) { var email = account[j]; // Assign component group as the account index var group = i; if (!emailComponents.ContainsKey(email)) { emailComponents[email] = group; } else { // Union this group with the previous group of the email set.Union(group, emailComponents[email]); } } } // Store emails corresponding to the components parent var emailGroups = new Dictionary<int, List<string>>(); foreach (var email in emailComponents.Keys) { var group = emailComponents[email]; var groupParent = set.Find(group); if (!emailGroups.ContainsKey(groupParent)) { emailGroups[groupParent] = new List<string>(); } emailGroups[groupParent].Add(email); } // Sort the emails and add the account name var result = new List<IList<string>>(); foreach (var group in emailGroups.Keys) { var emails = emailGroups[group]; emails.Sort(StringComparer.Ordinal); emails.Insert(0, accounts[group][0]); result.Add(emails); } return result; } public class UnionFindSet { int[] parent; int[] size; public UnionFindSet(int count) { parent = new int[count]; size = new int[count]; for (int index = 0; index < count; ++index) { parent[index] = index; size[index] = 1; } } public int Find(int x) { if (parent[x] != x) { parent[x] = Find(parent[x]); } return parent[x]; } public void Union(int x, int y) { var parentX = Find(x); var parentY = Find(y); if (parentX == parentY) { return; } if (size[parentX] >= size[parentY]) { size[parentX] += size[parentY]; parent[parentY] = parentX; } else { size[parentY] += size[parentX]; parent[parentX] = parentY; } } } }// 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:
[["John","[email protected]","[email protected]","[email protected]"],["Mary","[email protected]"],["John","[email protected]"]]
[["Gabe","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Ethan","[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]","[email protected]"]]
C# || How To Find All Paths From Source To Target In Graph Using C#
The following is a module with functions which demonstrates how to find all paths from source to target in a graph using C#.
1. All Paths Source Target – Problem Statement
Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n – 1, find all possible paths from node 0 to node n – 1 and return them in any order.
The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).
Example 1:
Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
Example 2:
Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
Example 3:
Input: graph = [[1],[]]
Output: [[0,1]]
Example 4:
Input: graph = [[1,2,3],[2],[3],[]]
Output: [[0,1,2,3],[0,2,3],[0,3]]
Example 5:
Input: graph = [[1,3],[2],[3],[]]
Output: [[0,1,2,3],[0,3]]
2. All Paths Source Target – Solution
The following is a solution which demonstrates how to find all paths from source to target in a graph.
This solution uses Breadth First Search and backtracking when looking for paths.
|
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: Nov 28, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find all paths in a graph // ============================================================================ public class Solution { public IList<IList<int>> AllPathsSourceTarget(int[][] graph) { var result = new List<IList<int>>(); var queue = new Queue<List<int>>(); queue.Enqueue(new List<int>{0}); while (queue.Count > 0) { var currentPath = queue.Dequeue(); var currentNode = currentPath[currentPath.Count - 1]; if (currentNode == graph.Length - 1) { result.Add(currentPath); } else { foreach (var child in graph[currentNode]) { currentPath.Add(child); queue.Enqueue(new List<int>(currentPath)); currentPath.RemoveAt(currentPath.Count - 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,3],[0,2,3]]
[[0,4],[0,3,4],[0,1,4],[0,1,3,4],[0,1,2,3,4]]
[[0,1]]
[[0,3],[0,2,3],[0,1,2,3]]
[[0,3],[0,1,2,3]]
C# || How To Search In Rotated Sorted Array Using C#
The following is a module with functions which demonstrates how to search for a target value in a rotated sorted array using C#.
1. Search – Problem Statement
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:
Input: nums = [1], target = 0
Output: -1
2. Search – Solution
The following is a solution which demonstrates how to search for a target value in a rotated sorted array.
The idea of this solution is to use binary search, and for each loop iteration we compare the midpoint element with the right side of the array to determine the search area of where the target element might be.
|
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 |
// ============================================================================ // Author: Kenneth Perkins // Date: Nov 26, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to search for a target in a rotated array // ============================================================================ public class Solution { public int Search(int[] nums, int target) { var lo = 0; var hi = nums.Length - 1; while (lo <= hi) { var mid = lo + (hi - lo) / 2; // Target element found if (nums[mid] == target) { return mid; // Midpoint element is greater than right side of array } else if (nums[mid] > nums[hi]) { // Determine which side of array to adjust if (target < nums[mid] && target >= nums[lo]) { hi = mid - 1; } else { lo = mid + 1; } // Midpoint element is less than right side of array } else { // Determine which side of array to adjust if (target > nums[mid] && target <= nums[hi]) { lo = mid + 1; } else { hi = mid - 1; } } } 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:
4
-1
-1
C# || How To Find Product Of Array Except Self Using C#
The following is a module with functions which demonstrates how to find the product of an array except itself using C#.
1. Product Except Self – Problem Statement
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
2. Product Except Self – Solution
The following is a solution which demonstrates how to find the product of an array except itself.
In this solution, the product for result[i] is calculated by scanning the input array, and multiplying the numbers that come before the current i, and the numbers that come after the current i.
First, the running product of the numbers that come before the current i is calculated by scanning the array starting from the beginning (prefix).
Then, the running product of the numbers that come after the current i is calculated by scanning the array starting from the end (suffix).
|
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 |
// ============================================================================ // Author: Kenneth Perkins // Date: Nov 26, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find product of array except self // ============================================================================ public class Solution { public int[] ProductExceptSelf(int[] nums) { var result = new int[nums.Length]; // Prefix var runningPrefix = 1; for (int index = 0; index < nums.Length; ++index) { result[index] = runningPrefix; runningPrefix *= nums[index]; } // Suffix var runningSufix = 1; for (int index = nums.Length - 1; index >= 0; --index) { result[index] *= runningSufix; runningSufix *= nums[index]; } 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:
[24,12,8,6]
[0,0,9,0,0]
C# || How To Find Interval List Intersections From Two Arrays Using C#
The following is a module with functions which demonstrates how to find interval list intersections from two arrays using C#.
1. Interval Intersection – Problem Statement
You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.
Return the intersection of these two interval lists.
A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.
The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].
Example 1:
Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Example 2:
Input: firstList = [[1,3],[5,9]], secondList = []
Output: []
Example 3:
Input: firstList = [], secondList = [[4,8],[10,12]]
Output: []
Example 4:
Input: firstList = [[1,7]], secondList = [[3,10]]
Output: [[3,7]]
2. Interval Intersection – Solution
The following is a solution which demonstrates how to find interval list intersections from two arrays.
This solution uses the two pointer technique when looking for valid interval intersections.
|
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: Nov 23, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find interval list intersections // ============================================================================ public class Solution { public int[][] IntervalIntersection(int[][] firstList, int[][] secondList) { var result = new List<int[]>(); // Go through first and second array looking for range intersection var indexFirst = 0; var indexSecond = 0; while (indexFirst < firstList.Length && indexSecond < secondList.Length) { // Get the first and second array var first = firstList[indexFirst]; var second = secondList[indexSecond]; // Check to see if this is a valid intersection if (first[1] >= second[0] && first[0] <= second[1]) { // Get starting and ending range from the two arrays var start = Math.Max(first[0], second[0]); var end = Math.Min(first[1], second[1]); result.Add(new int[] {start, end}); } // Increment array index depending on which range is completely satisfied if (first[1] < second[1]) { ++indexFirst; } else { ++indexSecond; } } return result.ToArray(); } }// 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],[5,5],[8,10],[15,23],[24,24],[25,25]]
[]
[]
[[3,7]]
C# || CombinationIterator – How To Implement Iterator For Combination Using C#
The following is a module with functions which demonstrates how to implement iterator for combination using C#.
1. Combination Iterator – Problem Statement
Design the CombinationIterator class:
- CombinationIterator(string characters, int combinationLength) Initializes the object with a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
- next() Returns the next combination of length combinationLength in lexicographical order.
- hasNext() Returns true if and only if there exists a next combination.
Example 1:
Input
Input:
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output:
[null, "ab", true, "ac", true, "bc", false]Explanation:
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next(); // return "ab"
itr.hasNext(); // return True
itr.next(); // return "ac"
itr.hasNext(); // return True
itr.next(); // return "bc"
itr.hasNext(); // return False
2. Combination Iterator – Solution
The following is a solution which demonstrates how to implement iterator for combination.
The following solution uses backtracking to generate combinations.
|
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 |
// ============================================================================ // Author: Kenneth Perkins // Date: Nov 20, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to implement iterator for combination // ============================================================================ public class CombinationIterator { Queue<string> combinations; public CombinationIterator(string characters, int combinationLength) { combinations = new Queue<string>(); Generate(characters, combinationLength, 0, new StringBuilder()); } private void Generate(string characters, int combinationLength, int startIndex, StringBuilder currentCombo) { if (currentCombo.Length == combinationLength) { combinations.Enqueue(currentCombo.ToString()); return; } for (int index = startIndex; index < characters.Length; ++index) { // Add this item to the combination currentCombo.Append(characters[index]); // Keep generating permutations Generate(characters, combinationLength, index + 1, currentCombo); // Remove last item as its already been explored currentCombo.Remove(currentCombo.Length - 1, 1); } } public string Next() { return combinations.Dequeue(); } public bool HasNext() { return combinations.Count > 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:
[null,"ab",true,"ac",true,"bc",false]
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
