leetcode – Page 3 – My Programming Notes

Tag Archives: leetcode

C# || How To Determine If String Halves Are Alike Using C#

January 02, 2023 admin No comments

The following is a module with functions which demonstrates how to determine if string halves are alike using C#.

1. Halves Are A like – Problem Statement

You are given a string s of even length. Split this string into two halves of equal lengths, and let a be the first half and b be the second half.

Two strings are alike if they have the same number of vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’, ‘A’, ‘E’, ‘I’, ‘O’, ‘U’). Notice that s contains uppercase and lowercase letters.

Return true if a and b are alike. Otherwise, return false.

Example 1:

Input: s = "book" Output: true Explanation: a = "bo" and b = "ok". a has 1 vowel and b has 1 vowel. Therefore, they are alike.

Example 2:

Input: s = "textbook" Output: false Explanation: a = "text" and b = "book". a has 1 vowel whereas b has 2. Therefore, they are not alike. Notice that the vowel o is counted twice.

2. Halves Are A like – Solution

The following is a solution which demonstrates how to determine if string halves are alike.





		
		
			2. Halves Are A like - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 2, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to determine if string halves are alike
// ============================================================================
public class Solution {
    public bool HalvesAreAlike(string s) {
        // Get first half count
        int firstHalfVowel = 0;
        for (int index = 0; index < s.Length / 2; ++index) {
            if (IsVowel(s[index])) {
                ++firstHalfVowel;
            }
        }

        // Get second half count
        int secondHalfVowel = 0;
        for (int index = s.Length / 2 ; index < s.Length && secondHalfVowel <= firstHalfVowel; ++index) {
            if (IsVowel(s[index])) {
                ++secondHalfVowel;
            }
        }
        return firstHalfVowel == secondHalfVowel;
    }

    private static bool IsVowel(char ch) {
        ch = char.ToLower(ch);
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
    }
}// 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 2, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to determine if string halves are alike
// ============================================================================
public class Solution {
    public bool HalvesAreAlike(string s) {
        // Get first half count
        int firstHalfVowel = 0;
        for (int index = 0; index < s.Length / 2; ++index) {
            if (IsVowel(s[index])) {
                ++firstHalfVowel;
            }
        }
 
        // Get second half count
        int secondHalfVowel = 0;
        for (int index = s.Length / 2 ; index < s.Length && secondHalfVowel <= firstHalfVowel; ++index) {
            if (IsVowel(s[index])) {
                ++secondHalfVowel;
            }
        }
        return firstHalfVowel == secondHalfVowel;
    }
 
    private static bool IsVowel(char ch) {
        ch = char.ToLower(ch);
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
    }
}// http://programmingnotes.org/

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

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

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

true false

C# || How To Find The Maximum Profit In Job Scheduling Using C#

January 01, 2023 admin No comments

The following is a module with functions which demonstrates how to find the maximum profit in job scheduling using C#.

1. Job Scheduling – Problem Statement

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70] Output: 120 Explanation: The subset chosen is the first and fourth job. Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60] Output: 150 Explanation: The subset chosen is the first, fourth and fifth job. Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4] Output: 6

2. Job Scheduling – Solution

The following is a solution which demonstrates how to find the maximum profit in job scheduling.





		
		
			2. Job Scheduling - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find maximum profit in job scheduling
// ============================================================================
public class Solution {
    public int JobScheduling(int[] startTime, int[] endTime, int[] profit) {
        if (startTime == null || startTime.Length == 0) {
            return 0;
        }

        var jobs = new List<Job>();
        for (int index = 0; index < startTime.Length; ++index) {
            jobs.Add(new Job(startTime[index], endTime[index], profit[index]));
        }

        jobs.Sort((a, b) => a.Start - b.Start);

        return DFS(jobs, 0, new Dictionary<int, int>());
    }

    private int DFS(List<Job> jobs, int currentJobIndex, Dictionary<int, int> maxProfits) {
        if (currentJobIndex >= jobs.Count) {
            return 0;
        }

        if (maxProfits.ContainsKey(currentJobIndex)) {
            return maxProfits[currentJobIndex];
        }

        int next = BinarySearch(jobs, currentJobIndex);
        int inc = jobs[currentJobIndex].Profit + (next == -1 ? 0 : DFS(jobs, next, maxProfits));
        int exc = DFS(jobs, currentJobIndex + 1, maxProfits);

        int maxProfit = Math.Max(inc, exc);
        maxProfits[currentJobIndex] =  maxProfit;
        return maxProfit;
    }

    private int BinarySearch(List<Job> jobs, int currentJobIndex) {
        int lo = currentJobIndex;
        int high = jobs.Count - 1;
        int result = -1;

        while (lo <= high) {
            int mid = lo + (high - lo) / 2;

            if (jobs[currentJobIndex].End <= jobs[mid].Start) {
                result = mid;
                high = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return result;
    }

    class Job {
        public int Start { get; set; }
        public int End { get; set; }
        public int Profit { get; set; }

        public Job(int startTime, int endTime, int profit) {
            Start = startTime;
            End = endTime;
            Profit = profit;
        }
    }
}// 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find maximum profit in job scheduling
// ============================================================================
public class Solution {
    public int JobScheduling(int[] startTime, int[] endTime, int[] profit) {
        if (startTime == null || startTime.Length == 0) {
            return 0;
        }
 
        var jobs = new List<Job>();
        for (int index = 0; index < startTime.Length; ++index) {
            jobs.Add(new Job(startTime[index], endTime[index], profit[index]));
        }
 
        jobs.Sort((a, b) => a.Start - b.Start);
 
        return DFS(jobs, 0, new Dictionary<int, int>());
    }
 
    private int DFS(List<Job> jobs, int currentJobIndex, Dictionary<int, int> maxProfits) {
        if (currentJobIndex >= jobs.Count) {
            return 0;
        }
 
        if (maxProfits.ContainsKey(currentJobIndex)) {
            return maxProfits[currentJobIndex];
        }
 
        int next = BinarySearch(jobs, currentJobIndex);
        int inc = jobs[currentJobIndex].Profit + (next == -1 ? 0 : DFS(jobs, next, maxProfits));
        int exc = DFS(jobs, currentJobIndex + 1, maxProfits);
 
        int maxProfit = Math.Max(inc, exc);
        maxProfits[currentJobIndex] =  maxProfit;
        return maxProfit;
    }
 
    private int BinarySearch(List<Job> jobs, int currentJobIndex) {
        int lo = currentJobIndex;
        int high = jobs.Count - 1;
        int result = -1;
 
        while (lo <= high) {
            int mid = lo + (high - lo) / 2;
 
            if (jobs[currentJobIndex].End <= jobs[mid].Start) {
                result = mid;
                high = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return result;
    }
 
    class Job {
        public int Start { get; set; }
        public int End { get; set; }
        public int Profit { get; set; }
 
        public Job(int startTime, int endTime, int profit) {
            Start = startTime;
            End = endTime;
            Profit = profit;
        }
    }
}// 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:

120 150 6

C# || Contains Duplicate II – How To Determine Two Distinct Indices In Array Equal To Target Value Using C#

December 25, 2022 admin No comments

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

1. Contains Nearby Duplicate – Problem Statement

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i – j) <= k.

Example 1:

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

Example 2:

Input: nums = [1,0,1,1], k = 1 Output: true

Example 3:

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

2. Contains Nearby Duplicate – Solution

The following are two solutions which demonstrates how to determine two distinct indices in array equal to target value.





		
		
			2. Contains Nearby Duplicate - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 25, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to determine two indices equal to target value
// ============================================================================
public class Solution {
    public bool ContainsNearbyDuplicate(int[] nums, int k) {
        var set = new HashSet<int>();
        for (int index = 0; index < nums.Length; ++index){
            if (index > k) {
                set.Remove(nums[index - k - 1]);
            }
            if (!set.Add(nums[index])) {
                return true;
            }
        }
        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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 25, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to determine two indices equal to target value
// ============================================================================
public class Solution {
    public bool ContainsNearbyDuplicate(int[] nums, int k) {
        var set = new HashSet<int>();
        for (int index = 0; index < nums.Length; ++index){
            if (index > k) {
                set.Remove(nums[index - k - 1]);
            }
            if (!set.Add(nums[index])) {
                return true;
            }
        }
        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# || How To Find The Nearest Exit From Entrance In Maze Using C#

December 01, 2022 admin No comments

The following is a module with functions which demonstrates how to find the nearest exit from the entrance in a maze using C#.

1. Nearest Exit – Problem Statement

You are given an m x n matrix maze (0-indexed) with empty cells (represented as ‘.’) and walls (represented as ‘+’). You are also given the entrance of the maze, where entrance = [entrance_row, entrance_col] denotes the row and column of the cell you are initially standing at.

In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.

Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.

Example 1:

Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2] Output: 1 Explanation: There are 3 exits in this maze at [1,0], [0,2], and [2,3]. Initially, you are at the entrance cell [1,2]. - You can reach [1,0] by moving 2 steps left. - You can reach [0,2] by moving 1 step up. It is impossible to reach [2,3] from the entrance. Thus, the nearest exit is [0,2], which is 1 step away.

Example 2:

Input: maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0] Output: 2 Explanation: There is 1 exit in this maze at [1,2]. [1,0] does not count as an exit since it is the entrance cell. Initially, you are at the entrance cell [1,0]. - You can reach [1,2] by moving 2 steps right. Thus, the nearest exit is [1,2], which is 2 steps away.

Example 3:

Input: maze = [[".","+"]], entrance = [0,0] Output: -1 Explanation: There are no exits in this maze.

2. Nearest Exit – Solution

The following is a solution which demonstrates how find the nearest exit from the entrance in a maze.





		
		
			2. Nearest Exit - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 1, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find nearest exit from entrance in maze
// ============================================================================
public class Solution {
    public int NearestExit(char[][] maze, int[] entrance) {
        int rows = maze.Length;
        int cols = maze[0].Length;
        var directions = new List<KeyValuePair<int, int>>() {
            // Direction coordinates: (y, x)
            new KeyValuePair<int, int>(1, 0),
            new KeyValuePair<int, int>(-1, 0),
            new KeyValuePair<int, int>(0, 1),
            new KeyValuePair<int, int>(0, -1)
        };
        char VISITED = '+';
        char NOT_VISITED = '.';

        // Mark the entrance as visited since its not a exit.
        int startRow = entrance[0];
        int startCol = entrance[1];
        maze[startRow][startCol] = VISITED;

        // Start BFS from the entrance, and use a queue `queue` to store all
        // the cells to be visited.
        var queue = new Queue<int[]>();
        queue.Enqueue(new int[]{startRow, startCol, 0});

        while (queue.Count > 0) {
            int[] currState = queue.Dequeue();
            int currRow = currState[0];
            int currCol = currState[1];
            int currDistance = currState[2];

            // For the current cell, check its four neighbor cells.
            foreach (var dir in directions) {
                int nextRow = currRow + dir.Key;
                int nextCol = currCol + dir.Value;

                // If there exists an unvisited empty neighbor:
                if (IsValidCell(maze, nextRow, nextCol) && maze[nextRow][nextCol] == NOT_VISITED) {
                    // If this empty cell is an exit, return distance + 1.
                    if (nextRow == 0 || nextRow == rows - 1 || nextCol == 0 || nextCol == cols - 1) {
                        return currDistance + 1;
                    }

                    // Otherwise, add this cell to 'queue' and mark it as visited.
                    maze[nextRow][nextCol] = VISITED;
                    queue.Enqueue(new int[]{nextRow, nextCol, currDistance + 1});
                }
            }
        }

        // If we finish iterating without finding an exit, return -1.
        return -1;
    }

    private bool IsValidCell(char[][] grid, int row, int col) {
        return row >= 0 && row < grid.Length && col >= 0 && col < grid[row].Length;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Dec 1, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find nearest exit from entrance in maze
// ============================================================================
public class Solution {
    public int NearestExit(char[][] maze, int[] entrance) {
        int rows = maze.Length;
        int cols = maze[0].Length;
        var directions = new List<KeyValuePair<int, int>>() {
            // Direction coordinates: (y, x)
            new KeyValuePair<int, int>(1, 0),
            new KeyValuePair<int, int>(-1, 0),
            new KeyValuePair<int, int>(0, 1),
            new KeyValuePair<int, int>(0, -1)
        };
        char VISITED = '+';
        char NOT_VISITED = '.';
 
        // Mark the entrance as visited since its not a exit.
        int startRow = entrance[0];
        int startCol = entrance[1];
        maze[startRow][startCol] = VISITED;
 
        // Start BFS from the entrance, and use a queue `queue` to store all
        // the cells to be visited.
        var queue = new Queue<int[]>();
        queue.Enqueue(new int[]{startRow, startCol, 0});
 
        while (queue.Count > 0) {
            int[] currState = queue.Dequeue();
            int currRow = currState[0];
            int currCol = currState[1];
            int currDistance = currState[2];
 
            // For the current cell, check its four neighbor cells.
            foreach (var dir in directions) {
                int nextRow = currRow + dir.Key;
                int nextCol = currCol + dir.Value;
 
                // If there exists an unvisited empty neighbor:
                if (IsValidCell(maze, nextRow, nextCol) && maze[nextRow][nextCol] == NOT_VISITED) {
                    // If this empty cell is an exit, return distance + 1.
                    if (nextRow == 0 || nextRow == rows - 1 || nextCol == 0 || nextCol == cols - 1) {
                        return currDistance + 1;
                    }
 
                    // Otherwise, add this cell to 'queue' and mark it as visited.
                    maze[nextRow][nextCol] = VISITED;
                    queue.Enqueue(new int[]{nextRow, nextCol, currDistance + 1});
                }
            }
        }
 
        // If we finish iterating without finding an exit, return -1.
        return -1;
    }
 
    private bool IsValidCell(char[][] 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:

1 2 -1

C# || How To Design A Time Based Key-Value Store To Retrieve Timestamps Using C#

November 01, 2022 admin No comments

The following is a module with functions which demonstrates how to design a time based key-value store to retrieve timestamps using C#.

1. Time Map – Problem Statement

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key’s value at a certain timestamp.

Implement the TimeMap class:

TimeMap() Initializes the object of the data structure.
void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns “”.

Example 1:

Input ["TimeMap", "set", "get", "get", "set", "get", "get"] [[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]] Output [null, null, "bar", "bar", null, "bar2", "bar2"]
Explanation TimeMap timeMap = new TimeMap(); timeMap.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1. timeMap.get("foo", 1); // return "bar" timeMap.get("foo", 3); // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar". timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4. timeMap.get("foo", 4); // return "bar2" timeMap.get("foo", 5); // return "bar2"

2. Time Map – Solution

The following is a solution which demonstrates how to design a time based key-value store to retrieve timestamps.





		
		
			2. Time Map - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 1, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to design a time map
// ============================================================================
/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.Set(key,value,timestamp);
 * string param_2 = obj.Get(key,timestamp);
 */
public class TimeMap {
    private class Data {
        public string value;
        public int timestamp;
        public Data(string value, int timestamp) {
            this.value = value;
            this.timestamp = timestamp;
        }
    }

    private Dictionary<string, List<Data>> map;

    public TimeMap() {
        map = new Dictionary<string, List<Data>>();
    }

    public void Set(string key, string value, int timestamp) {
        if (!map.ContainsKey(key)) {
            map.Add(key, new List<Data>());
        }
        map[key].Add(new Data(value, timestamp));
    }

    public string Get(string key, int timestamp) {
        if (!map.ContainsKey(key)) {
             return "";
        }
        return BinarySearch(map[key], timestamp);
    }
    
    string BinarySearch(List<Data> bucket, int target) {
        int low = 0, high = bucket.Count;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (bucket[mid].timestamp <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (high == 0) {
            return "";
        }
        return (bucket[high - 1].timestamp <= target) ? bucket[high - 1].value : "";
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 1, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to design a time map
// ============================================================================
/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.Set(key,value,timestamp);
 * string param_2 = obj.Get(key,timestamp);
 */
public class TimeMap {
    private class Data {
        public string value;
        public int timestamp;
        public Data(string value, int timestamp) {
            this.value = value;
            this.timestamp = timestamp;
        }
    }
 
    private Dictionary<string, List<Data>> map;
 
    public TimeMap() {
        map = new Dictionary<string, List<Data>>();
    }
 
    public void Set(string key, string value, int timestamp) {
        if (!map.ContainsKey(key)) {
            map.Add(key, new List<Data>());
        }
        map[key].Add(new Data(value, timestamp));
    }
 
    public string Get(string key, int timestamp) {
        if (!map.ContainsKey(key)) {
             return "";
        }
        return BinarySearch(map[key], timestamp);
    }
    
    string BinarySearch(List<Data> bucket, int target) {
        int low = 0, high = bucket.Count;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (bucket[mid].timestamp <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (high == 0) {
            return "";
        }
        return (bucket[high - 1].timestamp <= target) ? bucket[high - 1].value : "";
    }
}// http://programmingnotes.org/

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

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

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

[null,null,"bar","bar",null,"bar2","bar2"]

C# || How To Return The Top K Frequent Words In Array Of Strings Using C#

October 23, 2022 admin No comments

The following is a module with functions which demonstrates how to get the top K frequent words in an array of strings using C#.

1. Top K Frequent – Problem Statement

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Example 1:

Input: words = ["i","love","leetcode","i","love","coding"], k = 2 Output: ["i","love"] Explanation: "i" and "love" are the two most frequent words. Note that "i" comes before "love" due to a lower alphabetical order.

Example 2:

Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4 Output: ["the","is","sunny","day"] Explanation: "the", "is", "sunny" and "day" are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.

2. Top K Frequent – Solution

The following are two solutions which demonstrates how to get the top K frequent words in an array of strings.





		
		
			2. Top K Frequent - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 23, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Determines how to get the top K frequent words in array
// ============================================================================
public class Solution {
    public IList<string> TopKFrequent(string[] words, int k) {
        // Use a map to get the frequency of each word
        var frequency = new Dictionary<string, int>();
        foreach (var word in words) {
            frequency[word] = frequency.GetValueOrDefault(word, 0) + 1;
        }

        // Get the frequency map as a list and sort
        var frequencyList = frequency.ToList();
        frequencyList.Sort((a, b) => {
            // If words have the same frequency, sort
            // by their lexicographical order
            if (a.Value == b.Value) {
                return string.Compare(a.Key, b.Key);
            }
            // Sort by the frequency from highest to lowest
            return b.Value - a.Value;
        });

        // Get the results
        var result = new List<string>();
        for (int index = 0; index < frequencyList.Count; ++index) {
            result.Add(frequencyList[index].Key);
            if (result.Count == k) {
                break;
            }
        }
        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 23, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Determines how to get the top K frequent words in array
// ============================================================================
public class Solution {
    public IList<string> TopKFrequent(string[] words, int k) {
        // Use a map to get the frequency of each word
        var frequency = new Dictionary<string, int>();
        foreach (var word in words) {
            frequency[word] = frequency.GetValueOrDefault(word, 0) + 1;
        }
 
        // Get the frequency map as a list and sort
        var frequencyList = frequency.ToList();
        frequencyList.Sort((a, b) => {
            // If words have the same frequency, sort
            // by their lexicographical order
            if (a.Value == b.Value) {
                return string.Compare(a.Key, b.Key);
            }
            // Sort by the frequency from highest to lowest
            return b.Value - a.Value;
        });
 
        // Get the results
        var result = new List<string>();
        for (int index = 0; index < frequencyList.Count; ++index) {
            result.Add(frequencyList[index].Key);
            if (result.Count == k) {
                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:

["i","love"] ["the","is","sunny","day"]

C# || Two Sum IV – How To Get Two Numbers In Binary Search Tree Equal To Target Value Using C#

October 09, 2022 admin No comments

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

1. Find Target – Problem Statement

Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9 Output: true

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28 Output: false

2. Find Target – Solution

The following are two solutions which demonstrates how to get two numbers in a binary search tree equal to target value.

Both solutions use a set to keep track of the items already seen.

Each time a new node is encountered, we subtract the target value from the current node value. If the difference amount from subtracting the two numbers exists in the set, a 2 sum combination exists in the tree

1. Recursive

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





		
		
			2. Find Target - Solution - Recursive
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 9, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public bool FindTarget(TreeNode root, int k) {
        return Traverse(root, k, new HashSet<int>());
    }

    private bool Traverse(TreeNode node, int k, HashSet<int> seen) {
        if (node == null) {
            return false;
        }
        // Get remaining value
        var remaining = k - node.val;

        // Check if remaining value has been seen
        if (seen.Contains(remaining)) {
            return true;
        }
        // Add current node value to items seen
        seen.Add(node.val);

        // Keep traversing left and right looking for 2 sum
        return Traverse(node.left, k, seen) || Traverse(node.right, k, seen);
    }
}// 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 9, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public bool FindTarget(TreeNode root, int k) {
        return Traverse(root, k, new HashSet<int>());
    }
 
    private bool Traverse(TreeNode node, int k, HashSet<int> seen) {
        if (node == null) {
            return false;
        }
        // Get remaining value
        var remaining = k - node.val;
 
        // Check if remaining value has been seen
        if (seen.Contains(remaining)) {
            return true;
        }
        // Add current node value to items seen
        seen.Add(node.val);
 
        // Keep traversing left and right looking for 2 sum
        return Traverse(node.left, k, seen) || Traverse(node.right, k, seen);
    }
}// http://programmingnotes.org/

2. Iterative

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





		
		
			2. Find Target - Solution - Iterative
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 9, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public bool FindTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        // Declare stack
        var stack = new Stack<TreeNode>();

        // Keep track of values seen
        var seen = new HashSet<int>();

        // Add root to stack
        stack.Push(root);

        // Loop through items on the stack
        while (stack.Count > 0) {
            // Get current node
            var node = stack.Pop();

            // Get remaining value
            var remaining = k - node.val;

            // Check if remaining value has been seen
            if (seen.Contains(remaining)) {
                return true;
            } else {
                // Keep traversing left and right looking for 2 sum
                if (node.left != null) {
                    stack.Push(node.left);
                }
                if (node.right != null) {
                    stack.Push(node.right);
                }
            }
            // Add current node value to items seen
            seen.Add(node.val);
        }
        return false;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 9, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public bool FindTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        // Declare stack
        var stack = new Stack<TreeNode>();
 
        // Keep track of values seen
        var seen = new HashSet<int>();
 
        // Add root to stack
        stack.Push(root);
 
        // Loop through items on the stack
        while (stack.Count > 0) {
            // Get current node
            var node = stack.Pop();
 
            // Get remaining value
            var remaining = k - node.val;
 
            // Check if remaining value has been seen
            if (seen.Contains(remaining)) {
                return true;
            } else {
                // Keep traversing left and right looking for 2 sum
                if (node.left != null) {
                    stack.Push(node.left);
                }
                if (node.right != null) {
                    stack.Push(node.right);
                }
            }
            // Add current node value to items seen
            seen.Add(node.val);
        }
        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 false

C# || Counting Bits – How To Return The Number Of 1’s In Binary Representation Of X Using C#

October 02, 2022 admin No comments

The following is a module with functions which demonstrates how to return the number of 1’s in binary representation of X using C#.

1. Count Bits – Problem Statement

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1‘s in the binary representation of i.

Example 1:

Input: n = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10

Example 2:

Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101

2. Count Bits – Solution

The following is a solution which demonstrates how return the number of 1’s in binary representation of X.

In this problem, we can see a pattern start to form.

When the current n is even, we can get the answer by dividing by 2 (e.g result[n] = result[n / 2])

When the current n is odd, we can get the answer by getting the result at previous index and adding 1 (e.g result[n] = result[n – 1] + 1)





		
		
			2. Level Order - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 2, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to return binary representation of X
// ============================================================================
public class Solution {
    public int[] CountBits(int n) {
        var result = new int[n + 1];
        result[0] = 0;

        for (int index = 1; index < result.Length; ++index) {
            if (index % 2 == 0) {
                result[index] = result[index / 2];
            } else {
                result[index] = result[index - 1] + 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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 2, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to return binary representation of X
// ============================================================================
public class Solution {
    public int[] CountBits(int n) {
        var result = new int[n + 1];
        result[0] = 0;
 
        for (int index = 1; index < result.Length; ++index) {
            if (index % 2 == 0) {
                result[index] = result[index / 2];
            } else {
                result[index] = result[index - 1] + 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,1] [0,1,1,2,1,2]

C# || How To Traverse N-ary Tree Level Order Using C#

September 05, 2022 admin No comments

The following is a module with functions which demonstrates how to traverse a N-ary Tree level order using C#.

1. Level Order – Problem Statement

Given an n-ary tree, return the level order traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Example 1:

Input: root = [1,null,3,2,4,null,5,6] Output: [[1],[3,2,4],[5,6]]

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

2. Level Order – Solution

The following is a solution which demonstrates how to traverse a N-ary Tree level order.

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





		
		
			2. Level Order - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Sep 5, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to traverse a N-ary Tree Level Order
// ============================================================================
/*
// Definition for a Node.
public class Node {
    public int val;
    public IList<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, IList<Node> _children) {
        val = _val;
        children = _children;
    }
}
*/
public class Solution {
    public IList<IList<int>> LevelOrder(Node root) {
        var result = new List<IList<int>>();
        if (root == null) {
           return result;
        }

        var queue = new Queue<Node>();
        queue.Enqueue(root);

        while (queue.Count > 0) {
            var currentLevel = new List<int>();
            for (int count = queue.Count - 1; count >= 0 ; --count) {
                var currentNode = queue.Dequeue();
                currentLevel.Add(currentNode.val);
                foreach (var child in currentNode.children) {
                    queue.Enqueue(child);
                }
            }
            result.Add(currentLevel);
        }

        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Sep 5, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to traverse a N-ary Tree Level Order
// ============================================================================
/*
// Definition for a Node.
public class Node {
    public int val;
    public IList<Node> children;
 
    public Node() {}
 
    public Node(int _val) {
        val = _val;
    }
 
    public Node(int _val, IList<Node> _children) {
        val = _val;
        children = _children;
    }
}
*/
public class Solution {
    public IList<IList<int>> LevelOrder(Node root) {
        var result = new List<IList<int>>();
        if (root == null) {
           return result;
        }
 
        var queue = new Queue<Node>();
        queue.Enqueue(root);
 
        while (queue.Count > 0) {
            var currentLevel = new List<int>();
            for (int count = queue.Count - 1; count >= 0 ; --count) {
                var currentNode = queue.Dequeue();
                currentLevel.Add(currentNode.val);
                foreach (var child in currentNode.children) {
                    queue.Enqueue(child);
                }
            }
            result.Add(currentLevel);
        }
 
        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],[3,2,4],[5,6]] [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

C# || How To Validate A Binary Search Tree Using C#

August 12, 2022 admin No comments

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

1. Is Valid BST – Problem Statement

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

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

Example 1:

Input: root = [2,1,3] Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.

2. Is Valid BST – Solution

The following is a solution which demonstrates how to validate a binary search tree.





		
		
			2. Is Valid BST - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Aug 12, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to validate a BST
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool IsValidBST(TreeNode root) {
        return Traverse(root, null, null);
    }

    private bool Traverse(TreeNode node, TreeNode min, TreeNode max) {
        if (node == null) {
            return true;
        }
        if (max != null && node.val >= max.val) {
            return false;
        }
        if (min != null && node.val <= min.val) {
            return false;
        }
        return Traverse(node.left, min, node)
            && Traverse(node.right, node, max);
    }
}// 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:   Aug 12, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to validate a BST
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool IsValidBST(TreeNode root) {
        return Traverse(root, null, null);
    }
 
    private bool Traverse(TreeNode node, TreeNode min, TreeNode max) {
        if (node == null) {
            return true;
        }
        if (max != null && node.val >= max.val) {
            return false;
        }
        if (min != null && node.val <= min.val) {
            return false;
        }
        return Traverse(node.left, min, node)
            && Traverse(node.right, node, max);
    }
}// http://programmingnotes.org/

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

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

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

true false

C# || Max Area of Island – How To Find The Maximum Area Of An Island In A Grid Using C#

July 28, 2022 admin No comments

The following is a module with functions which demonstrates how to find the maximum area of an island in a grid using C#.

1. Max Area Of Island – Problem Statement

You are given an m x n binary matrix grid. An island is a group of 1‘s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]] Output: 6 Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

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

2. Max Area Of Island – Solution

The following is a solution which demonstrates how to find the maximum area of an island in a grid.

We want to know the area of each connected shape in the grid, then take the maximum of these.

If we are on a land square and explore every square connected to it 4-directionally (and recursively squares connected to those squares, and so on), then the total number of squares explored will be the area of that connected shape.

To ensure we don’t count squares in a shape more than once, we use ‘seen’ to keep track of squares we haven’t visited before. It will also prevent us from counting the same shape more than once.





		
		
			2. Max Area Of Island - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jul 28, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the maximum area in a grid
// ============================================================================
public class Solution {
    public int MaxAreaOfIsland(int[][] grid) {
        var seen = new bool[grid.Length][];
        for (int row = 0; row < seen.Length; ++row) {
            seen[row] = new bool[grid[row].Length];
        }
        var result = 0;
        for (int row = 0; row < grid.Length; ++row) {
            for (int col = 0; col < grid[row].Length; ++col) {
                result = Math.Max(result, Area(grid, row, col, seen));
            }
        }
        return result;
    }

    private int Area(int[][] grid, int row, int col, bool[][] seen) {
        if (!IsValidCell(grid, row, col)) {
            return 0;
        }
        if (seen[row][col] || grid[row][col] == 0) {
            return 0;
        }
        seen[row][col] = true;
        return 1 +
            // Search Bottom
            Area(grid, row + 1, col, seen) +
            // Search Top
            Area(grid, row - 1, col, seen) +
            // Search Left
            Area(grid, row, col - 1, seen) +
            // Search Right
            Area(grid, row, col + 1, seen);
    }

    private bool IsValidCell(int[][] grid, int row, int col) {
        return row >= 0 && row < grid.Length && col >= 0 && col < grid[row].Length;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jul 28, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the maximum area in a grid
// ============================================================================
public class Solution {
    public int MaxAreaOfIsland(int[][] grid) {
        var seen = new bool[grid.Length][];
        for (int row = 0; row < seen.Length; ++row) {
            seen[row] = new bool[grid[row].Length];
        }
        var result = 0;
        for (int row = 0; row < grid.Length; ++row) {
            for (int col = 0; col < grid[row].Length; ++col) {
                result = Math.Max(result, Area(grid, row, col, seen));
            }
        }
        return result;
    }
 
    private int Area(int[][] grid, int row, int col, bool[][] seen) {
        if (!IsValidCell(grid, row, col)) {
            return 0;
        }
        if (seen[row][col] || grid[row][col] == 0) {
            return 0;
        }
        seen[row][col] = true;
        return 1 +
            // Search Bottom
            Area(grid, row + 1, col, seen) +
            // Search Top
            Area(grid, row - 1, col, seen) +
            // Search Left
            Area(grid, row, col - 1, seen) +
            // Search Right
            Area(grid, row, col + 1, seen);
    }
 
    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:

6 0

C# || Binary Tree Right Side View – How To Get Nodes Ordered Top To Bottom C#

July 10, 2022 admin No comments

The following is a module with functions which demonstrates how to get nodes in a binary tree ordered from top to bottom using C#.

1. Right Side View – Problem Statement

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

Input: root = [1,2,3,null,5,null,4] Output: [1,3,4]

Example 2:

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

Example 3:

Input: root = [] Output: []

2. Right Side View – Solution

The following is a solution which demonstrates how to get right side nodes ordered from top to bottom.

This solution uses Depth First Search level order traversal to explore items at each level, and then adds the last node on every layer.





		
		
			2. Right Side View - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jul 10, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get nodes ordered from top to bottom
// ============================================================================
/**
 * 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<int> RightSideView(TreeNode root) {
        var result = new List<int>();
        Traverse(root, 0, result);
        return result;
    }

    public void Traverse(TreeNode node, int currentDepth, List<int> result) {
        if (node == null) {
            return;
        }
        if (currentDepth == result.Count) {
            result.Add(node.val);
        }
        Traverse(node.right, currentDepth + 1, result);
        Traverse(node.left, currentDepth + 1, 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:   Jul 10, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get nodes ordered from top to bottom
// ============================================================================
/**
 * 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<int> RightSideView(TreeNode root) {
        var result = new List<int>();
        Traverse(root, 0, result);
        return result;
    }
 
    public void Traverse(TreeNode node, int currentDepth, List<int> result) {
        if (node == null) {
            return;
        }
        if (currentDepth == result.Count) {
            result.Add(node.val);
        }
        Traverse(node.right, currentDepth + 1, result);
        Traverse(node.left, currentDepth + 1, 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,3,4] [1,3] []

C# || How To Find The Shortest Clear Path In A Binary Matrix Using C#

June 03, 2022 admin No comments

The following is a module with functions which demonstrates how to find the shortest clear path in a binary matrix using C#.

1. Shortest Path Binary Matrix – Problem Statement

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n – 1, n – 1)) such that:

All the visited cells of the path are 0.
All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Example 1:

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

Example 2:

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

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,0]] Output: -1

2. Shortest Path Binary Matrix – Solution

The following is a solution which demonstrates how find the shortest clear path in a binary matrix.





		
		
			2. Shortest Path Binary Matrix - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jun 3, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find shortest path binary matrix
// ============================================================================
public class Solution {
    // Search directions
    List<KeyValuePair<int, int>> directions = new List<KeyValuePair<int, int>>() {
        // Direction coordinates: (y, x)
        new KeyValuePair<int, int>(0, -1),
        new KeyValuePair<int, int>(0, 1),
        new KeyValuePair<int, int>(-1, 0),
        new KeyValuePair<int, int>(1, 0),
        new KeyValuePair<int, int>(1, 1),
        new KeyValuePair<int, int>(-1, -1),
        new KeyValuePair<int, int>(-1, 1),
        new KeyValuePair<int, int>(1, -1)
    };

    public int ShortestPathBinaryMatrix(int[][] grid) {
        var NOT_VISITED = 0;
        var VISITED = 1;

        if (grid[0][0] == VISITED) {
            return -1;
        }

        var queue = new Queue<KeyValuePair<int, int>>();
        queue.Enqueue(new KeyValuePair<int, int>(0, 0));
        grid[0][0] = VISITED;

        var result = 0;
        while(queue.Count > 0) {
            ++result;
            for (var itemCount = queue.Count; itemCount > 0; --itemCount) {
                var current = queue.Dequeue();

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

                if (row == grid.Length - 1 && col == grid[row].Length - 1) {
                    return result;
                }

                // Search in different directions
                foreach (var direction in directions) {
                    var newRow = row + direction.Key;
                    var newCol = col + direction.Value;

                    if (IsValidCell(grid, newRow, newCol) && grid[newRow][newCol] == NOT_VISITED) {
                        grid[newRow][newCol] = VISITED;
                        queue.Enqueue(new KeyValuePair<int, int>(newRow, newCol));
                    }
                }
            }
        }
        return -1;
    }

    private bool IsValidCell(int[][] grid, int row, int col) {
        return row >= 0 && row < grid.Length && col >= 0 && col < grid[row].Length;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jun 3, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find shortest path binary matrix
// ============================================================================
public class Solution {
    // Search directions
    List<KeyValuePair<int, int>> directions = new List<KeyValuePair<int, int>>() {
        // Direction coordinates: (y, x)
        new KeyValuePair<int, int>(0, -1),
        new KeyValuePair<int, int>(0, 1),
        new KeyValuePair<int, int>(-1, 0),
        new KeyValuePair<int, int>(1, 0),
        new KeyValuePair<int, int>(1, 1),
        new KeyValuePair<int, int>(-1, -1),
        new KeyValuePair<int, int>(-1, 1),
        new KeyValuePair<int, int>(1, -1)
    };
 
    public int ShortestPathBinaryMatrix(int[][] grid) {
        var NOT_VISITED = 0;
        var VISITED = 1;
 
        if (grid[0][0] == VISITED) {
            return -1;
        }
 
        var queue = new Queue<KeyValuePair<int, int>>();
        queue.Enqueue(new KeyValuePair<int, int>(0, 0));
        grid[0][0] = VISITED;
 
        var result = 0;
        while(queue.Count > 0) {
            ++result;
            for (var itemCount = queue.Count; itemCount > 0; --itemCount) {
                var current = queue.Dequeue();
 
                // Get the current coordinates
                var row = current.Key;
                var col = current.Value;
 
                if (row == grid.Length - 1 && col == grid[row].Length - 1) {
                    return result;
                }
 
                // Search in different directions
                foreach (var direction in directions) {
                    var newRow = row + direction.Key;
                    var newCol = col + direction.Value;
 
                    if (IsValidCell(grid, newRow, newCol) && grid[newRow][newCol] == NOT_VISITED) {
                        grid[newRow][newCol] = VISITED;
                        queue.Enqueue(new KeyValuePair<int, int>(newRow, newCol));
                    }
                }
            }
        }
        return -1;
    }
 
    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:

2 4 -1

C# || Palindromic Substrings – How To Find The Number Of Palindromic Substrings Using C#

June 02, 2022 admin No comments

The following is a module with functions which demonstrates how to find the number of palindromic substrings using C#.

1. Count Substrings – Problem Statement

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

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

Example 1:

Input: s = "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

2. Count Substrings – Solution

The following is a solution which demonstrates how to find the number of palindromic substrings.





		
		
			2. Count Substrings - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jun 2, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find palindromic substrings
// ============================================================================
public class Solution {
    public int CountSubstrings(string s) {
        var count = 0;
        for (var index = 0; index < s.Length; ++index) {
            count += CountPalindrome(s, index, index);  // Count even sized
            count += CountPalindrome(s, index, index + 1); // Count odd sized
        }
        return count;
    }

    private int CountPalindrome(string s, int start, int end) {
        var count = 0;
        while (start >= 0 && end < s.Length && s[start--] == s[end++]) {
            ++count;
        }
        return count;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jun 2, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find palindromic substrings
// ============================================================================
public class Solution {
    public int CountSubstrings(string s) {
        var count = 0;
        for (var index = 0; index < s.Length; ++index) {
            count += CountPalindrome(s, index, index);  // Count even sized
            count += CountPalindrome(s, index, index + 1); // Count odd sized
        }
        return count;
    }
 
    private int CountPalindrome(string s, int start, int end) {
        var count = 0;
        while (start >= 0 && end < s.Length && s[start--] == s[end++]) {
            ++count;
        }
        return count;
    }
}// http://programmingnotes.org/

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

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

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

3 6

Tag Archives: leetcode

C# || How To Determine If String Halves Are Alike Using C#

C# || How To Find The Maximum Profit In Job Scheduling Using C#

C# || Contains Duplicate II – How To Determine Two Distinct Indices In Array Equal To Target Value Using C#

C# || How To Find The Nearest Exit From Entrance In Maze Using C#

C# || How To Design A Time Based Key-Value Store To Retrieve Timestamps Using C#

C# || How To Return The Top K Frequent Words In Array Of Strings Using C#

C# || Two Sum IV – How To Get Two Numbers In Binary Search Tree Equal To Target Value Using C#

C# || Counting Bits – How To Return The Number Of 1’s In Binary Representation Of X Using C#

C# || How To Traverse N-ary Tree Level Order Using C#

C# || How To Validate A Binary Search Tree Using C#

C# || Max Area of Island – How To Find The Maximum Area Of An Island In A Grid Using C#

C# || Binary Tree Right Side View – How To Get Nodes Ordered Top To Bottom C#

C# || How To Find The Shortest Clear Path In A Binary Matrix Using C#

C# || Palindromic Substrings – How To Find The Number Of Palindromic Substrings Using C#

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories