admin

Author Archives: admin

C# || How To Get Total Sum Root To Leaf Binary Numbers In Binary Tree Using C#

January 10, 2022 admin No comments

The following is a module with functions which demonstrates how to get the total sum root to leaf binary numbers in a binary tree using C#.

1. Sum Root To Leaf – Problem Statement

You are given the root of a binary tree where each node has a value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit.

For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return the sum of these numbers.

The test cases are generated so that the answer fits in a 32-bits integer.

A leaf node is a node with no children.

Example 1:

Input: root = [1,0,1,0,1,0,1] Output: 22 Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

Example 2:

Input: root = [0] Output: 0

2. Sum Root To Leaf – Solution

The following is a solution which demonstrates how to get the total sum root to leaf binary numbers in a binary tree.

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





		
		
			2. Sum Root To Leaf - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 10, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get sum root to leaf binary numbers
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int SumRootToLeaf(TreeNode root) {
        return Traverse(root, 0);
    }
    private int Traverse(TreeNode node, int currentSum) {
        if (node == null) {
            return 0;
        }
        // Calculate current sum
        currentSum = (currentSum * 2) + node.val;

        // We have reached a leaf node
        if (node.left == null && node.right == null) {
            return currentSum;
        }
        // Keep traversing left and right calculating the sum
        return Traverse(node.left, currentSum) + Traverse(node.right, currentSum);
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 10, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get sum root to leaf binary numbers
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int SumRootToLeaf(TreeNode root) {
        return Traverse(root, 0);
    }
    private int Traverse(TreeNode node, int currentSum) {
        if (node == null) {
            return 0;
        }
        // Calculate current sum
        currentSum = (currentSum * 2) + node.val;
 
        // We have reached a leaf node
        if (node.left == null && node.right == null) {
            return currentSum;
        }
        // Keep traversing left and right calculating the sum
        return Traverse(node.left, currentSum) + Traverse(node.right, currentSum);
    }
}// http://programmingnotes.org/

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

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

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

22 0

Angular || How To Create A Simple Weather Forecast App Using Angular

December 22, 2021 admin 2 Comments

The following is an implementation which demonstrates how to create a simple weather forecast app using Angular.

This project allows you to view the current weather conditions, as well as a 16 day future weather forecast. Weather locations are searched by ip address (on initial page load), gps position, and by searching by entering a city, state, or region in the search box.

All location and weather information is obtained by using real data from APIs. Geolocation is used to predict nearest location match.

Angular Weather Forecast Source

Angular Weather Forecast Demo

1. Get Started

To get started, make sure you have a package manager like Node.js installed. Node.js is used to install packages.

You’ll also want to have Angular cli installed. Visit the official documentation for more information on how this is done.

Next, navigate to the project directory in the terminal, then run the following commands (Node.js):

Project Setup

npm install

Compiles and hot-reloads for development

npm run start

2. Features

This project implements a simple weather forecast app which has the following features:

Display the current weather and 16 day daily future forecast for a location Search weather by GPS position location, ip address location, and/or by city, state, region Make API calls for each of the above actions Make use of multiple components to display information

3. Screenshots

Initial weather information for a current location based off ip address

Custom scroll animation when viewing daily forecast

Getting weather information from current GPS position

Result from entering a custom search location

Responsive view

4. Download

Angular Weather Forecast Source

Angular Weather Forecast Demo

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.

JavaScript || How To Use Geolocation To Get Current Position With Promises Using Vanilla JavaScript

December 15, 2021 admin No comments

The following is a module with functions which demonstrates how to use geolocation to get the device current position with promises using vanilla JavaScript.

The following function is a wrapper for the navigator.geolocation.getCurrentPosition, updated to use promises to run as an asynchronous operation.

1. Get Current Position

The example below demonstrates the use of ‘Utils.getCurrentPosition‘ to get the current position of the device.





		
		
			1. Get Current Position
			
JavaScript
			
			// Get Current Position

<script>
(async () => {
    try {
        // Get device position
        let position = await Utils.getCurrentPosition();
        console.log(position);
        alert(`Latitude: ${position.coords.latitude}, Longitude: ${position.coords.longitude}`);
    } catch (error) {
        console.log(error);
        alert(`Error Code: ${error.code}, Error Message: ${error.message}`);
    }
})();
</script>

// example output:
/*
    {
        "coords":
        {   
            "accuracy": 13.094
            "altitude": null
            "altitudeAccuracy": null
            "heading": null
            "latitude": 36.4458083
            "longitude": -114.6677835
            "speed": null
        }
        "timestamp": 1639609018611
    }
*/
			
				
					
				
					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
				
						// Get Current Position
 
<script>
(async () => {
    try {
        // Get device position
        let position = await Utils.getCurrentPosition();
        console.log(position);
        alert(`Latitude: ${position.coords.latitude}, Longitude: ${position.coords.longitude}`);
    } catch (error) {
        console.log(error);
        alert(`Error Code: ${error.code}, Error Message: ${error.message}`);
    }
})();
</script>
 
// example output:
/*
    {
        "coords":
        {   
            "accuracy": 13.094
            "altitude": null
            "altitudeAccuracy": null
            "heading": null
            "latitude": 36.4458083
            "longitude": -114.6677835
            "speed": null
        }
        "timestamp": 1639609018611
    }
*/

3. Utils Namespace

The following is the Utils.js Namespace. Include this in your project to start using!





		
		
			Utils.js Namespace
			
