Friday, February 26, 2021

Leetcode Everyday: 1252. Cells with Odd Values in a Matrix. Easy

public class Solution {
    public int OddCells(int n, int m, int[][] indices) {
        var mat = new int[n, m];
        
        foreach (var index in indices) {
            var ri = index[0];                
            for (var col = 0; col < m; ++col) {
                ++mat[ri, col];
            }
            
            var ci = index[1];
            for (var row = 0; row < n; ++row) {
                ++mat[row, ci];
            }
        }
        
        
        // functional programming:
        // return mat.Cast<int>().Count(number => number % 2 == 1);
        
        
        // this would work:
        // var oddCount = 0;
        // for (var ni = 0; ni < n; ++ni) {
        //     for (var mi = 0; mi < m; ++mi) {
        //         oddCount += mat[ni, mi] % 2;
        //     }
        // }
        
        
        // this is better and faster. C# can look at array as if it is one-dimensional
        var oddCount = 0;
        foreach (var number in mat) {
            oddCount += number % 2;
        }        
        return oddCount;
    }
}
Source: https://leetcode.com/problems/cells-with-odd-values-in-a-matrix/

Wednesday, February 24, 2021

Leetcode Everyday: 804. Unique Morse Code Words. Easy

Functional programming:
public class Solution {
    readonly string[] morseCodes = new[] {
        ".-","-...","-.-.","-..",".",
        "..-.","--.","....","..",".---",
        "-.-",".-..","--","-.","---",
        ".--.","--.-",".-.","...","-",
        "..-","...-",".--","-..-","-.--","--.."
    };
    
    public int UniqueMorseRepresentations(string[] words) =>
        words.Select(word =>
            word.Skip(1).Aggregate(
                morseCodes[word[0] - 'a'].ToString(),
                (txMorse, current) => txMorse + morseCodes[current - 'a']
            )
        ).Distinct().Count();    
}
Imperative programming:
public class Solution {

    public int UniqueMorseRepresentations(string[] words) {        
        var morseCodes = new[] {
            ".-","-...","-.-.","-..",".",
            "..-.","--.","....","..",".---",
            "-.-",".-..","--","-.","---",
            ".--.","--.-",".-.","...","-",
            "..-","...-",".--","-..-","-.--","--.."
        };
        
		var distinctMorses = new HashSet();
        var buildMorse = new StringBuilder();
        foreach (var word in words) {
        
            foreach (var c in word) {
                buildMorse.Append(morseCodes[c - 'a']);
            }
            
            var txMorse = buildMorse.ToString();
            buildMorse.Clear();
            
            if (!distinctMorses.Contains(txMorse)) {
                distinctMorses.Add(txMorse);
            }
        }        
        return distinctMorses.Count;
    }      
          
}
Source: https://leetcode.com/problems/unique-morse-code-words/

Tuesday, February 23, 2021

Leetcode Everyday: 1021. Remove Outermost Parentheses. Easy

public class Solution {
    public string RemoveOuterParentheses(string s) {
        var sb = new StringBuilder();        
    
        var opList = new Dictionary<char, int> {
            ['('] = 1,
            [')'] = -1
        };
        
        int depth = 0;
        foreach (var c in s) {
            var op = opList[c];
            depth += op;
            if (op == 1 && depth > 1 || op == -1 && depth > 0) {
                sb.Append(c);
            }
        }
        
        return sb.ToString();
    }
}
Compact condition:
public class Solution {
    public string RemoveOuterParentheses(string s) {
        var sb = new StringBuilder();
         
     
        // KeyValue<op, depth>
        // op = 1 = increment
        // op = -1 = decrement
        var opList = new Dictionary<char, KeyValuePair<int, int>> {
            ['('] = new KeyValuePair<int, int>(1, 1),
            [')'] = new KeyValuePair<int, int>(-1, 0)
        };
         
         
        int depth = 0;
        foreach (var c in s) {
            var (op, opDepth) = opList[c];
            depth += op;
                  
            if (depth > opDepth) {
                sb.Append(c);
            }
        }
         
        return sb.ToString();
    }
}
Source: https://leetcode.com/problems/remove-outermost-parentheses/

