October 2021 – My Programming Notes

Monthly Archives: October 2021

C# || How To Flatten A Multilevel Doubly Linked List Using C#

October 30, 2021 admin No comments

The following is a module with functions which demonstrates how to flatten a doubly linked list using C#.

1. Flatten – Problem Statement

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] Output: [1,2,3,7,8,11,12,9,10,4,5,6] Explanation:
The multilevel linked list in the input is as follows:

After flattening the multilevel linked list it becomes:

Example 2:

Input: head = [1,2,null,3] Output: [1,3,2] Explanation:
The input multilevel linked list is as follows:
1---2---NULL | 3---NULL

Example 3:

Input: head = [] Output: []

2. Flatten – Solution

The following are two solutions which demonstrates how to flatten a doubly linked list.

Iterative





		
		
			2. Flatten Iterative - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to flatten a doubly linked list
// ============================================================================
/*
// Definition for a Node.
public class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}
*/
public class Solution {
    public Node Flatten(Node head) {
        var current = head;
        var stack = new Stack<Node>();

        // Loop through nodes
        while (current != null) {

            // Check to see if node has child
            if (current.child != null) {
                // If current node has a next node, save to stack
                // so we can reconnect it to the tail
                // of the child node later
                if (current.next != null) {
                    stack.Push(current.next);
                }

                // Set the next node as the child,
                // we will now iterate down this path
                current.next = current.child;

                // Set the previous node as the current
                current.next.prev = current;

                // Set child to null
                current.child = null;

            } else if (current.next == null) {
                // Reconnect node at the top of the
                // stack to the tail child node
                if (stack.Count > 0) {
                    // Set the next node as the reconnected node,
                    // we will now iterate down this path
                    current.next = stack.Pop();
                    current.next.prev = current;
                }
            }
            current = current.next;
        }

        return head;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to flatten a doubly linked list
// ============================================================================
/*
// Definition for a Node.
public class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}
*/
public class Solution {
    public Node Flatten(Node head) {
        var current = head;
        var stack = new Stack<Node>();
 
        // Loop through nodes
        while (current != null) {
 
            // Check to see if node has child
            if (current.child != null) {
                // If current node has a next node, save to stack
                // so we can reconnect it to the tail
                // of the child node later
                if (current.next != null) {
                    stack.Push(current.next);
                }
 
                // Set the next node as the child,
                // we will now iterate down this path
                current.next = current.child;
 
                // Set the previous node as the current
                current.next.prev = current;
 
                // Set child to null
                current.child = null;
 
            } else if (current.next == null) {
                // Reconnect node at the top of the
                // stack to the tail child node
                if (stack.Count > 0) {
                    // Set the next node as the reconnected node,
                    // we will now iterate down this path
                    current.next = stack.Pop();
                    current.next.prev = current;
                }
            }
            current = current.next;
        }
 
        return head;
    }
}// http://programmingnotes.org/

Recursive





		
		
			2. Flatten Recursive - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to flatten a doubly linked list
// ============================================================================
/*
// Definition for a Node.
public class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}
*/
public class Solution {
    public Node Flatten(Node head) {
        Flatten(head, null);
        return head;
    }

    private Node Flatten(Node current, Node previous) {
        if (current == null) {
            return previous;
        }

        // If previous node exists, set the next and previous values
        if (previous != null) {
            previous.next = current;
            current.prev = previous;
        }

        // Save the next node so we can reconnect it to the tail
        // of the child node later
        var next = current.next;

        // Traverse down child path.
        // If children exist, this returns the last child for the current node
        var tail = Flatten(current.child, current);

        // Child path has been explored, set to null
        current.child = null;

        // Reconnect the next node to the tail child node
        return Flatten(next, tail);
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to flatten a doubly linked list
// ============================================================================
/*
// Definition for a Node.
public class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}
*/
public class Solution {
    public Node Flatten(Node head) {
        Flatten(head, null);
        return head;
    }
 
    private Node Flatten(Node current, Node previous) {
        if (current == null) {
            return previous;
        }
 
        // If previous node exists, set the next and previous values
        if (previous != null) {
            previous.next = current;
            current.prev = previous;
        }
 
        // Save the next node so we can reconnect it to the tail
        // of the child node later
        var next = current.next;
 
        // Traverse down child path.
        // If children exist, this returns the last child for the current node
        var tail = Flatten(current.child, current);
 
        // Child path has been explored, set to null
        current.child = null;
 
        // Reconnect the next node to the tail child node
        return Flatten(next, tail);
    }
}// 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,7,8,11,12,9,10,4,5,6] [1,3,2] []

C# || How To Traverse Binary Tree Zigzag Level Order Using C#

October 30, 2021 admin No comments

The following is a module with functions which demonstrates how to traverse binary tree zigzag level order using C#.

1. Zigzag Level Order – Problem Statement

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]]

Example 2:

Input: root = [1] Output: [[1]]

Example 3:

Input: root = [] Output: []

2. Zigzag Level Order – Solution

The following is a solution which demonstrates how to traverse binary tree zigzag level order.

This solution uses Breadth First Search to explore items at each level.





		
		
			2. Zigzag Level Order - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 29, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to traverse a tree zigzag level order
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
        var result = new List<IList<int>>();
        var stack = new Stack<TreeNode>();

        // Add root to stack
        if (root != null) {
            stack.Push(root);
        }

        var leftToRight = true;
        while (stack.Count > 0) {
            var queue = new Queue<TreeNode>();
            var level = new List<int>();

            // Add items at the top of the stack to the current level
            for (var itemCount = stack.Count; itemCount > 0; --itemCount) {
                var current = stack.Peek();
                stack.Pop();

                level.Add(current.val);
                queue.Enqueue(current);
            }

            // Add level to result
            result.Add(level);

            // Go through items in the queue and add them to the stack in the proper order
            for (var itemCount = queue.Count; itemCount > 0; --itemCount) {
                var current = queue.Peek();
                queue.Dequeue();

                // Add children to the stack
                // Left to right or Right to left order
                if (leftToRight) {
                    if (current.left != null) {
                        stack.Push(current.left);
                    }
                    if (current.right != null) {
                        stack.Push(current.right);
                    }
                } else {
                    if (current.right != null) {
                        stack.Push(current.right);
                    }
                    if (current.left != null) {
                        stack.Push(current.left);
                    }
                }
            }
            // Alternate order for the next level
            leftToRight = !leftToRight;
        }
        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
75
76
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 29, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to traverse a tree zigzag level order
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
        var result = new List<IList<int>>();
        var stack = new Stack<TreeNode>();
 
        // Add root to stack
        if (root != null) {
            stack.Push(root);
        }
 
        var leftToRight = true;
        while (stack.Count > 0) {
            var queue = new Queue<TreeNode>();
            var level = new List<int>();
 
            // Add items at the top of the stack to the current level
            for (var itemCount = stack.Count; itemCount > 0; --itemCount) {
                var current = stack.Peek();
                stack.Pop();
 
                level.Add(current.val);
                queue.Enqueue(current);
            }
 
            // Add level to result
            result.Add(level);
 
            // Go through items in the queue and add them to the stack in the proper order
            for (var itemCount = queue.Count; itemCount > 0; --itemCount) {
                var current = queue.Peek();
                queue.Dequeue();
 
                // Add children to the stack
                // Left to right or Right to left order
                if (leftToRight) {
                    if (current.left != null) {
                        stack.Push(current.left);
                    }
                    if (current.right != null) {
                        stack.Push(current.right);
                    }
                } else {
                    if (current.right != null) {
                        stack.Push(current.right);
                    }
                    if (current.left != null) {
                        stack.Push(current.left);
                    }
                }
            }
            // Alternate order for the next level
            leftToRight = !leftToRight;
        }
        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:

[[3],[20,9],[15,7]] [[1]] []

C# || How To Find Longest Duplicate Substring Using C#

October 30, 2021 admin No comments

The following is a module with functions which demonstrates how to find the longest duplicate substring using C#.

1. Longest Dup Substring – Problem Statement

Given a string s, consider all duplicated substrings: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.

Return any duplicated substring that has the longest possible length. If s does not have a duplicated substring, the answer is “”.

Example 1:

Input: s = "banana" Output: "ana"

Example 2:

Input: s = "abcd" Output: ""

2. Longest Dup Substring – Solution

The following is a solution which demonstrates how find the longest duplicate substring.

This solution uses Binary Search and Rolling Hash.





		
		
			2. Longest Dup Substring - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the longest duplicate substring
// ============================================================================
public class Solution {
    public string LongestDupSubstring(string s) {
        // Convert string to array of ascii integers
        // to implement constant time slice
        var nums = new int[s.Length];
        for (int index = 0; index < s.Length; ++index) {
            nums[index] = (int)s[index] - (int)'a';
        }

        // Keeps track of substring start index and length
        var startIndex = -1;
        var substrLength = -1;

        // Use binary search to find the largest possible length of a duplicate substring
        var left = 1;
        var right = s.Length;
        while (left < right) {
            var mid = left + (right - left) / 2;

            // Rolling hash (Rabin-Karp)
            var index = RollingSearch(nums, mid);

            // Substring found
            if (index != -1) {
                if (mid > substrLength) {
                    startIndex = index;
                    substrLength = mid;
                }
                left = mid + 1;

            // Substring not found
            } else {
               right = mid;
            }
        }
        return substrLength != -1 ? s.Substring(startIndex, substrLength): "";
    }

    private int RollingSearch(int[] nums, int mid) {
        var seen = new HashSet<long>();

        // Base value for the rolling hash function
        var a = 31;

        // Current hash
        var hash = Hash(nums, mid, a);

        seen.Add(hash);

        long pow = 1;
        for (var index = 1; index < mid; ++index) {
            pow *= a;
        }

        var result = -1;
        for (var index = 1; index < nums.Length - mid + 1; ++index) {
            // Compute rolling hash
            hash = RollingHash(pow, hash, nums[index - 1], nums[index + mid - 1], a);

            // Hash found
            if (seen.Contains(hash)) {
                result = index;
                break;
            }
            // Hash not found
            seen.Add(hash);
        }
        return result;
    }

    private long Hash(int[] nums, int mid, int a) {
        long h = 0;
        long aL = 1;
        for (var index = mid; index >= 1; --index) {
            h += (nums[index - 1] + 1) * aL;
            aL *= a;
        }
        return h;
    }

    private long RollingHash(long pow, long hash, int left, int right, int a) {
        return (hash - (left + 1) * pow) * a + (right + 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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the longest duplicate substring
// ============================================================================
public class Solution {
    public string LongestDupSubstring(string s) {
        // Convert string to array of ascii integers
        // to implement constant time slice
        var nums = new int[s.Length];
        for (int index = 0; index < s.Length; ++index) {
            nums[index] = (int)s[index] - (int)'a';
        }
 
        // Keeps track of substring start index and length
        var startIndex = -1;
        var substrLength = -1;
 
        // Use binary search to find the largest possible length of a duplicate substring
        var left = 1;
        var right = s.Length;
        while (left < right) {
            var mid = left + (right - left) / 2;
 
            // Rolling hash (Rabin-Karp)
            var index = RollingSearch(nums, mid);
 
            // Substring found
            if (index != -1) {
                if (mid > substrLength) {
                    startIndex = index;
                    substrLength = mid;
                }
                left = mid + 1;
 
            // Substring not found
            } else {
               right = mid;
            }
        }
        return substrLength != -1 ? s.Substring(startIndex, substrLength): "";
    }
 
    private int RollingSearch(int[] nums, int mid) {
        var seen = new HashSet<long>();
 
        // Base value for the rolling hash function
        var a = 31;
 
        // Current hash
        var hash = Hash(nums, mid, a);
 
        seen.Add(hash);
 
        long pow = 1;
        for (var index = 1; index < mid; ++index) {
            pow *= a;
        }
 
        var result = -1;
        for (var index = 1; index < nums.Length - mid + 1; ++index) {
            // Compute rolling hash
            hash = RollingHash(pow, hash, nums[index - 1], nums[index + mid - 1], a);
 
            // Hash found
            if (seen.Contains(hash)) {
                result = index;
                break;
            }
            // Hash not found
            seen.Add(hash);
        }
        return result;
    }
 
    private long Hash(int[] nums, int mid, int a) {
        long h = 0;
        long aL = 1;
        for (var index = mid; index >= 1; --index) {
            h += (nums[index - 1] + 1) * aL;
            aL *= a;
        }
        return h;
    }
 
    private long RollingHash(long pow, long hash, int left, int right, int a) {
        return (hash - (left + 1) * pow) * a + (right + 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:

"ana" ""

C# || Group Anagrams – How To Group Array Of Anagrams Using C#

October 30, 2021 admin No comments

The following is a module with functions which demonstrates how to group an array of anagrams using C#.

1. Group Anagrams – Problem Statement

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""] Output: [[""]]

Example 3:

Input: strs = ["a"] Output: [["a"]]

2. Group Anagrams – Solution

The following is a solution which demonstrates how to group an array of anagrams.

The idea of this solution is to generate a simple hash key for each anagram.

The hash key is made up consisting of a digit, and a letter. These two values represents the character count, and the letter found in the given string.

For example, given the input ["eat","tea","tan","ate","nat","bat"] we create a hash for each anagram as follows:

anagram: eat, hash: 1a1e1t anagram: tea, hash: 1a1e1t anagram: tan, hash: 1a1n1t anagram: ate, hash: 1a1e1t anagram: nat, hash: 1a1n1t anagram: bat, hash: 1a1b1t

The hash key is generated similar to the counting sort technique. We use this hash to group the anagrams together.





		
		
			2. Group Anagrams - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to group anagrams
// ============================================================================
public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        var result = new List<IList<string>>();
        var seen = new Dictionary<string, List<string>>();

        // Go through the anagrams
        foreach (var anagram in strs) {
            // Create a hash for this anagram
            var hash = Hash(anagram);

            // Check if this hash key exists
            if (!seen.ContainsKey(hash)) {
                seen[hash] = new List<string>();
            }

            // Add anagram to matching bucket
            seen[hash].Add(anagram);
        }

        // Build result
        foreach (var pair in seen) {
            result.Add(pair.Value);
        }

        return result;
    }

    private string Hash(string input) {
        var alphabet = new int[26];
        foreach (var ch in input) {
            ++alphabet[ch - 'a'];
        }
        var sb = new StringBuilder();
        for (int position = 0; position < alphabet.Length; ++position) {
            if (alphabet[position] > 0) {
                sb.Append(alphabet[position]);
                sb.Append((char)('a' + position));
            }
        }
        return sb.ToString();
    }
}// 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to group anagrams
// ============================================================================
public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        var result = new List<IList<string>>();
        var seen = new Dictionary<string, List<string>>();
 
        // Go through the anagrams
        foreach (var anagram in strs) {
            // Create a hash for this anagram
            var hash = Hash(anagram);
 
            // Check if this hash key exists
            if (!seen.ContainsKey(hash)) {
                seen[hash] = new List<string>();
            }
 
            // Add anagram to matching bucket
            seen[hash].Add(anagram);
        }
 
        // Build result
        foreach (var pair in seen) {
            result.Add(pair.Value);
        }
 
        return result;
    }
 
    private string Hash(string input) {
        var alphabet = new int[26];
        foreach (var ch in input) {
            ++alphabet[ch - 'a'];
        }
        var sb = new StringBuilder();
        for (int position = 0; position < alphabet.Length; ++position) {
            if (alphabet[position] > 0) {
                sb.Append(alphabet[position]);
                sb.Append((char)('a' + position));
            }
        }
        return sb.ToString();
    }
}// 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:

[["eat","tea","ate"],["tan","nat"],["bat"]] [[""]] [["a"]]

C# || How To Traverse Binary Tree Level Order Using C#

October 29, 2021 admin No comments

The following is a module with functions which demonstrates how to traverse binary tree level order using C#.

1. Level Order – Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1] Output: [[1]]

Example 3:

Input: root = [] Output: []

2. Level Order – Solution

The following is a solution which demonstrates how to traverse binary tree level order.

This solution uses Breadth First Search to explore items at each level.





		
		
			2. Level Order - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 29, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Determines how to traverse a tree level order
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<IList<int>> LevelOrder(TreeNode root) {
        var result = new List<IList<int>>();
        var queue = new Queue<TreeNode>();

        if (root != null) {
            queue.Enqueue(root);
        }

        while (queue.Count > 0) {
            var level = new List<int>();

            // Loop through items in the queue
            for (var itemCount = queue.Count; itemCount > 0; --itemCount) {
                var current = queue.Peek();
                queue.Dequeue();

                // Add children to the queue if they exist
                if (current.left != null) {
                    queue.Enqueue(current.left);
                }
                if (current.right != null) {
                    queue.Enqueue(current.right);
                }

                // Add current value to the level
                level.Add(current.val);
            }

            // Add items on this level to the result
            result.Add(level);
        }

        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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 29, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Determines how to traverse a tree level order
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<IList<int>> LevelOrder(TreeNode root) {
        var result = new List<IList<int>>();
        var queue = new Queue<TreeNode>();
 
        if (root != null) {
            queue.Enqueue(root);
        }
 
        while (queue.Count > 0) {
            var level = new List<int>();
 
            // Loop through items in the queue
            for (var itemCount = queue.Count; itemCount > 0; --itemCount) {
                var current = queue.Peek();
                queue.Dequeue();
 
                // Add children to the queue if they exist
                if (current.left != null) {
                    queue.Enqueue(current.left);
                }
                if (current.right != null) {
                    queue.Enqueue(current.right);
                }
 
                // Add current value to the level
                level.Add(current.val);
            }
 
            // Add items on this level to the result
            result.Add(level);
        }
 
        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:

[[3],[9,20],[15,7]] [[1]] []

C# || How To Determine When A Fresh Orange Becomes Rotten Using C#

October 29, 2021 admin No comments

The following is a module with functions which demonstrates how to determine when a fresh orange becomes rotten using C#.

1. Oranges Rotting – Problem Statement

You are given an m x n grid where each cell can have one of three values:

0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]] Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]] Output: -1 Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]] Output: 0 Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

