Another Casual Coder

Problem is here:  https://leetcode.com/problems/buddy-strings/description/ Given two strings  A  and  B  of lowercase letters, return  true  if and only if we can swap two letters in  A  so that the result equals  B . Example 1: Input: A = "ab" , B = "ba" Output: true Example 2: Input: A = "ab" , B = "ab" Output: false Example 3: Input: A = "aa" , B = "aa" Output: true Example 4: Input: A = "aaaaaaabc" , B = "aaaaaaacb" Output: true Example 5: Input: A = "" , B = "aa" Output: false Note: 0 <= A.length <= 20000 0 <= B.length <= 20000 A  and  B  consist only of lowercase letters. Problem is deceivingly more obnoxious than it looks. Not hard in terms of "algorithms", but rather the different "special" cases need to be thought thru properly. Here they are: Conditions where you know there won't be a solut...

Problem is here:  https://leetcode.com/problems/maximum-width-ramp/description/ : Given an array  A  of integers, a  ramp  is a tuple  (i, j)  for which  i < j  and  A[i] <= A[j] .  The width of such a ramp is  j - i . Find the maximum width of a ramp in  A .  If one doesn't exist, return 0. Example 1: Input: [6,0,8,2,1,5] Output: 4 Explanation: The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5. Example 2: Input: [9,8,1,0,1,9,4,0,4,1] Output: 7 Explanation: The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1. Note: 2 <= A.length <= 50000 0 <= A[i] <= 50000 There must be an O(N) solution to this problem, but I got an NLogN one (sorry). The idea is the following: Create a class called "Pair" which will have the value and index of the array Implement an IComparable interface (to be used in the Sort algorithm) ...

This one comes from Lyft, by Daily Coding Problem: This problem was asked by Lyft. Given a list of integers and a number K, return which contiguous elements of the list sum to K. For example, if the list is [1, 2, 3, 4, 5] and K is 9, then it should return [2, 3, 4]. I changed the problem a bit so that you should return the shortest contiguous array that sums up to K. The O(N^2)-time solution is trivial (two tested loops, keeping track of the shortest length). There is an O(N)-time which goes like this: Keep a variable holding the sum from 1.. up to "i" Hash table that sum, with the value being the index "i" Then, always check to see if sum - k has already been added to the hash table If so, then get that index, call it j The shortest contiguous sum will be from j+1..i, unless  j == i, in which case the solution is a single number (i..i) For this input for example: Numbers = {-3 0 -1 2 -3 4 -6 12 13 -6 -7 7 8} K=21 The solution should ...

This problem comes from Alibaba, via Daily Coding Problem: This problem was asked by Alibaba. Given an even number (greater than 2), return two prime numbers whose sum will be equal to the given number. A solution will always exist. See  Goldbach’s conjecture . Example: Input: 4 Output: 2 + 2 = 4 If there are more than one solution possible, return the lexicographically smaller solution. If [a, b] is one solution with a <= b, and [c, d] is another solution with c <= d, then [a, b] < [c, d] If a < c OR a==c AND b < d. My solution is O(n)-time and O(n)-space; Sieve it up to n in order to cache the primes/non-primes Use the two-pointers (left and right) to find the answer Hence the solution for N = 98778998 would be: 79 + 98778919 Code is on GitHub, here: https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem12242018.cs and also down below, cheers, Marcelo. class DailyCodingProblem12242018 { p...

Problem is here:  https://leetcode.com/problems/shortest-path-to-get-all-keys/description/ : We are given a 2-dimensional  grid .  "."  is an empty cell,  "#"  is a wall,  "@"  is the starting point, ( "a" ,  "b" , ...) are keys, and ( "A" ,  "B" , ...) are locks. We start at the starting point, and one move consists of walking one space in one of the 4 cardinal directions.  We cannot walk outside the grid, or walk into a wall.  If we walk over a key, we pick it up.  We can't walk over a lock unless we have the corresponding key. For some  1 <= K <= 6 , there is exactly one lowercase and one uppercase letter of the first  K  letters of the English alphabet in the grid.  This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet. Return the ...

Here is the problem:  https://leetcode.com/problems/implement-trie-prefix-tree/description/ Implement a trie with  insert ,  search , and  startsWith  methods. Example: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // returns true trie.search("app"); // returns false trie.startsWith("app"); // returns true trie.insert("app"); trie.search("app"); // returns true Note: You may assume that all inputs are consist of lowercase letters  a-z . All inputs are guaranteed to be non-empty strings. I've written about Tries before ( https://anothercasualcoder.blogspot.com/2018/09/a-simple-trie-for-prefix-match-problem.html ), with the implementation using just a Hashtable and a boolean, take a look at the other post I linked here. Cheers, Marcelo. public class Trie { private Hashtable ht = null; private bool endOfWord = false; /** Initialize your data structure here. */ public...

Problem is here:  https://leetcode.com/problems/binary-tree-postorder-traversal/ Given a binary tree, return the  postorder  traversal of its nodes' values. Example: Input:   [1,null,2,3] 1 \ 2 / 3 Output:   [3,2,1] Follow up:  Recursive solution is trivial, could you do it iteratively? The recursive solution is indeed trivial and I don't really think this should be considered a hard problem. Solution is below, cheers, Marcelo. public class Solution { public IList PostorderTraversal(TreeNode root) { List list = new List (); PostorderTraversal(root, list); return list; } private void PostorderTraversal(TreeNode root, IList list) { if (root == null) return; PostorderTraversal(root.left, list); PostorderTraversal(root.right, list); list.Add(root.val); } }

This problem comes via Daily Coding Problem : This problem was asked by Microsoft. Given an unsorted array of integers, find the length of the longest consecutive elements sequence. For example, given  [100, 4, 200, 1, 3, 2] , the longest consecutive element sequence is [1, 2, 3, 4] . Return its length:  4 . Your algorithm should run in  O(n)  complexity. The idea is to use some extra space (O(n)-space) to accomplish an O(n)-time solution. Basically we'll make use of two hash tables: First one contains all the (unique) numbers from the input array Second one will be used later to mark the "visited" numbers As you progress thru the first hash table, then do a "search" to the left and to the right looking for non-visited numbers. As you continue, increase your current sequence length. A very important point is to upon visiting any number, always mark it as visited . This will guarantee the linearity of your solution: each number will be at most ...

Problem is here:  https://leetcode.com/problems/search-a-2d-matrix-ii/description/ Write an efficient algorithm that searches for a value in an  m  x  n  matrix. This matrix has the following properties: Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom. Example: Consider the following matrix: [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] Given target =  5 , return  true . Given target =  20 , return  false . The trick is actually to start the search from the top right corner : if the target is equal to that cell, great, otherwise either move to the left or down for a total of O(m+n)-time and no extra space. Cheers, Marcelo. public class Solution { public bool SearchMatrix(int[,] matrix, int target) { if (matrix == null || matrix.GetLength(...

Problem is here:  https://leetcode.com/problems/maximize-distance-to-closest-person/description/ In a row of  seats ,  1  represents a person sitting in that seat, and  0  represents that the seat is empty.  There is at least one empty seat, and at least one person sitting. Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized.  Return that maximum distance to closest person. Example 1: Input: [1,0,0,0,1,0,1] Output: 2 Explanation: If Alex sits in the second open seat (seats[2]), then the closest person has distance 2. If Alex sits in any other open seat, the closest person has distance 1. Thus, the maximum distance to the closest person is 2. Example 2: Input: [1,0,0,0] Output: 3 Explanation: If Alex sits in the last seat, the closest person is 3 seats away. This is the maximum distance possible, so the answer is 3. Note: 1 <= seats.length <= 20000 seats ...

Problem is here:  https://leetcode.com/problems/minimum-size-subarray-sum/description/ Given an array of  n  positive integers and a positive integer  s , find the minimal length of a  contiguous  subarray of which the sum ≥  s . If there isn't one, return 0 instead. Example:  Input: s = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: the subarray [4,3] has the minimal length under the problem constraint. Follow up: If you have figured out the  O ( n ) solution, try coding another solution of which the time complexity is  O ( n  log  n ).  Slightly different approach than the other DP solution, DP linear solution nevertheless. Keep track of the sum of all the elements up to index i (O(n)-space and O(n)-time). With that in hands, you'll have two pointers, one for the front one of the back. Using the sum array, you always check whether the two pointers meet the "s" criteria, if so check if the distance (fron...

One more problem that cab be solved using DP:  https://leetcode.com/problems/min-cost-climbing-stairs/description/ On a staircase, the  i -th step has some non-negative cost  cost[i]  assigned (0 indexed). Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1. Example 1: Input: cost = [10, 15, 20] Output: 15 Explanation: Cheapest is start on cost[1], pay that cost and go to the top. Example 2: Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] Output: 6 Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3]. Note: cost  will have a length in the range  [2, 1000] . Every  cost[i]  will be an integer in the range  [0, 999] . Same hints as seen before: looking for min/max, a "cost" function used as the weight, combinatorial is intractable. Solutio...

Problem is here:  https://leetcode.com/problems/binary-tree-maximum-path-sum/description/ Given a  non-empty  binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain  at least one node  and does not need to go through the root. Example 1: Input: [1,2,3] 1 / \ 2 3 Output: 6 Example 2: Input: [-10,9,20,null,null,15,7]   -10    / \   9   20     /  \     15   7 Output: 42 This is in essence a variation of the Largest Binary Search Tree problem previously discussed. The idea will be to do it in linear time via post-search traversal: at every node, compute the max sum ending at  that node and thru  that node. Once you do it for all trees in the left, and all trees in the right, the calculation for the curre...

Problem is here:  https://leetcode.com/problems/minimum-index-sum-of-two-lists/description/ Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings. You need to help them find out their  common interest  with the  least list index sum . If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer. Example 1: Input: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"] Output: ["Shogun"] Explanation: The only restaurant they both like is "Shogun". Example 2: Input: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["KFC", "Shogun", "Burger King"] Output: ["Shogun"]...

Problem is here:  https://leetcode.com/problems/minimum-time-difference/description/ Given a list of 24-hour clock time points in "Hour:Minutes" format, find the minimum  minutes  difference between any two time points in the list. Example 1: Input: ["23:59","00:00"] Output: 1 Note: The number of time points in the given list is at least 2 and won't exceed 20000. The input time is legal and ranges from 00:00 to 23:59. Despite being a medium-complexity problem, there is a way to do it in linear time using concepts of DP: Basically the input range is very small: it fits into a 1500 array Create a bool array of this size and map each time to it If the time has already been set, return 0 (that's the min) This cost linear time and constant space (O(1500)) Next traverse the array and compare the two adjacent cells that have a time on it Some extra check is needed for the boundary case when the min diff crosses the day line That...

Very similar problem to the previous post, with a similar DP solution:  https://leetcode.com/problems/minimum-falling-path-sum/description/ Given a  square  array of integers  A , we want the  minimum  sum of a  falling path  through  A . A falling path starts at any element in the first row, and chooses one element from each row.  The next row's choice must be in a column that is different from the previous row's column by at most one. Example 1: Input: [[1,2,3],[4,5,6],[7,8,9]] Output: 12 Explanation: The possible falling paths are: [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9] [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9] [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9] The falling path with the smallest sum is  [1,4,7] , so the answer is  12 . Note: 1 <= A.length == A[0].length <= 100 -100 <= A[i][j] <= 100 Same hints as before: minimum (or maximum) ask, highly exponent...