JavaScript
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 15, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Utils.js
//    Description: Javascript that handles general utility functions
// ============================================================================
/**
* NAMESPACE: Utils
* USE: Handles general utility functions.
*/
var Utils = Utils || {};
(function(namespace) {
    'use strict';

    // Property to hold public variables and functions
    let exposed = namespace;

    /**
    * FUNCTION: getCurrentPosition
    * USE: Gets the current position of the device
    * @param options: The PositionOptions
    * @return: A promise that will contain the GeolocationPosition of the device on completion
    */
    exposed.getCurrentPosition = (options = null) => {
        return new Promise((resolve, reject) => {
            if (navigator && navigator.geolocation) {
                navigator.geolocation.getCurrentPosition(resolve, reject, options);
            } else {
                reject(new Error('Geolocation is not supported by this environment'));
            }
        });
    }  
    
    (function (factory) {
        if (typeof define === 'function' && define.amd) {
            define([], factory);
        } else if (typeof exports === 'object') {
            module.exports = factory();
        }
    }(function() { return namespace; }));      
}(Utils)); // http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 15, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Utils.js
//    Description: Javascript that handles general utility functions
// ============================================================================
/**
* NAMESPACE: Utils
* USE: Handles general utility functions.
*/
var Utils = Utils || {};
(function(namespace) {
    'use strict';
 
    // Property to hold public variables and functions
    let exposed = namespace;
 
    /**
    * FUNCTION: getCurrentPosition
    * USE: Gets the current position of the device
    * @param options: The PositionOptions
    * @return: A promise that will contain the GeolocationPosition of the device on completion
    */
    exposed.getCurrentPosition = (options = null) => {
        return new Promise((resolve, reject) => {
            if (navigator && navigator.geolocation) {
                navigator.geolocation.getCurrentPosition(resolve, reject, options);
            } else {
                reject(new Error('Geolocation is not supported by this environment'));
            }
        });
    }  
    
    (function (factory) {
        if (typeof define === 'function' && define.amd) {
            define([], factory);
        } else if (typeof exports === 'object') {
            module.exports = factory();
        }
    }(function() { return namespace; }));      
}(Utils)); // 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.

Angular || How To Resolve Issue: “Module Parse Failed: Unexpected Character – You May Need An Appropriate Loader” Using Angular

December 14, 2021 admin No comments

The following is a page which demonstrates how to resolve the issue: “Module parse failed: Unexpected character ”. You may need an appropriate loader to handle this file type, currently no loaders are configured to process this file” using Angular.

Contents

1. Overview 2. Install Custom Webpack Config Package 3. Update angular.json 4. Create Custom Webpack Config File 5. Rebuild Project

1. Overview

This error basically means there is no appropriate webpack file loader installed in the project to handle the file being referenced.

Out of the box, webpack only understands JavaScript and JSON files. File loaders allow webpack to process other types of files and convert them into valid modules that can be consumed by our application.

This page will demonstrate how to use webpack Asset Modules to configure the appropriate file loader for our project.

Asset Modules are loaders that specifies how a file should be handled. There are 4 module types:

asset/resource: Emits a separate file and exports the URL. (file-loader) asset/inline: Exports a data URI of the asset. (url-loader) asset/source: Exports the source code of the asset. (raw-loader) asset: Automatically chooses between exporting a data URI and emitting a separate file. (url-loader with asset size limit)

If you are using >= webpack 5, you don’t need to install anything. These are included.

2. Install Custom Webpack Config Package

To configure a file loader in our Angular project, we need to allow for custom webpack configurations.

In the terminal, run the following command from your project directory. This command installs a package that allows for custom webpack build configurations with Angular. The custom configuration will allow us to configure the proper file loader for use in our project.

npm i -D @angular-builders/custom-webpack

3. Update angular.json

To tell Angular to use the custom build process, we need to update src/angular.json.

In src/angular.json, wherever ‘@angular-devkit/build-angular‘ is referenced, replace the value with ‘@angular-builders/custom-webpack‘.

For example:

'@angular-devkit/build-angular:browser' will be changed to '@angular-builders/custom-webpack:browser' '@angular-devkit/build-angular:dev-server' will be changed to '@angular-builders/custom-webpack:dev-server'

The following is a sample of src/angular.json after making the above changes:





		
		
			3. Sample angular.json
			

			
			...
"architect": {
    "build": {
        "builder": "@angular-builders/custom-webpack:browser",
        ...
    },
    ...
    "serve": {
        "builder": "@angular-builders/custom-webpack:dev-server",
        ...
    }
    ...
...
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
				
						...
"architect": {
    "build": {
        "builder": "@angular-builders/custom-webpack:browser",
        ...
    },
    ...
    "serve": {
        "builder": "@angular-builders/custom-webpack:dev-server",
        ...
    }
    ...
...

After the changes above have been made, we need to add a field that specifies the custom webpack config file path. It should be added in the following section of src/angular.json:





		
		
			3. Sample angular.json - Add customWebpackConfig
			

			
			...
"architect": {
    "build": {
        "builder": "@angular-builders/custom-webpack:browser",
        "options": {
            ...
            "customWebpackConfig": {
                "path": "./extra-webpack.config.js"
            },
            ...
        }
        ...
    },
    ...
...
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
				
						...
"architect": {
    "build": {
        "builder": "@angular-builders/custom-webpack:browser",
        "options": {
            ...
            "customWebpackConfig": {
                "path": "./extra-webpack.config.js"
            },
            ...
        }
        ...
    },
    ...
...

The file ‘extra-webpack.config‘ is where we will define the file loader.

4. Create Custom Webpack Config File

Create the ‘extra-webpack.config‘ file. It should be placed in the same path as specified in the ‘customWebpackConfig‘ node of src/angular.json.

The following is a sample ‘extra-webpack.config’ file. This file configures an Asset Module file loader rule for images.





		
		
			4. Create Custom Webpack Config File
			
JavaScript
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 14, 2021
//    Taken From: http://programmingnotes.org/
//    File:  extra-webpack.config.js
//    Description: Configures an Asset Module file loader for images
// ============================================================================
module.exports = {
    module: {
        rules: [
            {
                test: /\.(png|jpg|gif)$/i,
                type: 'asset',
            },
        ],
    },
};
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 14, 2021
//    Taken From: http://programmingnotes.org/
//    File:  extra-webpack.config.js
//    Description: Configures an Asset Module file loader for images
// ============================================================================
module.exports = {
    module: {
        rules: [
            {
                test: /\.(png|jpg|gif)$/i,
                type: 'asset',
            },
        ],
    },
};

For more example configurations, visit the official documentation.

5. Rebuild Project

After making the above changes, save, and restart your project / server.

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.

Angular || How To Resolve Issue: “Cannot find name ‘require'” Using Angular

December 14, 2021 admin No comments

The following is a page which demonstrates how to resolve the issue: “Cannot find name ‘require’. Do you need to install type definitions for node?” using Angular.

1. Install Package Definition

The type definition for node may not be installed. In the terminal, run the following command from your project directory. This command installs a package that defines require.

npm i --save-dev @types/node

Note: If the package is already installed, go to the next step.

2. Update tsconfig.json & tsconfig.app.json

Tell TypeScript to globally include type definitions by updating and adding ‘node‘ to the ‘types‘ field in src/tsconfig.json and src/tsconfig.app.json.





		
		
			2. Update tsconfig.json
			

			
			...
"compilerOptions": {
    ...
    "types": [ "node" ],
    ...
},
...
			
				
					
				
					1
2
3
4
5
6
7
				
						...
"compilerOptions": {
    ...
    "types": [ "node" ],
    ...
},
...





		
		
			2. Update tsconfig.app.json
			

			
			...
"compilerOptions": {
    ...
    "types": [ "node" ],
    ...
},
...
			
				
					
				
					1
2
3
4
5
6
7
				
						...
"compilerOptions": {
    ...
    "types": [ "node" ],
    ...
},
...

3. Rebuild Project

After making the above changes, save, and restart your project / server.

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.

Angular || How To Create A Simple Personal Contact List Using Angular

December 13, 2021 admin No comments

The following is an implementation which demonstrates how to create a simple personal contact list using Angular.

This project allows you to add a new contact, update an existing contact, and delete a contact. All contacts are retrieved and updated using web request calls on a mock API.

Angular Contact List Source

Angular Contact List Demo

1. Get Started

To get started, make sure you have a package manager like Node.js installed. Node.js is used to install packages.

You’ll also want to have Angular cli installed. Visit the official documentation for more information on how this is done.

Next, navigate to the project directory in the terminal, then run the following commands (Node.js):

Project Setup

npm install

Compiles and hot-reloads for development

npm run start

2. Features

This project implements a simple personal contact list which demonstrates how to:

Work with data, methods, conditional statements, and events Create, update, view, and delete contacts from the system Make API calls for each of the above actions Use tables, forms, and form validation

3. Screenshots

Initial Contact List Fetched From API

Adding A New Contact

Contact List With New Contact Added

Updating A Contact

Contact List With New Entries

4. Download

Angular Contact List Source

Angular Contact List Demo

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.

C# || Jump Game III – How To Check If You Can Reach Target Value In Array Using C#

December 08, 2021 admin No comments

The following is a module with functions which demonstrates how to check if you can reach a target value in an array using C#.

1. Can Reach – Problem Statement

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i – arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5 Output: true Explanation: All possible ways to reach at index 3 with value 0 are: index 5 -> index 4 -> index 1 -> index 3 index 5 -> index 6 -> index 4 -> index 1 -> index 3

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0 Output: true Explanation: One possible way to reach at index 3 with value 0 is: index 0 -> index 4 -> index 1 -> index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2 Output: false Explanation: There is no way to reach at index 1 with value 0.

2. Can Reach – Solution

The following are two solutions which demonstrates how to check if you can reach a target value in an array.

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





		
		
			2. Can Reach - DFS - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 8, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Determines if a target value can be reached in an array
// ============================================================================
public class Solution {
    public bool CanReach(int[] arr, int start) {
        var visited = new bool[arr.Length];
        return DFS(arr, start, visited);
    }
    public bool DFS(int[] arr, int currentIndex, bool[] visited) {
        // Make sure parameters are in bounds
        if (currentIndex < 0 || currentIndex >= arr.Length) {
            return false;
        }
        // Check to see if the index has been visited
        if (visited[currentIndex]) {
            return false;
        }
        // Check to see if we found the target value
        if (arr[currentIndex] == 0) {
            return true;
        }
        // Mark current index as visited
        visited[currentIndex] = true;

        // Keep searching forwards and backwards
        var forwards = currentIndex + arr[currentIndex];
        var backwards = currentIndex - arr[currentIndex];

        return DFS(arr, backwards, visited) || DFS(arr, forwards, visited);
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 8, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Determines if a target value can be reached in an array
// ============================================================================
public class Solution {
    public bool CanReach(int[] arr, int start) {
        var visited = new bool[arr.Length];
        return DFS(arr, start, visited);
    }
    public bool DFS(int[] arr, int currentIndex, bool[] visited) {
        // Make sure parameters are in bounds
        if (currentIndex < 0 || currentIndex >= arr.Length) {
            return false;
        }
        // Check to see if the index has been visited
        if (visited[currentIndex]) {
            return false;
        }
        // Check to see if we found the target value
        if (arr[currentIndex] == 0) {
            return true;
        }
        // Mark current index as visited
        visited[currentIndex] = true;
 
        // Keep searching forwards and backwards
        var forwards = currentIndex + arr[currentIndex];
        var backwards = currentIndex - arr[currentIndex];
 
        return DFS(arr, backwards, visited) || DFS(arr, forwards, visited);
    }
}// http://programmingnotes.org/

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





		
		
			2. Can Reach - BFS - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 8, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Determines if a target value can be reached in an array
// ============================================================================
public class Solution {
    public bool CanReach(int[] arr, int start) {
        var visited = new bool[arr.Length];
        var queue = new Queue<int>();

        queue.Enqueue(start);

        while (queue.Count > 0) {
            var currentIndex = queue.Dequeue();

            // Check to see if we found the target value
            if (arr[currentIndex] == 0) {
                return true;
            }
            // Mark current index as visited
            visited[currentIndex] = true;

            // Keep searching forwards and backwards
            var forwards = currentIndex + arr[currentIndex];
            var backwards = currentIndex - arr[currentIndex];
            var directions = new List<int>{forwards, backwards};

            foreach (var direction in directions) {
                if (direction >= 0 && direction < arr.Length && !visited[direction]) {
                    queue.Enqueue(direction);
                }
            }
        }
        return false;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 8, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Determines if a target value can be reached in an array
// ============================================================================
public class Solution {
    public bool CanReach(int[] arr, int start) {
        var visited = new bool[arr.Length];
        var queue = new Queue<int>();
 
        queue.Enqueue(start);
 
        while (queue.Count > 0) {
            var currentIndex = queue.Dequeue();
 
            // Check to see if we found the target value
            if (arr[currentIndex] == 0) {
                return true;
            }
            // Mark current index as visited
            visited[currentIndex] = true;
 
            // Keep searching forwards and backwards
            var forwards = currentIndex + arr[currentIndex];
            var backwards = currentIndex - arr[currentIndex];
            var directions = new List<int>{forwards, backwards};
 
            foreach (var direction in directions) {
                if (direction >= 0 && direction < arr.Length && !visited[direction]) {
                    queue.Enqueue(direction);
                }
            }
        }
        return false;
    }
}// http://programmingnotes.org/

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

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

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

true true false

C# || Maximum Product Subarray – How To Find Largest Product In Contiguous Subarray Using C#

December 02, 2021 admin No comments

The following is a module with functions which demonstrates how to find the largest product in a contiguous subarray using C#.

1. Max Product – Problem Statement

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

2. Max Product – Solution

The following is a solution which demonstrates how to find the largest product in a contiguous subarray.

This solution is inspired by Kadane’s algorithm to find the result.

The idea here is similar to the ‘Maximum Subarray‘ problem.

In this solution, we have two values:

The current cumulative maximum product up to current element The current cumulative minimum product up to current element

Each loop iteration, these values are updated by either multiplying the new element at the current index with the existing product, or starting fresh from current index.

When a negative number is encountered, the current max and current min values are swapped, because multiplying a negative number makes a big number smaller, and multiplying a negative number makes small number bigger. So their intent is redefined by swapping.





		
		
			2. Max Product - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 2, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find maximum product contiguous subarray
// ============================================================================
public class Solution {
    public int MaxProduct(int[] nums) {
        // Store the result
        var result = nums[0];

        // The current maximum and minimum product of the subarray
        var currentMin = nums[0];
        var currentMax = nums[0];

        for (int index = 1; index < nums.Length; ++index) {
            // Swap current max/min because multiplying
            // a negative number makes a big number smaller,
            // and multiplying a negative number makes small number bigger.
            // So their intent is redefined by swapping
            if (nums[index] < 0) {
                var temp = currentMax;
                currentMax = currentMin;
                currentMin = temp;
            }

            // Determine the max/min product for the current number.
            // It is either the current number itself
            // or the max/min by the previous values times the current one
            currentMax = Math.Max(nums[index], currentMax * nums[index]);
            currentMin = Math.Min(nums[index], currentMin * nums[index]);

            // Keep track of the current max result
            result = Math.Max(result, currentMax);
        }
        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 2, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find maximum product contiguous subarray
// ============================================================================
public class Solution {
    public int MaxProduct(int[] nums) {
        // Store the result
        var result = nums[0];
 
        // The current maximum and minimum product of the subarray
        var currentMin = nums[0];
        var currentMax = nums[0];
 
        for (int index = 1; index < nums.Length; ++index) {
            // Swap current max/min because multiplying
            // a negative number makes a big number smaller,
            // and multiplying a negative number makes small number bigger.
            // So their intent is redefined by swapping
            if (nums[index] < 0) {
                var temp = currentMax;
                currentMax = currentMin;
                currentMin = temp;
            }
 
            // Determine the max/min product for the current number.
            // It is either the current number itself
            // or the max/min by the previous values times the current one
            currentMax = Math.Max(nums[index], currentMax * nums[index]);
            currentMin = Math.Min(nums[index], currentMin * nums[index]);
 
            // Keep track of the current max result
            result = Math.Max(result, currentMax);
        }
        return result;
    }
}// http://programmingnotes.org/

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

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

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

6 0

C# || Maximum Subarray – How To Find Largest Sum In Contiguous Subarray Using C#

December 02, 2021 admin No comments

The following is a module with functions which demonstrates how to find the largest sum in a contiguous subarray using C#.

1. Max Sub Array – Problem Statement

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1] Output: 1

Example 3:

Input: nums = [5,4,-1,7,8] Output: 23

2. Max Sub Array – Solution

The following is a solution which demonstrates how to find the largest sum in a contiguous subarray.

This solution uses Kadane’s algorithm to find the result.





		
		
			2. Max Sub Array - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 2, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find maximum sum in contiguous subarray
// ============================================================================
public class Solution {
    public int MaxSubArray(int[] nums) {
        var result = nums[0];
        var current = result;

        for (int index = 1; index < nums.Length; ++index) {
            current = Math.Max(nums[index], nums[index] + current);
            result = Math.Max(result, current);
        }

        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 2, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find maximum sum in contiguous subarray
// ============================================================================
public class Solution {
    public int MaxSubArray(int[] nums) {
        var result = nums[0];
        var current = result;
 
        for (int index = 1; index < nums.Length; ++index) {
            current = Math.Max(nums[index], nums[index] + current);
            result = Math.Max(result, current);
        }
 
        return result;
    }
}// http://programmingnotes.org/

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

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

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

6 1 23

C# || String To Integer (atoi) – How To Convert String To Signed Integer Using C#

November 30, 2021 admin 1 Comment

The following is a module with functions which demonstrates how to convert a string to 32-bit signed integer using C#.

1. My Atoi – Problem Statement

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).

The algorithm for myAtoi(string s) is as follows:

Read in and ignore any leading whitespace.
Check if the next character (if not already at the end of the string) is ‘-‘ or ‘+’. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
Convert these digits into an integer (i.e. “123” -> 123, “0032” -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
If the integer is out of the 32-bit signed integer range [-2³¹, 2³¹ – 1], then clamp the integer so that it remains in the range. Specifically, integers less than -2³¹ should be clamped to -2³¹, and integers greater than 2³¹ – 1 should be clamped to 2³¹ – 1.
Return the integer as the final result.

Note:

Only the space character ‘ ‘ is considered a whitespace character.
Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.

Example 1:

Input: s = "42" Output: 42 Explanation: The underlined characters are what is read in, the caret is the current reader position. Step 1: "42" (no characters read because there is no leading whitespace) ^ Step 2: "42" (no characters read because there is neither a '-' nor '+') ^ Step 3: "42" ("42" is read in) ^ The parsed integer is 42. Since 42 is in the range [-2³¹, 2³¹ - 1], the final result is 42.

Example 2:

Input: s = " -42" Output: -42 Explanation: Step 1: " -42" (leading whitespace is read and ignored) ^ Step 2: " -42" ('-' is read, so the result should be negative) ^ Step 3: " -42" ("42" is read in) ^ The parsed integer is -42. Since -42 is in the range [-2³¹, 2³¹ - 1], the final result is -42.

Example 3:

Input: s = "4193 with words" Output: 4193 Explanation: Step 1: "4193 with words" (no characters read because there is no leading whitespace) ^ Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+') ^ Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit) ^ The parsed integer is 4193. Since 4193 is in the range [-2³¹, 2³¹ - 1], the final result is 4193.

Example 4:

Input: s = "words and 987" Output: 0 Explanation: Step 1: "words and 987" (no characters read because there is no leading whitespace) ^ Step 2: "words and 987" (no characters read because there is neither a '-' nor '+') ^ Step 3: "words and 987" (reading stops immediately because there is a non-digit 'w') ^ The parsed integer is 0 because no digits were read. Since 0 is in the range [-2³¹, 2³¹ - 1], the final result is 0.

Example 5:

Input: s = "-91283472332" Output: -2147483648 Explanation: Step 1: "-91283472332" (no characters read because there is no leading whitespace) ^ Step 2: "-91283472332" ('-' is read, so the result should be negative) ^ Step 3: "-91283472332" ("91283472332" is read in) ^ The parsed integer is -91283472332. Since -91283472332 is less than the lower bound of the range [-2³¹, 2³¹ - 1], the final result is clamped to -2³¹ = -2147483648.

2. My Atoi – Solution

The following is a solution which demonstrates how to convert a string to 32-bit signed integer.





		
		
			2. My Atoi - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to convert string to integer
// ============================================================================
public class Solution {
    public int MyAtoi(string s) {
        // 1. Advance leading whitespace
        var index = 0;
        while (index < s.Length && char.IsWhiteSpace(s[index])) {
            ++index;
        }

        // 2. Determine if number is positive or negative
        var sign = 1;
        if (index < s.Length && (s[index] == '-' || s[index] == '+')) {
            if (s[index] == '-') {
                sign = -1;
            }
            ++index;
        }

        // 3. Convert char digits to numeric value
        var result = 0;
        while (index < s.Length && char.IsDigit(s[index])) {
            var digit = CharToInt(s[index]);
            // Check for overflow
            if (result > (int.MaxValue - digit) / 10) {
                return sign == -1 ? int.MinValue : int.MaxValue;
            }
            result = (result * 10) + digit;
            ++index;
        }
        return result * sign;
    }

    private static int CharToInt(char ch) {
        return ch - '0';
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to convert string to integer
// ============================================================================
public class Solution {
    public int MyAtoi(string s) {
        // 1. Advance leading whitespace
        var index = 0;
        while (index < s.Length && char.IsWhiteSpace(s[index])) {
            ++index;
        }
 
        // 2. Determine if number is positive or negative
        var sign = 1;
        if (index < s.Length && (s[index] == '-' || s[index] == '+')) {
            if (s[index] == '-') {
                sign = -1;
            }
            ++index;
        }
 
        // 3. Convert char digits to numeric value
        var result = 0;
        while (index < s.Length && char.IsDigit(s[index])) {
            var digit = CharToInt(s[index]);
            // Check for overflow
            if (result > (int.MaxValue - digit) / 10) {
                return sign == -1 ? int.MinValue : int.MaxValue;
            }
            result = (result * 10) + digit;
            ++index;
        }
        return result * sign;
    }
 
    private static int CharToInt(char ch) {
        return ch - '0';
    }
}// http://programmingnotes.org/

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

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

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

42 -42 4193 0 -2147483648

C# || Maximal Rectangle – How To Find Largest Rectangle Area Using C#

November 30, 2021 admin No comments

The following is a module with functions which demonstrates how to find the largest rectangle area containing only 1’s using C#.

1. Maximal Rectangle – Problem Statement

Given a rows x cols binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing only 1‘s and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 6 Explanation: The maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = [] Output: 0

Example 3:

Input: matrix = [["0"]] Output: 0

Example 4:

Input: matrix = [["1"]] Output: 1

Example 5:

Input: matrix = [["0","0"]] Output: 0

2. Maximal Rectangle – Solution

The following is a solution which demonstrates how to find the largest rectangle area containing only 1’s.

This solution uses the monotonic stack approach.





		
		
			2. Maximal Rectangle - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the largest rectangle area
// ============================================================================
public class Solution {
    public int MaximalRectangle(char[][] matrix) {
        if (matrix.Length == 0) {
            return 0;
        }

        var result = 0;
        var histogram = new int[matrix[0].Length + 1];
        for (int row = 0; row < matrix.Length; ++row) {
            var stack = new Stack<int>();
            for (int col = 0; col <= matrix[row].Length; ++col) {
                // Set value
                if (col < matrix[row].Length) {
                    if (matrix[row][col] == '1') {
                        histogram[col] += 1;
                    } else {
                        histogram[col] = 0;
                    }
                }

                // Compute area
                while (stack.Count > 0 && histogram[stack.Peek()] >= histogram[col]) {
                    var area = histogram[stack.Pop()] * (stack.Count == 0 ? col : (col - stack.Peek() - 1));
                    result = Math.Max(result, area);
                }
                stack.Push(col);
            }
        }
        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the largest rectangle area
// ============================================================================
public class Solution {
    public int MaximalRectangle(char[][] matrix) {
        if (matrix.Length == 0) {
            return 0;
        }
 
        var result = 0;
        var histogram = new int[matrix[0].Length + 1];
        for (int row = 0; row < matrix.Length; ++row) {
            var stack = new Stack<int>();
            for (int col = 0; col <= matrix[row].Length; ++col) {
                // Set value
                if (col < matrix[row].Length) {
                    if (matrix[row][col] == '1') {
                        histogram[col] += 1;
                    } else {
                        histogram[col] = 0;
                    }
                }
 
                // Compute area
                while (stack.Count > 0 && histogram[stack.Peek()] >= histogram[col]) {
                    var area = histogram[stack.Pop()] * (stack.Count == 0 ? col : (col - stack.Peek() - 1));
                    result = Math.Max(result, area);
                }
                stack.Push(col);
            }
        }
        return result;
    }
}// http://programmingnotes.org/

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

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

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

6 0 0 1 0

C# || How To Find The Largest Component Size By Common Factor Using C#

November 28, 2021 admin No comments

The following is a module with functions which demonstrates how to find the largest component size by common factor using C#.

1. Largest Component Size – Problem Statement

You are given an integer array of unique positive integers nums. Consider the following graph:

There are nums.length nodes, labeled nums[0] to nums[nums.length – 1],
There is an undirected edge between nums[i] and nums[j] if nums[i] and nums[j] share a common factor greater than 1.

Return the size of the largest connected component in the graph.

Example 1:

Input: nums = [4,6,15,35] Output: 4

Example 2:

Input: nums = [20,50,9,63] Output: 2

Example 3:

Input: nums = [2,3,6,7,4,12,21,39] Output: 8

2. Largest Component Size – Solution

The following is a solution which demonstrates how to find the largest component size by common factor.

The following solution uses a union find set to group connections together.





		
		
			2. Largest Component Size - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find largest common factor
// ============================================================================
public class Solution {
    public int LargestComponentSize(int[] nums) {
        var set = new UnionFindSet(nums.Max() + 1);

        // Calculate primes set for all elements
        foreach (var num in nums) {
            for (var k = 2; k * k <= num; ++k) {
                if (num % k == 0) {
                    set.Union(num, k);
                    set.Union(num, num / k);
                }
            }
        }

        // Count the apperance of parents, return the maxium one.
        // All connected nodes will point to same parent
        var map = new Dictionary<int, int>();
        var result = 1;
        foreach (var num in nums) {
            var count = set.Find(num);
            map[count] = (map.ContainsKey(count) ? map[count] : 0) + 1;
            result = Math.Max(result, map[count]);
        }
        return result;
    }

    public class UnionFindSet {
        private int[] parent;

        public UnionFindSet(int size) {
            parent = new int[size];
            for (int i = 0; i < parent.Length; ++i) {
                parent[i] = i;
            }
        }
        public void Union(int x, int y) {
            parent[Find(x)] = parent[Find(y)];
        }
        public int Find(int x) {
            if (parent[x] != x) {
                parent[x] = Find(parent[x]);
            }
            return parent[x];
        }
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find largest common factor
// ============================================================================
public class Solution {
    public int LargestComponentSize(int[] nums) {
        var set = new UnionFindSet(nums.Max() + 1);
 
        // Calculate primes set for all elements
        foreach (var num in nums) {
            for (var k = 2; k * k <= num; ++k) {
                if (num % k == 0) {
                    set.Union(num, k);
                    set.Union(num, num / k);
                }
            }
        }
 
        // Count the apperance of parents, return the maxium one.
        // All connected nodes will point to same parent
        var map = new Dictionary<int, int>();
        var result = 1;
        foreach (var num in nums) {
            var count = set.Find(num);
            map[count] = (map.ContainsKey(count) ? map[count] : 0) + 1;
            result = Math.Max(result, map[count]);
        }
        return result;
    }
 
    public class UnionFindSet {
        private int[] parent;
 
        public UnionFindSet(int size) {
            parent = new int[size];
            for (int i = 0; i < parent.Length; ++i) {
                parent[i] = i;
            }
        }
        public void Union(int x, int y) {
            parent[Find(x)] = parent[Find(y)];
        }
        public int Find(int x) {
            if (parent[x] != x) {
                parent[x] = Find(parent[x]);
            }
            return parent[x];
        }
    }
}// http://programmingnotes.org/

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

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

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

4 2 8

C# || Accounts Merge – How To Merge A List Of Emails Using C#

November 28, 2021 admin No comments

The following is a module with functions which demonstrates how to merge a list of emails using C#.

1. Accounts Merge – Problem Statement

Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example 1:

Input: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]] Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]] Explanation: The first and second John's are the same person as they have the common email "johnsmith@mail.com". The third John and Mary are different people as none of their email addresses are used by other accounts. We could return these lists in any order, for example the answer [['Mary', 'mary@mail.com'], ['John', 'johnnybravo@mail.com'], ['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']] would still be accepted.

Example 2:

Input: accounts = [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]] Output: [["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]

2. Accounts Merge – Solution

The following is a solution which demonstrates how to merge a list of emails.

The following solution uses a union find set to group accounts with matching emails together.





		
		
			2. Accounts Merge - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to merge a list of emails
// ============================================================================
public class Solution {
    public IList<IList<string>> AccountsMerge(IList<IList<string>> accounts) {
        var set = new UnionFindSet(accounts.Count);

        // Map email to their component index
        var emailComponents = new Dictionary<string, int>();
        for (int i = 0; i < accounts.Count; ++i) {
            var account = accounts[i];

            for (int j = 1; j < account.Count; ++j) {
                var email = account[j];

                // Assign component group as the account index
                var group = i;
                if (!emailComponents.ContainsKey(email)) {
                    emailComponents[email] = group;
                } else {
                    // Union this group with the previous group of the email
                    set.Union(group, emailComponents[email]);
                }
            }
        }

        // Store emails corresponding to the components parent
        var emailGroups = new Dictionary<int, List<string>>();
        foreach (var email in emailComponents.Keys) {
            var group = emailComponents[email];
            var groupParent = set.Find(group);

            if (!emailGroups.ContainsKey(groupParent)) {
                emailGroups[groupParent] = new List<string>();
            }
            emailGroups[groupParent].Add(email);
        }

        // Sort the emails and add the account name
        var result = new List<IList<string>>();
        foreach (var group in emailGroups.Keys) {
            var emails = emailGroups[group];
            emails.Sort(StringComparer.Ordinal);
            emails.Insert(0, accounts[group][0]);
            result.Add(emails);
        }
        return result;
    }

    public class UnionFindSet {
        int[] parent;
        int[] size;

        public UnionFindSet(int count) {
            parent = new int[count];
            size = new int[count];
            for (int index = 0; index < count; ++index) {
                parent[index] = index;
                size[index] = 1;
            }
        }
        public int Find(int x) {
            if (parent[x] != x) {
                parent[x] = Find(parent[x]);
            }
            return parent[x];
        }
        public void Union(int x, int y) {
            var parentX = Find(x);
            var parentY = Find(y);
            if (parentX == parentY) {
                return;
            }
            if (size[parentX] >= size[parentY]) {
                size[parentX] += size[parentY];
                parent[parentY] = parentX;
            } else {
                size[parentY] += size[parentX];
                parent[parentX] = parentY;
            }
        }
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to merge a list of emails
// ============================================================================
public class Solution {
    public IList<IList<string>> AccountsMerge(IList<IList<string>> accounts) {
        var set = new UnionFindSet(accounts.Count);
 
        // Map email to their component index
        var emailComponents = new Dictionary<string, int>();
        for (int i = 0; i < accounts.Count; ++i) {
            var account = accounts[i];
 
            for (int j = 1; j < account.Count; ++j) {
                var email = account[j];
 
                // Assign component group as the account index
                var group = i;
                if (!emailComponents.ContainsKey(email)) {
                    emailComponents[email] = group;
                } else {
                    // Union this group with the previous group of the email
                    set.Union(group, emailComponents[email]);
                }
            }
        }
 
        // Store emails corresponding to the components parent
        var emailGroups = new Dictionary<int, List<string>>();
        foreach (var email in emailComponents.Keys) {
            var group = emailComponents[email];
            var groupParent = set.Find(group);
 
            if (!emailGroups.ContainsKey(groupParent)) {
                emailGroups[groupParent] = new List<string>();
            }
            emailGroups[groupParent].Add(email);
        }
 
        // Sort the emails and add the account name
        var result = new List<IList<string>>();
        foreach (var group in emailGroups.Keys) {
            var emails = emailGroups[group];
            emails.Sort(StringComparer.Ordinal);
            emails.Insert(0, accounts[group][0]);
            result.Add(emails);
        }
        return result;
    }
 
    public class UnionFindSet {
        int[] parent;
        int[] size;
 
        public UnionFindSet(int count) {
            parent = new int[count];
            size = new int[count];
            for (int index = 0; index < count; ++index) {
                parent[index] = index;
                size[index] = 1;
            }
        }
        public int Find(int x) {
            if (parent[x] != x) {
                parent[x] = Find(parent[x]);
            }
            return parent[x];
        }
        public void Union(int x, int y) {
            var parentX = Find(x);
            var parentY = Find(y);
            if (parentX == parentY) {
                return;
            }
            if (size[parentX] >= size[parentY]) {
                size[parentX] += size[parentY];
                parent[parentY] = parentX;
            } else {
                size[parentY] += size[parentX];
                parent[parentX] = parentY;
            }
        }
    }
}// http://programmingnotes.org/

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

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

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

[["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]] [["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]

C# || How To Find All Paths From Source To Target In Graph Using C#

November 28, 2021 admin No comments

The following is a module with functions which demonstrates how to find all paths from source to target in a graph using C#.

1. All Paths Source Target – Problem Statement

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n – 1, find all possible paths from node 0 to node n – 1 and return them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

Example 1:

Input: graph = [[1,2],[3],[3],[]] Output: [[0,1,3],[0,2,3]] Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Example 2:

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

Example 3:

Input: graph = [[1],[]] Output: [[0,1]]

Example 4:

Input: graph = [[1,2,3],[2],[3],[]] Output: [[0,1,2,3],[0,2,3],[0,3]]

Example 5:

Input: graph = [[1,3],[2],[3],[]] Output: [[0,1,2,3],[0,3]]

2. All Paths Source Target – Solution

The following is a solution which demonstrates how to find all paths from source to target in a graph.

This solution uses Breadth First Search and backtracking when looking for paths.





		
		
			2. All Paths Source Target - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find all paths in a graph
// ============================================================================
public class Solution {
    public IList<IList<int>> AllPathsSourceTarget(int[][] graph) {
        var result = new List<IList<int>>();
        var queue = new Queue<List<int>>();

        queue.Enqueue(new List<int>{0});

        while (queue.Count > 0) {
            var currentPath = queue.Dequeue();
            var currentNode = currentPath[currentPath.Count - 1];

            if (currentNode == graph.Length - 1) {
                result.Add(currentPath);
            } else {
                foreach (var child in graph[currentNode]) {
                    currentPath.Add(child);
                    queue.Enqueue(new List<int>(currentPath));
                    currentPath.RemoveAt(currentPath.Count - 1);
                }
            }
        }
        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find all paths in a graph
// ============================================================================
public class Solution {
    public IList<IList<int>> AllPathsSourceTarget(int[][] graph) {
        var result = new List<IList<int>>();
        var queue = new Queue<List<int>>();
 
        queue.Enqueue(new List<int>{0});
 
        while (queue.Count > 0) {
            var currentPath = queue.Dequeue();
            var currentNode = currentPath[currentPath.Count - 1];
 
            if (currentNode == graph.Length - 1) {
                result.Add(currentPath);
            } else {
                foreach (var child in graph[currentNode]) {
                    currentPath.Add(child);
                    queue.Enqueue(new List<int>(currentPath));
                    currentPath.RemoveAt(currentPath.Count - 1);
                }
            }
        }
        return result;
    }
}// http://programmingnotes.org/

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

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

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

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

Translate Page

Compile Your Code Now
- Compile Your Code Online

Calendar
April 2026

S M T W T F S

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

« Apr

April 2026
S	M	T	W	T	F	S
	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

Popular Pages
Sorry. No data so far.

Hi, I'm a software engineer. I write articles about programming and design in my spare time.

If I have been of help to you, please visit one of our advertisers, or consider buying me a coffee.

Your encouragement keeps the passion alive.

Thank you for your support!

Author Archives: admin

C# || How To Get Total Sum Root To Leaf Binary Numbers In Binary Tree Using C#

Angular || How To Create A Simple Weather Forecast App Using Angular

JavaScript || How To Use Geolocation To Get Current Position With Promises Using Vanilla JavaScript

Angular || How To Resolve Issue: “Module Parse Failed: Unexpected Character – You May Need An Appropriate Loader” Using Angular

Angular || How To Resolve Issue: “Cannot find name ‘require'” Using Angular

Angular || How To Create A Simple Personal Contact List Using Angular

C# || Jump Game III – How To Check If You Can Reach Target Value In Array Using C#

C# || Maximum Product Subarray – How To Find Largest Product In Contiguous Subarray Using C#

C# || Maximum Subarray – How To Find Largest Sum In Contiguous Subarray Using C#

C# || String To Integer (atoi) – How To Convert String To Signed Integer Using C#

C# || Maximal Rectangle – How To Find Largest Rectangle Area Using C#

C# || How To Find The Largest Component Size By Common Factor Using C#

C# || Accounts Merge – How To Merge A List Of Emails Using C#

C# || How To Find All Paths From Source To Target In Graph Using C#

Search

Translate Page

Compile Your Code Now

Calendar

Recent

Archives

Categories

Author Archives: admin

Search

Translate Page

Compile Your Code Now

Calendar

Popular Pages

Recent

Archives

Categories