2. Oranges Rotting – Solution

The following is a solution which demonstrates how to determine when a fresh orange becomes rotten.

This solution uses Breadth First Search when looking for fresh cells to turn rotten.





		
		
			2. Oranges Rotting - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 29, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to determine rotten oranges
// ============================================================================
public class Solution {
    public int OrangesRotting(int[][] grid) {
        var EMPTY = 0;
        var FRESH = 1;
        var ROTTEN = 2;

        var elapsed = 0;
        var freshCount = 0;
        var queue = new Queue<KeyValuePair<int, int>>();

        // Get fresh cell count and rotten cell coordinates
        for (int row = 0; row < grid.Length; ++row) {
            for (int col = 0; col < grid[row].Length; ++col) {
                if (grid[row][col] == FRESH) {
                    ++freshCount;
                } else if (grid[row][col] == ROTTEN) {
                    queue.Enqueue(new KeyValuePair<int, int>(row, col));
                }
            }
        }

        // Search directions
        var directions = new List<KeyValuePair<int, int>>() {
            // Right
            new KeyValuePair<int, int>(0, 1),
            // Left
            new KeyValuePair<int, int>(0, -1),
            // Top
            new KeyValuePair<int, int>(-1, 0),
            // Bottom
            new KeyValuePair<int, int>(1, 0),
        };

        // Look for fresh cells to turn rotten
        while (queue.Count > 0) {
            for (var itemCount = queue.Count; itemCount > 0; --itemCount) {
                var current = queue.Peek();
                queue.Dequeue();

                // Get the coordinates of the rotten cell
                var row = current.Key;
                var col = current.Value;

                // Search right, left, top, bottom to see if a fresh cell can become rotten
                foreach (var direction in directions) {
                    var newRow = row + direction.Key;
                    var newCol = col + direction.Value;

                    // If the cell is fresh in this direction, make it rotten
                    if (IsValidCell(grid, newRow, newCol) && grid[newRow][newCol] == FRESH) {
                        grid[newRow][newCol] = ROTTEN;
                        queue.Enqueue(new KeyValuePair<int, int>(newRow, newCol));
                        --freshCount;
                    }
                }
            }

            // Increment elapsed time
            if (queue.Count > 0) {
                ++elapsed;
            }
        }

        return freshCount > 0 ? -1 : elapsed;
    }

