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;
                }                
            }
            list.Add(i);
            
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);
    }
}
Functional 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/

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) {
    
            var add = 0;

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

            return num + add;
    }
}
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/