Monday, February 22, 2021

Leetcode Everyday: 1295. Find Numbers with Even Number of Digits. Easy

Functional programming:
using static System.Math;

public class Solution {
    public int FindNumbers(int[] nums) =>
        nums.Count(num => CountDigit(num) % 2 == 0);
    
    public int CountDigit(int n) => (int)Max(Log10(n), 0) + 1;
}
Imperative programming:
using static System.Math;

public class Solution {
    public int FindNumbers(int[] nums) {
        int evenCount = 0;
        foreach (var num in nums) {
            if (CountDigit(num) % 2 == 0) {
                ++evenCount;
            }  
        }
        return evenCount;
        
        int CountDigit(int num) {            
            int digit = 0;
            for (; num != 0; num /= 10) {
                ++digit;
            }
            return Max(digit, 1);
        }
    }
}
Source: https://leetcode.com/problems/find-numbers-with-even-number-of-digits/submissions/

Leetcode Everyday: 1266. Minimum Time Visiting All Points. Easy

Functional programming:
using static System.Math;

public class Solution {
    public int MinTimeToVisitAllPoints(int[][] points) =>
        points.Skip(1).Aggregate(
            new { count = 0, source = points.First() },
            (stat, dest) =>
                new
                { 
                    count = stat.count + 
                        Max(Abs(dest[0] - stat.source[0]), Abs(dest[1] - stat.source[1])), 
                    source = dest 
                }
        ).count;
}
Imperative programming:
using static System.Math;

public class Solution {
    public int MinTimeToVisitAllPoints(int[][] points) {
        var count = 0;
        
        var source = points.First();
        foreach (var dest in points.Skip(1)) {                                
            var lengthX = dest[0] - source[0];
            var lengthY = dest[1] - source[1];
            
            count += Max(Abs(lengthX), Abs(lengthY));
        
            source = dest;
        }
        
        return count;
    }
}
Source: https://leetcode.com/problems/minimum-time-visiting-all-points/

Sunday, February 21, 2021

Leetcode Everyday: 709. To Lower Case. Easy

It's in the rules not to use the built-in method. Here's a solution without using the built-in method
public class Solution {
    public string ToLowerCase(string str) {
        var sb = new StringBuilder(str);
        for (var i = 0; i < sb.Length; ++i) {
            char c = sb[i];
            if (c >= 'A' && c <= 'Z') {
                sb[i] =  (char)(c + ('a' - 'A'));
            }
        }
        return sb.ToString();
    }
}
Source: https://leetcode.com/problems/to-lower-case/

Leetcode Everyday: 1534. Count Good Triplets. Easy

public class Solution {
    public int CountGoodTriplets(int[] arr, int a, int b, int c) {
        int goodTriplets = 0;
        
        for (var i = 0; i < arr.Length - 2; ++i) 
            for (var j = i + 1; j < arr.Length - 1; ++j)
                for (var k = j + 1; k < arr.Length; ++k) {
                    if (Math.Abs(arr[i] - arr[j]) <= a && Math.Abs(arr[j] - arr[k]) <= b && Math.Abs(arr[i] - arr[k]) <= c) {
                        ++goodTriplets;
                    }       
                }
        
        return goodTriplets;
    }
}
Source: https://leetcode.com/problems/count-good-triplets/

Leetcode Everyday: 1732. Find the Highest Altitude. Easy

Solution using functional programming:
public class Solution {

    public int LargestAltitude(int[] gains) =>
        gains.Aggregate(      
            // Initial currentData:
            new { runningAlt = 0, maxAlt = 0}, 
        
            (currentData, gained) =>
                new 
                { 
                    runningAlt = 
                        currentData.runningAlt + gained, 
                    maxAlt = 
                        currentData.runningAlt + gained > currentData.maxAlt ? 
                            currentData.runningAlt + gained 
                        : 
                            currentData.maxAlt
                }
        ).maxAlt;
    
}
Imperative programming:
public class Solution {

    public int LargestAltitude(int[] gains) {
        var runningAlt = 0;
        var maxAlt = 0;
        
        foreach (var gained in gains) {
            runningAlt += gained;
            
            if (runningAlt > maxAlt) {
                maxAlt = runningAlt;
            }
        }
        
        return maxAlt;
    }
    
}
Source: https://leetcode.com/problems/find-the-highest-altitude/

Saturday, February 20, 2021

Leetcode Everyday: 1290. Convert Binary Number in a Linked List to Integer

public class Solution {
    public int GetDecimalValue(ListNode head) {    
        var stack = new Stack<int>();        
        while (head != null) {
            stack.Push(head.val);
            head = head.next;
        }
        
        int n = 1;
        int sum = 0;        
        foreach (var digit in stack) {
            sum += digit * n;
            n *= 2;
        }
        return sum;
    }
}
Source: https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer/

Leetcode Everyday: 1588. Sum of All Odd Length Subarrays. Easy

Solution for Sum of All Odd Length Subarrays:
public class Solution {
    public int SumOddLengthSubarrays(int[] arr) {
        int globalSum = 0;
           
        for (var odd = 1; odd <= arr.Length; odd += 2) {
            int count = 0;
            int sum = 0;
            for (; count < odd; ++count) {
                sum += arr[count];
            }
            // Log(sum);
            globalSum += sum;
            for (var i = count; i < arr.Length; ++i) {                
                sum += arr[i] - arr[i - odd];
                // Log(sum);
                globalSum += sum;
            }
            // Console.WriteLine();
        }
            
        return globalSum;
    }
    
    void Log(int n) {
          Console.Write("{0} ", n);   
    }
}
Output:
1 4 2 5 3 
7 11 10 
15 
There's a better solution than the above solution

Friday, February 19, 2021

Leetcode Everyday: 1179. Reformat Department Table. Easy

select id, 
    sum(case when month = 'Jan' then revenue end) as "Jan_Revenue",
    sum(case when month = 'Feb' then revenue end) as "Feb_Revenue",
    sum(case when month = 'Mar' then revenue end) as "Mar_Revenue",    
    sum(case when month = 'Apr' then revenue end) as "Apr_Revenue",    
    sum(case when month = 'May' then revenue end) as "May_Revenue",    
    sum(case when month = 'Jun' then revenue end) as "Jun_Revenue",    
    sum(case when month = 'Jul' then revenue end) as "Jul_Revenue",    
    sum(case when month = 'Aug' then revenue end) as "Aug_Revenue",    
    sum(case when month = 'Sep' then revenue end) as "Sep_Revenue",    
    sum(case when month = 'Oct' then revenue end) as "Oct_Revenue",    
    sum(case when month = 'Nov' then revenue end) as "Nov_Revenue",
    sum(case when month = 'Dec' then revenue end) as "Dec_Revenue"
from department
group by id
Source: https://leetcode.com/problems/reformat-department-table/

Leetcode Everyday: 1656. Design an Ordered Stream. Easy

public class OrderedStream {
    
    int _ptr = 1;
    readonly int _max;
    readonly string[] _list;

    public OrderedStream(int n) {
        _list = new string[n + 1];
        _max = n;
    }
    
    public IList<string> Insert(int idKey, string value) {       
        _list[idKey] = value;
        
        int start = _ptr;
        while (_ptr <= _max && _list[_ptr] != null) {
            ++_ptr;
        }
        
      
        // 424 ms.  
        // return _list[start.._ptr];        
        
        // 376 ms. For some reasons, this is faster
        return new Span<string>(_list, start, length: _ptr - start).ToArray();
    }
}
Fastest

Source: https://leetcode.com/problems/design-an-ordered-stream/

Thursday, February 18, 2021

Leetcode Everyday: 1688. Count of Matches in Tournament. Easy

public class Solution {
    public int NumberOfMatches(int teams) {          
        int matchesSum = 0;
        while (teams > 1) {
            int matches = teams / 2;
            matchesSum += matches;                        
            teams -= matches;   
        }
        
        return matchesSum;
    }
}
Source: https://leetcode.com/problems/count-of-matches-in-tournament/

Leetcode Everyday: 1614. Maximum Nesting Depth of the Parentheses. Easy

public class Solution {
    public int MaxDepth(string s) {
        int depth = 0;
        int maxDepth = 0;
        foreach (var c in s) {
            if (c == '(') {
                ++depth;
            } else if (c == ')') {
                --depth;
            }
            if (depth > maxDepth) {
                maxDepth = depth;
            }
        }
        return maxDepth;
    }
}
Source: https://leetcode.com/problems/maximum-nesting-depth-of-the-parentheses/

Leetcode Everyday: 938. Range Sum of BST. Easy

public class Solution {
    public int RangeSumBST(TreeNode root, int low, int high) {
        int sum = low <= root.val && root.val <= high ? root.val : 0;
        
        if (root.left != null) {
            sum += RangeSumBST(root.left, low, high);
        }
        if (root.right != null) {
            sum += RangeSumBST(root.right, low, high);
        }
        
        return sum;
    }
}
Source: https://leetcode.com/problems/range-sum-of-bst/

Wednesday, February 17, 2021

Leetcode Everyday: 1684. Count the Number of Consistent Strings. Easy

public class Solution {
     public int CountConsistentStrings(string allowed, string[] words) =>
         words.Count(word => !word.Any(wc => allowed.IndexOf(wc) == -1));
}
Solution 2, faster and still readable:
public class Solution {
    public int CountConsistentStrings(string allowed, string[] words) {
        int count = 0;
        foreach (string word in  words) {     
            foreach (char c in word) {          
              if (allowed.IndexOf(c) == -1) {
                 goto nextWord;
              }
            }
            ++count;
        nextWord:;
        }
        return count;
    }
}
Solution 2b, goto-less:
public class Solution {
    public int CountConsistentStrings(string allowed, string[] words) {
        int count = words.Length;
        foreach (string word in  words) {     
            foreach (char c in word) {          
              if (allowed.IndexOf(c) == -1) {
                 --count;
                  break;
              }
            }
        }
        return count;
    }
}
Solution 3, goto when used judiciously makes for a faster code. This is the fastest C# code on leetcode. Optimized other's code by converting boolean+break combo to a goto:
public class Solution {
    public int CountConsistentStrings(string allowed, string[] words) {
        bool[] valid = new bool[26];

        foreach (char c in allowed) valid[c - 'a'] = true;

        int count = 0;
        foreach (var word in words) {
            foreach (char c in word) if (!valid[c - 'a']) goto nextWord;
            
            ++count;            
        nextWord:;
        }
        
        return count;
    }
}
Solution 4, almost same as above, fastet code too. Just reversed the logic, something is valid until it is not. So the count starts with words.Length. made it goto-less
public class Solution {
    public int CountConsistentStrings(string allowed, string[] words) {
        bool[] valid = new bool[26];

        foreach (char c in allowed) valid[c - 'a'] = true;

        int count = words.Length;
        foreach (var word in words) {
            foreach (char c in word) {
                if (!valid[c - 'a']) {
                    --count;
                    break;
                }
            }
        }
        
        return count;
    }
}
Source: https://leetcode.com/problems/count-the-number-of-consistent-strings/

Leetcode Everyday: 1662. Check If Two String Arrays are Equivalent. Easy

public class Solution {
    public bool ArrayStringsAreEqual(string[] word1, string[] word2) {
        var isEqual = word1.Aggregate((left, right) => left + right) == word2.Aggregate((left, right) => left + right);
        
        return isEqual;
    }
}
Source: https://leetcode.com/problems/check-if-two-string-arrays-are-equivalent/

Tuesday, February 16, 2021

Leetcode Everyday: 1221. Split a String in Balanced Strings. Easy

public class Solution {
    public int BalancedStringSplit(string s) {
        var balanceCount = 0;
        var balanceDetector = 0;
        foreach (var c in s) {
            balanceDetector += c == 'L' ? 1 : -1;
            balanceCount += balanceDetector == 0 ? 1 : 0;
        }
        return balanceCount;
    }
}

Leetcode. 1486. XOR Operation in an Array. Easy

public class Solution {
    public int XorOperation(int n, int start) {
        int xored = 0;
        for (var i = 0; i < n; ++i) {
            xored ^= start + 2 * i;
        }
        return xored;
    }
}

Leetcode Everyday: 1389. Create Target Array in the Given Order. Easy

public class Solution {
    public int[] CreateTargetArray(int[] nums, int[] indexes) {    
        var list = new List<int>();
        
        foreach (var (num, index) in nums.Zip(indexes, (num, index) => (num, index))) {
            list.Insert(index, num);
        }
        return list.ToArray();
    }
}
Source: https://leetcode.com/problems/create-target-array-in-the-given-order/

Monday, February 15, 2021

Leetcode Everyday: 1313. Decompress Run-Length Encoded List. Easy

public class Solution {
    public int[] DecompressRLElist(int[] nums) {
        var list = new List<int>();
        for (var i = 0; i < nums.Length; i += 2) {
            var count = nums[i];
            var toDup = nums[i + 1];
            
            while (count-- > 0) {
                list.Add(toDup);
            }
        }
        return list.ToArray();
    }
}
Source: https://leetcode.com/problems/decompress-run-length-encoded-list/

Leetcode Everyday: 1281. Subtract the Product and Sum of Digits of an Integer. Easy

public class Solution {
    public int SubtractProductAndSum(int n) {
        int prod = 1;
        int sum = 0;
        for (; n > 0; n /= 10) {
            var remainder = n % 10;
            prod *= remainder;
            sum += remainder;
        }
        return prod - sum;
    }
}
Source: https://leetcode.com/problems/subtract-the-product-and-sum-of-digits-of-an-integer/submissions/

Leetcode Everyday: 1678. Goal Parser Interpretation. Easy

public class Solution {
    public string Interpret(string command) {
        var replaceWith = new Dictionary<string, string>() 
        {
            ["()"] = "o",
            ["(al)"] = "al"
        };
        foreach (var (key, value) in replaceWith) {
            command = command.Replace(key, value);
        }
        return command;
    }
}
Source: https://leetcode.com/problems/goal-parser-interpretation/submissions/

Leetcode Everyday: 1720. Decode XORed Array. Easy

public class Solution {
    public int[] Decode(int[] encoded, int first) {
        var list = new List<int>();
        var hidden = first;
        list.Add(hidden);
        foreach (var enc in encoded) {
            hidden ^= enc;
            list.Add(hidden);
        }
        return list.ToArray();
    }
}
Source: https://leetcode.com/problems/decode-xored-array/

Leetcode Everyday: 1528. Shuffle String. Easy

public class Solution {
    public string RestoreString(string s, int[] indices) {
        var sb = new StringBuilder();
        for (var i = 0; i < indices.Length; ++i) {
            var charPosition = Array.IndexOf(indices, i);
            sb.Append(s[charPosition]);
        }
        return sb.ToString();
    }
}
Source: https://leetcode.com/problems/shuffle-string/

Sunday, February 14, 2021

Leetcode Everyday: 1342. Number of Steps to Reduce a Number to Zero. Easy

public class Solution {
    public int NumberOfSteps (int num) {
        int steps = 0;
        while (num > 0) {
            ++steps;
            num = num % 2 == 0 ? num / 2 : num - 1;
        }
        return steps;
    }
}
Source: https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/

Leetcode Everyday: 1365. How Many Numbers Are Smaller Than the Current Number. Easy

public class Solution {
    public int[] SmallerNumbersThanCurrent(int[] nums) {
        var sorted = nums.OrderBy(n => n).ToArray();
        var smallCounts = new List();
        for (var i = 0; i < nums.Length; ++i) {
            var count = Array.IndexOf(sorted, nums[i]);
            smallCounts.Add(count);
        }
        return smallCounts.ToArray();
    }
}
Source: https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/

Leetcode Everyday: 1603. Design Parking System. Easy

public class ParkingSystem {
    
    Dictionary<int, int> _parkSlots = new Dictionary<int, int>();

    public ParkingSystem(int big, int medium, int small) {
        _parkSlots[1] = big;
        _parkSlots[2] = medium;
        _parkSlots[3] = small;
    }
    
    public bool AddCar(int carType) {
        if (_parkSlots[carType] > 0) {
            --_parkSlots[carType];
            return true;
        }
        return false;
    }
}


Leetcode Everyday: 771. Jewels and Stones. Easy

public class Solution {
    public int NumJewelsInStones(string jewels, string stones) {
        var list = 
            from stone in stones
            where jewels.Any(jewel => stone == jewel)
            select stone;
        
        return list.Count();
    }
}

Source: https://leetcode.com/problems/jewels-and-stones/

Leetcode Everyday: 1512. Number of Good Pairs. Easy

public class Solution {
    public int NumIdenticalPairs(int[] nums) {
        int goodPairs = 0;
        for (var i = 0; i < nums.Length - 1; ++i) {
            for (var j = i + 1; j < nums.Length; ++j) {
                if (nums[i] == nums[j]) {
                    ++goodPairs;
                }
            }
        }
        return goodPairs;
    }
}
Source: https://leetcode.com/problems/number-of-good-pairs/

Leetcode everyday: 1470. Shuffle the Array. Easy

public class Solution {
    public int[] Shuffle(int[] nums, int n) {
        var list = new List<int>();

        for (var i = 0; i < n; ++i) {
            list.Add(nums[i]);
            list.Add(nums[n + i]);
        }
        
        return list.ToArray();
    }
}
Source: https://leetcode.com/problems/shuffle-the-array/

Leetcode Everyday: 1431. Kids With Greatest Number of Candies. Easy

public class Solution {
    public IList KidsWithCandies(int[] candies, int extraCandies) {
        var maxCandy = candies.Max();
        return candies.Select(candy => candy + extraCandies >= maxCandy).ToList();
    }
}
Source: https://leetcode.com/problems/kids-with-the-greatest-number-of-candies/

Leetcode Everyday: 1672. Richest Customer Wealth. Easy

public class Solution {
    public int MaximumWealth(int[][] accounts) {
        return accounts.Select(a => a.Sum()).Max();
    }
}
Source: https://leetcode.com/problems/richest-customer-wealth/

Leetcode Everyday: 1108. Defanging an IP Address. Easy

public class Solution {
    public string DefangIPaddr(string address) {
        return address.Replace(".", "[.]");
    }
}
Source: https://leetcode.com/problems/defanging-an-ip-address/

Leetcode Everyday: 1480. Running Sum of 1d Array. Easy

public class Solution {
    public int[] RunningSum(int[] nums) {
        var accum = 0;
        var list = new List<int>();
        foreach (var n in nums) {
            accum += n;
            list.Add(accum);
        }
        return list.ToArray();
    }
}
Source: https://leetcode.com/problems/running-sum-of-1d-array/