    private bool IsValidCell(int[][] grid, int row, int col) {
        return row >= 0 && row < grid.Length && col >= 0 && col < grid[row].Length;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 29, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to determine rotten oranges
// ============================================================================
public class Solution {
    public int OrangesRotting(int[][] grid) {
        var EMPTY = 0;
        var FRESH = 1;
        var ROTTEN = 2;
 
        var elapsed = 0;
        var freshCount = 0;
        var queue = new Queue<KeyValuePair<int, int>>();
 
        // Get fresh cell count and rotten cell coordinates
        for (int row = 0; row < grid.Length; ++row) {
            for (int col = 0; col < grid[row].Length; ++col) {
                if (grid[row][col] == FRESH) {
                    ++freshCount;
                } else if (grid[row][col] == ROTTEN) {
                    queue.Enqueue(new KeyValuePair<int, int>(row, col));
                }
            }
        }
 
        // Search directions
        var directions = new List<KeyValuePair<int, int>>() {
            // Right
            new KeyValuePair<int, int>(0, 1),
            // Left
            new KeyValuePair<int, int>(0, -1),
            // Top
            new KeyValuePair<int, int>(-1, 0),
            // Bottom
            new KeyValuePair<int, int>(1, 0),
        };
 
        // Look for fresh cells to turn rotten
        while (queue.Count > 0) {
            for (var itemCount = queue.Count; itemCount > 0; --itemCount) {
                var current = queue.Peek();
                queue.Dequeue();
 
                // Get the coordinates of the rotten cell
                var row = current.Key;
                var col = current.Value;
 
                // Search right, left, top, bottom to see if a fresh cell can become rotten
                foreach (var direction in directions) {
                    var newRow = row + direction.Key;
                    var newCol = col + direction.Value;
 
                    // If the cell is fresh in this direction, make it rotten
                    if (IsValidCell(grid, newRow, newCol) && grid[newRow][newCol] == FRESH) {
                        grid[newRow][newCol] = ROTTEN;
                        queue.Enqueue(new KeyValuePair<int, int>(newRow, newCol));
                        --freshCount;
                    }
                }
            }
 
            // Increment elapsed time
            if (queue.Count > 0) {
                ++elapsed;
            }
        }
 
        return freshCount > 0 ? -1 : elapsed;
    }
 
    private bool IsValidCell(int[][] grid, int row, int col) {
        return row >= 0 && row < grid.Length && col >= 0 && col < grid[row].Length;
    }
}// http://programmingnotes.org/

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

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

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

4 -1 0

C# || 3Sum Closest – How To Get 3 Numbers In Array Closest Equal To Target Value Using C#

October 28, 2021 admin No comments

The following is a module with functions which demonstrates how to get 3 numbers in an array closest equal to target value using C#.

1. 3 Sum Closest – Problem Statement

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

Input: nums = [0,0,0], target = 1 Output: 0

2. 3 Sum Closest – Solution

The following is a solution which demonstrates how to get 3 numbers in an array closest equal to target value.

This solution uses the two pointer technique to find combinations.





		
		
			2. 3 Sum Closest - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get 3 numbers closest to target value
// ============================================================================
public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        var result = 0;

        // Keep track of the solution closest to the target
        var closestDifference = int.MaxValue;

        // Sort the array
        Array.Sort(nums);

        // Loop through numbers
        for (int index = 0; index < nums.Length; ++index) {
            // Skip duplicates
            if (index > 0 && nums[index] == nums[index - 1]) {
                continue;
            }

            // Find 3 sum combination closest to the target value
            var startIndex = index + 1;
            var endIndex = nums.Length - 1;
            while (startIndex < endIndex) {
                // Get the sum
                var sum = nums[index] + nums[startIndex] + nums[endIndex];

                // Determine how close the sum is to the target value
                var difference = Math.Abs(target - sum);
                if (difference < closestDifference) {
                    closestDifference = difference;
                    result = sum;
                }

                // An exact match is found, exit
                if (difference == 0) {
                    break;

                // Sum is less than target
                } else if (sum < target) {
                    ++startIndex;

                // Sum is greater than target
                } else {
                    --endIndex;
                }
            }

            // An exact match is found, exit
            if (closestDifference == 0) {
                break;
            }
        }

        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get 3 numbers closest to target value
// ============================================================================
public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        var result = 0;
 
        // Keep track of the solution closest to the target
        var closestDifference = int.MaxValue;
 
        // Sort the array
        Array.Sort(nums);
 
        // Loop through numbers
        for (int index = 0; index < nums.Length; ++index) {
            // Skip duplicates
            if (index > 0 && nums[index] == nums[index - 1]) {
                continue;
            }
 
            // Find 3 sum combination closest to the target value
            var startIndex = index + 1;
            var endIndex = nums.Length - 1;
            while (startIndex < endIndex) {
                // Get the sum
                var sum = nums[index] + nums[startIndex] + nums[endIndex];
 
                // Determine how close the sum is to the target value
                var difference = Math.Abs(target - sum);
                if (difference < closestDifference) {
                    closestDifference = difference;
                    result = sum;
                }
 
                // An exact match is found, exit
                if (difference == 0) {
                    break;
 
                // Sum is less than target
                } else if (sum < target) {
                    ++startIndex;
 
                // Sum is greater than target
                } else {
                    --endIndex;
                }
            }
 
            // An exact match is found, exit
            if (closestDifference == 0) {
                break;
            }
        }
 
        return result;
    }
}// http://programmingnotes.org/

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

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

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

2 0

C# || 3Sum – How To Get All Triplet Combinations In Array Equal To Target Value Using C#

October 28, 2021 admin No comments

The following is a module with functions which demonstrates how to get all triplet combinations in an array equal to a target value using C#.

1. 3 Sum – Problem Statement

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = [] Output: []

Example 3:

Input: nums = [0] Output: []

2. 3 Sum – Solution

The following is a solution which demonstrates how to get all triplet combinations in an array equal to a target value.

This solution uses the two pointer technique to find combinations.





		
		
			2. 3 Sum - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get 3 numbers equal to target value
// ============================================================================
public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        var result = new List<IList<int>>();

        // Sort the array
        Array.Sort(nums);

        // Set the target value
        var target = 0;

        // Loop through numbers
        for (int index = 0; index < nums.Length; ++index) {
            // Skip duplicates
            if (index > 0 && nums[index] == nums[index - 1]) {
                continue;
            }

            // Find all 3 sum combinations that equal the target value
            var startIndex = index + 1;
            var endIndex = nums.Length - 1;
            while (startIndex < endIndex) {
                // Get the sum
                var sum = nums[index] + nums[startIndex] + nums[endIndex];

                // Sum equals target
                if (sum == target) {
                    // Add values to results when a target is found
                    var valueStart = nums[startIndex];
                    var valueEnd = nums[endIndex];
                    result.Add(new List<int>{nums[index], valueStart, valueEnd});

                    // Advance past duplicate items to the 'next' values
                    // at the start and end of the array
                    while (startIndex < endIndex && valueStart == nums[startIndex]) {
                        ++startIndex;
                    }
                    while (startIndex < endIndex && valueEnd == nums[endIndex]) {
                        --endIndex;
                    }

                // Sum is less than target
                } else if (sum < target) {
                    ++startIndex;

                // Sum is greater than target
                } else {
                    --endIndex;
                }
            }
        }

        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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get 3 numbers equal to target value
