## C# || How To Flatten A Multilevel Doubly Linked List Using C# 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/ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859 // ============================================================================//    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/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748 // ============================================================================//    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# 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: [,[20,9],[15,7]] ```

Example 2:

``` Input: root =  Output: [] ```

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/ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576 // ============================================================================//    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:

``` [,[20,9],[15,7]] [] [] ```

## C# || How To Find Longest Duplicate Substring Using C# 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/ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091 // ============================================================================//    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# 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; 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/ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849 // ============================================================================//    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;        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# 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: [,[9,20],[15,7]] ```

Example 2:

``` Input: root =  Output: [] ```

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/ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556 // ============================================================================//    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:

``` [,[9,20],[15,7]] [] [] ```

## C# || How To Determine When A Fresh Orange Becomes Rotten Using C# 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/ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677 // ============================================================================//    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# 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/ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061 // ============================================================================//    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# 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 =  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/ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061 // ============================================================================//    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# 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[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] 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; 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 = lo + 1; result = 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/ 1234567891011121314151617181920212223242526272829303132333435363738394041424344 // ============================================================================//    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;         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 = lo + 1;                result = 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# 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 + nums == 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; // 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 = seen[remaining]; result = index; break; } // Save the number and index seen[nums[index]] = index; } return result; } }// http://programmingnotes.org/ 1234567891011121314151617181920212223242526272829303132333435 // ============================================================================//    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;         // 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 = seen[remaining];                result = 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# 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,2],[1,2,2],,[2,2]] ```

Example 2:

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

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/ 12345678910111213141516171819202122232425262728293031323334353637 // ============================================================================//    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,2],[1,2,2],,[2,2]] [[],] ```

## C# || How To Generate Subsets From Array With Distinct Values Using C# 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,3],[2,3],[1,2,3]] ```

Example 2:

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

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/ 12345678910111213141516171819202122232425262728293031 // ============================================================================//    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,3],[2,3],[1,2,3]] [[],] ```

## C# || How To Generate Next Permutation From Array Using C# 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 =  Output:  ```

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/ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152 // ============================================================================//    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]  ```

## C# || How To Generate Unique Permutations From Array With Duplicate Values Using C# 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/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748 // ============================================================================//    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]] ```