## Monday, March 29, 2021

### Leetcode Everyday: 617. Merge Two Binary Trees. Easy

```public class Solution {
public TreeNode MergeTrees(TreeNode root1, TreeNode root2) =>
root1 != null || root2 != null ?
new TreeNode(
(root1?.val ?? 0) + (root2?.val ?? 0),
MergeTrees(root1?.left, root2?.left),
MergeTrees(root1?.right, root2?.right)
)
:
null;
}

// TODO: optimize without allocating
```
Source: https://leetcode.com/problems/merge-two-binary-trees/

## Saturday, March 20, 2021

### Leetcode Everyday: 728. Self Dividing Numbers. Easy

```public class Solution {
public IList<int> SelfDividingNumbers(int left, int right) {
var list = new List<int>();
for (var i = left; i <= right; ++i) {
for (var n = i; n > 0; n /= 10) {
var toDivide = n % 10;
if (toDivide == 0 || i % toDivide != 0) {
goto goNextNumber;
}
}

goNextNumber:;
}
return list;
}
}
```
Source: https://leetcode.com/problems/self-dividing-numbers/

## Tuesday, March 16, 2021

### Leetcode Everyday: 1351. Count Negative Numbers in a Sorted Matrix. Easy

```public int CountNegatives(int[][] grid) {
var count = 0;
foreach (var line in grid) {
for (var i = 0; i < line.Length; ++i) {
if (line[i] <0) {
count += line.Length - i;
break;
}
}
}
return count;
}

// TODO: Create a binary search approach
```
Functional:
```public class Solution {
public int CountNegatives(int[][] grid) => grid.SelectMany(line => line).Count(n => n < 0);
}
```
Source: https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/

## Sunday, March 14, 2021

### Leetcode Everyday: 1464. Maximum Product of Two Elements in an Array. Easy

```public class Solution {
public int MaxProduct(int[] nums) {
// first and second highest
var first = 0;
var second = 0;

foreach (var n in nums) {
if (n > first) {
(first, second) = (n, first);
} else if (n > second) {
second = n;
}
}

return (first - 1) * (second - 1);
}
}```
Funtional Programming:
```public class Solution {
public int MaxProduct(int[] nums) =>
nums.OrderByDescending(n => n).Take(2)
.Aggregate((a, b) => (a-1) * (b-1));
}
```
Source: https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array/

## Saturday, March 13, 2021

### Leetcode Everyday: 1374. Generate a String With Characters That Have Odd Counts. Easy

```public class Solution {
public string GenerateTheString(int n) =>
new string('a', n - (n%2 ^ 1)) + new string('b', 1 - n%2);
}
```
Source: https://leetcode.com/problems/generate-a-string-with-characters-that-have-odd-counts/

## Wednesday, March 10, 2021

### Leetcode Everyday: 1304. Find N Unique Integers Sum up to Zero. Easy

```public class Solution {
public int[] SumZero(int n) {
var list = new int[n];

var ndx = 0;
for (var i = 1; i <= n / 2; ++i) {
list[ndx++] = i;
list[ndx++] = -i;
}

if (n % 2 == 1) {
list[ndx] = 0;
}

return list;
}
}
```
Alternative:
```public class Solution {
public int[] SumZero(int n) {
var list = new int[n];

for (int i = 1, ndx = 0; i <= n / 2; ++i, ndx += 2) {
list[ndx] = i;
list[ndx+1] = -i;
}

if (n % 2 == 1) {
list[^1] = 0;
}

return list;
}
}
```
This works, but is confusing:
```public class Solution {
public int[] SumZero(int n) {
var list = new int[n];

var i = 0;
while (i < n / 2) {
list[i++] = i;
list[^i] = -i;
}

if (n % 2 == 1) {
list[i] = 0;
}

return list;
}
}
```
Source: https://leetcode.com/problems/find-n-unique-integers-sum-up-to-zero/submissions/

### Leetcode Everyday: 1370. Increasing Decreasing String. Easy

```public class Solution {
public string SortString(string s) {
var sorted = s.Distinct().OrderBy(x => x).ToList();
var sortedDesc = sorted.OrderByDescending(x => x).ToList();

var sb = new StringBuilder();

var isAscending = true;
for (; s.Length > 0; isAscending = !isAscending) {
var toSort = isAscending ? sorted : sortedDesc;
foreach (var c in toSort) {
var i = s.IndexOf(c);
if (i >= 0) {
s = s.Remove(i, 1);
sb.Append(c);
}
}
}

return sb.ToString();
}
}
```
Optimized
```public class Solution {
public string SortString(string s) {
const int z = 26;
var freq = new int[z];

var sLength = s.Length;
var sb = new char[sLength]; // think of this as StringBuilder

foreach (var c in s){
++freq[c - 'a'];
}

for (var i = 0; i < sLength; ){

for (var small = 0; small < z; ++small){
if (freq[small] > 0){
--freq[small];
sb[i] = (char)('a' + small);

++i;
}
}

for (var large = z - 1; large >= 0; --large){
if (freq[large] > 0){
--freq[large];
sb[i] = (char)('a' + large);

++i;
}
}

}

return new string(sb);
}
}
```
Source: https://leetcode.com/problems/increasing-decreasing-string/submissions/

## Monday, March 8, 2021

### Leetcode Everyday: 1704. Determine if String Halves Are Alike. Easy

```public class Solution {
public bool HalvesAreAlike(string s) {
var half = s.Length / 2;
var a = s.Substring(0, half);
var b = s.Substring(s.Length - half, half);

var vowels = new HashSet<char>() {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};

return a.Count(c => vowels.Any(v => char.ToUpper(c) == v))
== b.Count(c => vowels.Any(v => char.ToUpper(c) == v));
}
}
```
Optimized:
```public class Solution {
public bool HalvesAreAlike(string s) {
var half = s.Length / 2;
var vowels = new HashSet<char>() {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};

var count = 0;
for (var i = 0; i < half; ++i) {
if (vowels.Contains(s[i]))
++count;

if (vowels.Contains(s[^(i + 1)]))
--count;
}
return count == 0;
}
}
```
```public class Solution {
public bool HalvesAreAlike(string s) {
var half = s.Length / 2;

var count = 0;
for (var i = 0; i < half; ++i) {
if (s[i] switch {
'A' => true,
'a' => true,
'E' => true,
'e' => true,
'I' => true,
'i' => true,
'O' => true,
'o' => true,
'U' => true,
'u' => true,
_ => false
}) {
++count;
}

if (s[(^(i + 1))] switch {
'A' => true,
'a' => true,
'E' => true,
'e' => true,
'I' => true,
'i' => true,
'O' => true,
'o' => true,
'U' => true,
'u' => true,
_ => false
}) {
--count;
}
}
return count == 0;
}
}
```
Source: https://leetcode.com/problems/determine-if-string-halves-are-alike/

## Sunday, March 7, 2021

### Leetcode Everyday: 1436. Destination City. Easy

```public class Solution {
public string DestCity(IList<IList<string>> paths) {
var pathLookup = new Dictionary<string, string>();

foreach (var path in paths) {
pathLookup[path.First()] = path.Last();
}

var source = pathLookup.FirstOrDefault().Key;
while (pathLookup.TryGetValue(source, out string destination)) {
source = destination;
}

return source;
}
}
```
Functional programming:
```public class Solution {
public string DestCity(IList<IList<string>> paths) =>
paths.Single(dest => !paths.Any(source => dest.Last() == source.First())).Last();
}
```
Optimized:
```public class Solution {
public string DestCity(IList<IList<string>> paths) {
var outgoing = new HashSet<string>();
outgoing.UnionWith(paths.Select(path => path.First()));

foreach (var path in paths) {
if (!outgoing.Contains(path.Last())) {
return path.Last();
}
}

return null;
}
}
```
Source: https://leetcode.com/problems/destination-city/submissions/

## Saturday, March 6, 2021

### Leetcode Everyday: 1309. Decrypt String from Alphabet to Integer Mapping. Easy

```using System.Text.RegularExpressions;

public class Solution {
public string FreqAlphabets(string s) {
var lookup = new Dictionary<string, char>();

var rx = new Regex(@"\d{2}#|\d{1}");
var alphabet = "12345678910#11#12#13#14#15#16#17#18#19#20#21#22#23#24#25#26#";

var c = 'a';
foreach (var match in rx.Matches(alphabet).Cast<Match>()) {
lookup[match.Value] = c++;
}

var sb = new StringBuilder();
foreach (var match in rx.Matches(s).Cast<Match>()) {
sb.Append(lookup[match.Value]);
}

return sb.ToString();
}
}
```
Optimized:
```public class Solution {
public string FreqAlphabets(string s) {
var sb = new StringBuilder();
for (var i = 0; i < s.Length; ) {
if (i+2 < s.Length && s[i+2] == '#') {
sb.Append((char)('a' + (s[i]-'0')*10 + s[i+1]-'0' - 1));
i += 3;
} else {
sb.Append((char)('a' + s[i]-'0' - 1));
++i;
}
}
return sb.ToString();
}
}
```
Source: https://leetcode.com/problems/decrypt-string-from-alphabet-to-integer-mapping/

## Thursday, March 4, 2021

### Leetcode Everyday: 1725. Number Of Rectangles That Can Form The Largest Square. Easy

```public class Solution {
public int CountGoodRectangles(int[][] rectangles) {
var minCounts = new Dictionary<int, int>();

foreach (var r in rectangles) {
var min = Math.Min(r[0], r[1]);
minCounts[min] =
(minCounts.TryGetValue(min, out int value) ? value : 0) + 1;
}

return minCounts[minCounts.Keys.Max()];
}
}
```
Source: https://leetcode.com/problems/number-of-rectangles-that-can-form-the-largest-square/

## Wednesday, March 3, 2021

### Leetcode Everyday: 1323. Maximum 69 Number. Easy

```public class Solution {
public int Maximum69Number (int num) {

var sNum = num.ToString();
var foundAt = sNum.IndexOf('6');

if (foundAt >= 0) {
return num +  (3 * (int)Math.Pow(10, sNum.Length - foundAt - 1));
}

return num;
}
}
```
Same speed as above (32ms), but uses less memory:
```public class Solution {
public int Maximum69Number (int num) {

for (int temp = num, step = 1; temp > 0; temp /= 10, step *= 10) {
if (temp % 10 == 6) {
}
}

}
}
```
Source: https://leetcode.com/problems/maximum-69-number/

## Tuesday, March 2, 2021

### Leetcode Everyday: 1572. Matrix Diagonal Sum. Easy

```public class Solution {
public int DiagonalSum(int[][] mat) {
var sum = 0;

var length = mat.Length;
for (var walk = 0; walk < length; ++walk) {
sum += mat[walk][walk] + mat[^(walk + 1)][walk];
}

// exclude center
var center = Math.DivRem(length, 2, out int remainder);
if (remainder == 1) {
sum -= mat[center][center];
}

return sum;
}
}
```
Source: https://leetcode.com/problems/matrix-diagonal-sum/

## Monday, March 1, 2021

### Leetcode Everyday: 832. Flipping an Image. Easy

```public class Solution {
public int[][] FlipAndInvertImage(int[][] image) {
foreach (var row in image) {
for (var col = 0; col < row.Length / 2; ++col) {
// shorthand:
(row[col], row[^(col+1)]) = (row[^(col+1)], row[col]);

// longhand:
// (row[col], row[row.Length - (col+1)]) = (row[row.Length - (col+1)], row[col]);
}

for (var col = 0; col < row.Length; ++col) {
row[col] ^= 1;
}
}

return image;
}
}
```
Optimized:
```public class Solution {
public int[][] FlipAndInvertImage(int[][] image) {
foreach (var row in image) {
var half = row.Length / 2;
for (var col = 0; col < half; ++col) {
// shorthand:
(row[col], row[^(col+1)]) = (row[^(col+1)] ^ 1, row[col] ^ 1);

// longhand:
// (row[col], row[row.Length - (col+1)]) = (row[row.Length - (col+1)], row[col]);
}
}

if (image.Length > 0 && image[0].Length % 2 == 1) {
var middle = image[0].Length / 2;
foreach (var row in image) {
row[middle] ^= 1;
}
}

return image;
}
}
```
Source: https://leetcode.com/problems/flipping-an-image/