// ============================================================================
public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        var result = new List<IList<int>>();
 
        // Sort the array
        Array.Sort(nums);
 
        // Set the target value
        var target = 0;
 
        // Loop through numbers
        for (int index = 0; index < nums.Length; ++index) {
            // Skip duplicates
            if (index > 0 && nums[index] == nums[index - 1]) {
                continue;
            }
 
            // Find all 3 sum combinations that equal the target value
            var startIndex = index + 1;
            var endIndex = nums.Length - 1;
            while (startIndex < endIndex) {
                // Get the sum
                var sum = nums[index] + nums[startIndex] + nums[endIndex];
 
                // Sum equals target
                if (sum == target) {
                    // Add values to results when a target is found
                    var valueStart = nums[startIndex];
                    var valueEnd = nums[endIndex];
                    result.Add(new List<int>{nums[index], valueStart, valueEnd});
 
                    // Advance past duplicate items to the 'next' values
                    // at the start and end of the array
                    while (startIndex < endIndex && valueStart == nums[startIndex]) {
                        ++startIndex;
                    }
                    while (startIndex < endIndex && valueEnd == nums[endIndex]) {
                        --endIndex;
                    }
 
                // Sum is less than target
                } else if (sum < target) {
                    ++startIndex;
 
                // Sum is greater than target
                } else {
                    --endIndex;
                }
            }
        }
 
        return result;
    }
}// http://programmingnotes.org/

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

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

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

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

C# || Two Sum II – How To Get Two Numbers In Sorted Array Equal To Target Value Using C#

October 28, 2021 admin No comments

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

1. Two Sum II – Problem Statement

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index₁] and numbers[index₂] where 1 <= index₁ < index₂ <= numbers.length.

Return the indices of the two numbers, index₁ and index₂, added by one as an integer array [index₁, index₂] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Example 1:

Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6 Output: [1,3] Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1 Output: [1,2] Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

2. Two Sum II – Solution

The following is a solution which demonstrates how to get two numbers in sorted array equal to target value.

In this solution, Binary Search is used to find the two numbers.





		
		
			2. Two Sum II - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        var result = new int[2];

        var lo = 0;
        var hi = numbers.Length - 1;

        while (lo < hi) {
            var m = lo + (hi - lo) / 2;
            var sum = numbers[lo] + numbers[hi];

            if (sum == target) {
                result[0] = lo + 1;
                result[1] = hi + 1;
                break;
            } else if (sum < target) {
                // Determine if mid is less than the remaining value
                // Increase lo to equal mid if so
                if (numbers[m] < target - numbers[hi]) {
                    lo = m + 1;
                } else {
                    lo = lo + 1;
                }
            } else {
                // Determine if mid is greater than the remaining value
                // Decrease hi to equal mid if so
                if (numbers[m] > target - numbers[lo]) {
                    hi = m - 1;
                } else {
                    hi = hi - 1;
                }
            }
        }

        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        var result = new int[2];
 
        var lo = 0;
        var hi = numbers.Length - 1;
 
        while (lo < hi) {
            var m = lo + (hi - lo) / 2;
            var sum = numbers[lo] + numbers[hi];
 
            if (sum == target) {
                result[0] = lo + 1;
                result[1] = hi + 1;
                break;
            } else if (sum < target) {
                // Determine if mid is less than the remaining value
                // Increase lo to equal mid if so
                if (numbers[m] < target - numbers[hi]) {
                    lo = m + 1;
                } else {
                    lo = lo + 1;
                }
            } else {
                // Determine if mid is greater than the remaining value
                // Decrease hi to equal mid if so
                if (numbers[m] > target - numbers[lo]) {
                    hi = m - 1;
                } else {
                    hi = hi - 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:

[1,2] [1,3] [1,2]

C# || Two Sum – How To Get Two Numbers In Array Equal To Target Value Using C#

October 28, 2021 admin No comments

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

1. Two Sum – Problem Statement

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9 Output: [0,1] Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6 Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6 Output: [0,1]

2. Two Sum – Solution

The following is a solution which demonstrates how to get two numbers in array equal to target value.





		
		
			2. Two Sum - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        var result = new int[2];

        // Use a map dictionary to keep track of the numbers already seen
        var seen = new Dictionary<int, int>();

        // Go through numbers
        for (int index = 0; index < nums.Length; ++index) {
            // Subtract the target from the current array index.
            // The result of this operation is the second number
            // that is needed to equal the target value
            int remaining = target - nums[index];

            // Check if we have 'seen' this remaining value before
            if (seen.ContainsKey(remaining)) {
                result[0] = seen[remaining];
                result[1] = index;
                break;
            }

            // Save the number and index
            seen[nums[index]] = index;
        }

        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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        var result = new int[2];
 
        // Use a map dictionary to keep track of the numbers already seen
        var seen = new Dictionary<int, int>();
 
        // Go through numbers
        for (int index = 0; index < nums.Length; ++index) {
            // Subtract the target from the current array index.
            // The result of this operation is the second number
            // that is needed to equal the target value
            int remaining = target - nums[index];
 
            // Check if we have 'seen' this remaining value before
            if (seen.ContainsKey(remaining)) {
                result[0] = seen[remaining];
                result[1] = index;
                break;
            }
 
            // Save the number and index
            seen[nums[index]] = 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:

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

C# || How To Generate Unique Subsets From Array With Duplicate Values Using C#

October 27, 2021 admin No comments

The following is a module with functions which demonstrates how to generate unique subsets from an array with duplicate values using C#.

1. Subsets With Dup – Problem Statement

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,2] Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Example 2:

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

2. Subsets With Dup – Solution

The following is a solution which demonstrates how to generate unique subsets from an array with duplicate values.





		
		
			2. Subsets With Dup - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 27, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to generate unique permutations
// ============================================================================
public class Solution {
    List<IList<int>> result = new List<IList<int>>();

    public IList<IList<int>> SubsetsWithDup(int[] nums) {
        // Sort array
        Array.Sort(nums);
        Generate(nums, 0, new List<int>());
        return result;
    }

    public void Generate(int[] nums, int startIndex, List<int> combination) {
        result.Add(new List<int>(combination));

        for (int index = startIndex; index < nums.Length; ++index) {
            // Check to see if this number has been visited
            if (index > startIndex && nums[index] == nums[index - 1]) {
                continue;
            }

            // Add this number to the combination
            combination.Add(nums[index]);

            // Keep generating subsets
            Generate(nums, index + 1, combination);

            // Remove last item as its already been explored
            combination.RemoveAt(combination.Count - 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 27, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to generate unique permutations
// ============================================================================
public class Solution {
    List<IList<int>> result = new List<IList<int>>();
 
    public IList<IList<int>> SubsetsWithDup(int[] nums) {
        // Sort array
        Array.Sort(nums);
        Generate(nums, 0, new List<int>());
        return result;
    }
 
    public void Generate(int[] nums, int startIndex, List<int> combination) {
        result.Add(new List<int>(combination));
 
        for (int index = startIndex; index < nums.Length; ++index) {
            // Check to see if this number has been visited
            if (index > startIndex && nums[index] == nums[index - 1]) {
                continue;
            }
 
            // Add this number to the combination
            combination.Add(nums[index]);
 
            // Keep generating subsets
            Generate(nums, index + 1, combination);
 
            // Remove last item as its already been explored
            combination.RemoveAt(combination.Count - 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:

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

C# || How To Generate Subsets From Array With Distinct Values Using C#

October 27, 2021 admin No comments

The following is a module with functions which demonstrates how to generate subsets from an array with distinct values using C#.

1. Subsets – Problem Statement

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

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

2. Subsets – Solution

The following is a solution which demonstrates how to generate subsets from an array with distinct values.

This solution uses bit manipulation to generate 2^n possibilities based of the array length, and then adds items to the result list if the array index is a valid bit based off of the subset possibilities.





		
		
			2. Subsets - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 27, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to generate subsets
// ============================================================================
public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        var result = new List<IList<int>>();

        // (2^n possibilities)
        var possibilities = (1 << nums.Length);

        // Generate subsets (2^n possibilities)
        for (int possibility = 0; possibility < possibilities; ++possibility) {
            var subset = new List<int>();

            // Add item to result if index is a valid bit
            // based off of the subset possibilities
            for (int index = 0; index < nums.Length; ++index) {
                if (((possibility >> index) & 1) == 1) {
                    subset.Add(nums[index]);
                }
            }
            result.Add(subset);
        }

        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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 27, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to generate subsets
// ============================================================================
public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        var result = new List<IList<int>>();
 
        // (2^n possibilities)
        var possibilities = (1 << nums.Length);
 
        // Generate subsets (2^n possibilities)
        for (int possibility = 0; possibility < possibilities; ++possibility) {
            var subset = new List<int>();
 
            // Add item to result if index is a valid bit
            // based off of the subset possibilities
            for (int index = 0; index < nums.Length; ++index) {
                if (((possibility >> index) & 1) == 1) {
                    subset.Add(nums[index]);
                }
            }
            result.Add(subset);
        }
 
        return result;
    }
}// http://programmingnotes.org/

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

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

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

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

C# || How To Generate Next Permutation From Array Using C#

October 27, 2021 admin 1 Comment

The following is a module with functions which demonstrates how to generate the next permutation from an array using C#.

1. Next Permutation – Problem Statement

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1,1,5] Output: [1,5,1]

Example 4:

Input: nums = [1] Output: [1]

2. Next Permutation – Solution

The following is a solution which demonstrates how to generate the next permutation from an array





		
		
			2. Next Permutation - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 27, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to generate the next permutation
// ============================================================================
public class Solution {
    public void NextPermutation(int[] nums) {
        // Starting from the end, look for the first index that is not in descending order
        var startIndex = nums.Length - 2;

        while (startIndex >= 0) {
            // Find first decreasing element
            if (nums[startIndex] < nums[startIndex + 1]) {
                break;
            }
            --startIndex;
        }

        if (startIndex >= 0) {
            // Starting from the end, look for the first element greater than the start index
            int endIndex = nums.Length - 1;

            while (endIndex > startIndex) {
                // Find first greater element
                if (nums[endIndex] > nums[startIndex]) {
                    break;
                }
                --endIndex;
            }

            // Swap first and last elements
            Swap(ref nums[startIndex], ref nums[endIndex]);
        }

        // Reverse the array
        Reverse(nums, startIndex + 1);
    }

    private void Reverse(int[] nums, int startIndex) {
        for (int start = startIndex, end = nums.Length - 1; start < end; ++start, --end) {
            Swap(ref nums[start], ref nums[end]);
        }
    }

    private void Swap(ref int a, ref int b) {
        var tmp = a;
        a = b;
        b = tmp;
    }
}// 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 27, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to generate the next permutation
// ============================================================================
public class Solution {
    public void NextPermutation(int[] nums) {
        // Starting from the end, look for the first index that is not in descending order
        var startIndex = nums.Length - 2;
 
        while (startIndex >= 0) {
            // Find first decreasing element
            if (nums[startIndex] < nums[startIndex + 1]) {
                break;
            }
            --startIndex;
        }
 
        if (startIndex >= 0) {
            // Starting from the end, look for the first element greater than the start index
            int endIndex = nums.Length - 1;
 
            while (endIndex > startIndex) {
                // Find first greater element
                if (nums[endIndex] > nums[startIndex]) {
                    break;
                }
                --endIndex;
            }
 
            // Swap first and last elements
            Swap(ref nums[startIndex], ref nums[endIndex]);
        }
 
        // Reverse the array
        Reverse(nums, startIndex + 1);
    }
 
    private void Reverse(int[] nums, int startIndex) {
        for (int start = startIndex, end = nums.Length - 1; start < end; ++start, --end) {
            Swap(ref nums[start], ref nums[end]);
        }
    }
 
    private void Swap(ref int a, ref int b) {
        var tmp = a;
        a = b;
        b = tmp;
    }
}// http://programmingnotes.org/

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

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

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

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

C# || How To Generate Unique Permutations From Array With Duplicate Values Using C#

October 27, 2021 admin No comments

The following is a module with functions which demonstrates how to generate unique permutations from an array with duplicate values using C#.

1. Permute Unique – Problem Statement

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

Input: nums = [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1]]

Example 2:

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

2. Permute Unique – Solution

The following is a solution which demonstrates how to generate unique permutations from an array with duplicate values.





		
		
			2. Permute Unique - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 27, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to generate unique permutations
// ============================================================================
public class Solution {
    private List<IList<int>> result = new List<IList<int>>();

    public IList<IList<int>> PermuteUnique(int[] nums) {
        // Sort Array
        Array.Sort(nums);
        Generate(nums, new List<int>(), new bool[nums.Length]);
        return result;
    }

    private void Generate(int[] nums, List<int> combination, bool[] visited) {
        if (combination.Count == nums.Length) {
            result.Add(new List<int>(combination));
            return;
        }

        for (int index = 0; index < nums.Length; ++index) {
            // Check to see if this number has been visited
            if (visited[index]) {
                continue;
            } else if (index > 0 && nums[index] == nums[index - 1] && !visited[index - 1]) {
                continue;
            }

            // Set that this index has been visited
            visited[index] = true;

            // Add this number to the combination
            combination.Add(nums[index]);

            // Keep generating permutations
            Generate(nums, combination, visited);

            // Unset that this index has been visited
            visited[index] = false;

            // Remove last item as its already been explored
            combination.RemoveAt(combination.Count - 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 27, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to generate unique permutations
// ============================================================================
public class Solution {
    private List<IList<int>> result = new List<IList<int>>();
 
    public IList<IList<int>> PermuteUnique(int[] nums) {
        // Sort Array
        Array.Sort(nums);
        Generate(nums, new List<int>(), new bool[nums.Length]);
        return result;
    }
 
    private void Generate(int[] nums, List<int> combination, bool[] visited) {
        if (combination.Count == nums.Length) {
            result.Add(new List<int>(combination));
            return;
        }
 
        for (int index = 0; index < nums.Length; ++index) {
            // Check to see if this number has been visited
            if (visited[index]) {
                continue;
            } else if (index > 0 && nums[index] == nums[index - 1] && !visited[index - 1]) {
                continue;
            }
 
            // Set that this index has been visited
            visited[index] = true;
 
            // Add this number to the combination
            combination.Add(nums[index]);
 
            // Keep generating permutations
            Generate(nums, combination, visited);
 
            // Unset that this index has been visited
            visited[index] = false;
 
            // Remove last item as its already been explored
            combination.RemoveAt(combination.Count - 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:

[[1,1,2],[1,2,1],[2,1,1]] [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Monthly Archives: October 2021

C# || How To Flatten A Multilevel Doubly Linked List Using C#

C# || How To Traverse Binary Tree Zigzag Level Order Using C#

C# || How To Find Longest Duplicate Substring Using C#

C# || Group Anagrams – How To Group Array Of Anagrams Using C#

C# || How To Traverse Binary Tree Level Order Using C#

C# || How To Determine When A Fresh Orange Becomes Rotten Using C#

C# || 3Sum Closest – How To Get 3 Numbers In Array Closest Equal To Target Value Using C#

C# || 3Sum – How To Get All Triplet Combinations In Array Equal To Target Value Using C#

C# || Two Sum II – How To Get Two Numbers In Sorted Array Equal To Target Value Using C#

C# || Two Sum – How To Get Two Numbers In Array Equal To Target Value Using C#

C# || How To Generate Unique Subsets From Array With Duplicate Values Using C#

C# || How To Generate Subsets From Array With Distinct Values Using C#

C# || How To Generate Next Permutation From Array Using C#

C# || How To Generate Unique Permutations From Array With Duplicate Values Using C#

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories