Another Casual Coder

Here is the problem, by Leetcode. First try to think of the brute-force approach.  https://leetcode.com/problems/integer-break/description/ Given a positive integer  n , break it into the sum of  at least  two positive integers and maximize the product of those integers. Return the maximum product you can get. Example 1: Input: 2 Output: 1 Explanation: 2 = 1 + 1, 1 × 1 = 1. Example 2: Input: 10 Output: 36 Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36. Note : You may assume that  n  is not less than 2 and not larger than 58. The brute-force will certainly be exponential. This problem is screaming for a DP solution, but coming up with exactly the "formula" for it is the challenge. Here is the way that I thought about the problem: as always, DP will be a construction approach, hence we'll build the solution for 1, 2, 3, ...., all the way to N, in our case N <= 58. Let's focus on a certain number N. One possibility is clear: the...

Problem is this:  https://leetcode.com/problems/largest-perimeter-triangle/description/ Given an array  A  of positive lengths, return the largest perimeter of a triangle with  non-zero area , formed from 3 of these lengths. If it is impossible to form any triangle of non-zero area, return  0 . Example 1: Input: [2,1,2] Output: 5 Example 2: Input: [1,2,1] Output: 0 Example 3: Input: [3,2,3,4] Output: 10 Example 4: Input: [3,6,2,3] Output: 8 Note: 3 <= A.length <= 10000 1 <= A[i] <= 10^6 Remember that for a triangle to be valid with Area > 0, the following condition must be true: Side1 + Side2 > Side3 Notice that you can't use greater than or equal  since the equal means area = 0. The solution becomes straightforward if you sort the array: from largest to smallest, find the first triplet matching the aforementioned condition, and then you're done. Hence O(NLogN) in 4 lines of code . Tha...

A not so fun problem:  https://leetcode.com/problems/rotate-list/description/ Given a linked list, rotate the list to the right by  k  places, where  k  is non-negative. Example 1: Input: 1->2->3->4->5->NULL, k = 2 Output: 4->5->1->2->3->NULL Explanation: rotate 1 steps to the right: 5->1->2->3->4->NULL rotate 2 steps to the right: 4->5->1->2->3->NULL Example 2: Input: 0->1->2->NULL, k = 4 Output: 2->0->1->NULL Explanation: rotate 1 steps to the right: 2->0->1->NULL rotate 2 steps to the right: 1->2->0->NULL rotate 3 steps to the right:  0->1->2->NULL rotate 4 steps to the right:  2->0->1->NULL I'm doing it in 2n-time: I do count the number of elements in the list, use it to mod the k, and then do another loop to find the precise pointers to use to reshape the list. Some of the "off by one" calculations in problems ...

Love problems like this one:  https://leetcode.com/problems/minimum-distance-between-bst-nodes/description/ Given a Binary Search Tree (BST) with the root node  root , return the minimum difference between the values of any two different nodes in the tree. Example : Input: root = [4,2,6,1,3,null,null] Output: 1 Explanation: Note that root is a TreeNode object, not an array. The given tree [4,2,6,1,3,null,null] is represented by the following diagram: 4 / \ 2 6 / \ 1 3 while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2. Note: The size of the BST will be between 2 and  100 . The BST is always valid, each node's value is an integer, and each node's value is different. The key here is to remember that in a Binary Search Tree, the elements are sorted when you traverse it using in-order traversal . With this information in mind, it becomes tri...

More deceiving than it looks:  https://leetcode.com/problems/largest-time-for-given-digits/description/ Given an array of 4 digits, return the largest 24 hour time that can be made. The smallest 24 hour time is 00:00, and the largest is 23:59.  Starting from 00:00, a time is larger if more time has elapsed since midnight. Return the answer as a string of length 5.  If no valid time can be made, return an empty string. Example 1: Input: [1,2,3,4] Output: "23:41" Example 2: Input: [5,5,5,5] Output: "" One way is to use backtracking, here is the gist of it: First sort the array in descending order. This will guarantee that the first solution found is the optimal Backtrack it For each index from 0..3, you'll need to use different rules based on the time structure. For example, for position 0, it is only allowed to have digits 2..0. And so on As you backtrack, if you find a solution return Given the small size of the input (4), even the...

I was shocked when I looked at this problem on LeetCode today:  https://leetcode.com/problems/decode-ways/description/ We'll get back to the problem soon, but the shocking part wasn't so much that this is a medium-complexity dynamic programming problem, but rather it was this : Unless the site is lying or there is a bug somewhere, there have been over 1,000,000 submissions to this problem ! You see numbers of this magnitude on popular Instagram posts or popular silly (or professional) YouTube videos. But I'd never have imagined that an algorithm problem that if you try brute-force times out hence you want to use dynamic programming (memoization) to cut down the execution time to O(n)-time at the cost of an extra space of O(n) space complexity  would ever be something popular! Code is everything, it is everywhere, algorithms are the heart of this world and it is amazing to be leaving in such a revolutionary era where in the past 100 years everything has been trans...

Problem:  https://leetcode.com/problems/insert-into-a-binary-search-tree/description/ Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST. Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them. For example,  Given the tree: 4 / \ 2 7 / \ 1 3 And the value to insert: 5 You can return this binary search tree: 4 / \ 2 7 / \ / 1 3 5 This tree is also valid: 5 / \ 2 7 / \ 1 3 \ 4 Best is to traverse down the tree using the BST characteristic ("binary") which should take Log(N). When you hit a node for which the corresponding right or left ...

Problem:  https://leetcode.com/problems/count-complete-tree-nodes/description/ Given a  complete  binary tree, count the number of nodes. Note: Definition of a complete binary tree from  Wikipedia : In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2 h  nodes inclusive at the last level h. Example: Input: 1 / \ 2 3 / \ / 4 5 6 Output: 6 Not sure why this was flagged as medium... code is below, works fast. public class Solution { public int CountNodes(TreeNode root) { if(root==null) return 0; return 1 +CountNodes(root.left)+CountNodes(root.right); } }

Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01...

Question today comes from Daily Coding Problem, from Zillow: This question was asked by Zillow. You are given a 2-d matrix where each cell represents number of coins in that cell. Assuming we start at matrix[0][0], and can only move right or down, find the maximum number of coins you can collect by the bottom right corner. For example, in this matrix 0 3 1 1 2 0 0 4 1 5 3 1 The most we can collect is 0 + 2 + 1 + 5 + 3 + 1 = 12 coins. This is another typical DP problem: it will require O(n)-space to hold the best sums per cell, but the time complexity will be linear, that’s usually the trade-off. The analogy with recursion that I always like to use is to structure the code in terms of Base Case + Construction for DP, instead of Base Case + Induction for Recursion. The solution is in the bottom right corner cell. Works well, code is checked-in on Github ( https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem01142019.cs ) and down...

This is my 300th leetcode problem solved:  https://leetcode.com/problems/spiral-matrix-ii/description/ Given a positive integer  n , generate a square matrix filled with elements from 1 to  n 2  in spiral order. Example: Input: 3 Output: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] My approach is to have an outer loop going from the upper left corner towards the center of the matrix via the diagonal. This variable will control the beginning of the row/col being worked on. Inside the outer loop you will have 4 loops: left to right, top to bottom, right to left and finally bottom to top. You should also be careful to not add the corner elements twice. Call your variables "c" and "r" to facilitate the implementation (col and row). Just play with the indexes a bit, focus on the symmetry of the solution, and it should do it. Code is below - thanks, Marcelo. public class Solution { public int[,] GenerateMatrix(int n) { int[,] retVal = new int[n, ...

To exemplify the statement in the title, we'll tackle this problem:  https://leetcode.com/problems/majority-element-ii/ Given an integer array of size  n , find all elements that appear more than  ⌊ n/3 ⌋  times. Note:  The algorithm should run in linear time and in O(1) space. Example 1: Input: [3,2,3] Output: [3] Example 2: Input: [1,1,1,3,3,2,2,2] Output: [1,2] Many times when we see the "linear time" we tend to be obsessed with one-pass solution. One-pass solution is linear. But so is a two-passes solution. And so is a three-passes solution. In general, so it is a C-passes solution, where C is a constant. What this means is that you can have a linear-time solution by doing many passes in the input data structure, as long as the "many" is a constant number . The solution to the above problem then will make us of this C with C > 1. First, since we're looking for all the numbers that appear more than a 1/3 of the times, it mea...

Problem is here:  https://leetcode.com/problems/diameter-of-binary-tree/description/ Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the  longest  path between any two nodes in a tree. This path may or may not pass through the root. Example: Given a binary tree  1 / \ 2 3 / \ 4 5 Return  3 , which is the length of the path [4,2,1,3] or [5,2,1,3]. Note:  The length of path between two nodes is represented by the number of edges between them. If you know how to code the height of a binary tree, then you can solve this problem. Here is the gist of the problem: just think about solving the height of a binary tree problem, which is the classic post-order traversal example: Height(T)   T is null ==> 0   Else ==> Max(Height(T.L), Height(T.R)) + 1 The only difference is that along the ...

Problem is here:  https://leetcode.com/problems/sudoku-solver/description/ Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy  all of the following rules : Each of the digits  1-9  must occur exactly once in each row. Each of the digits  1-9  must occur exactly once in each column. Each of the the digits  1-9  must occur exactly once in each of the 9  3x3  sub-boxes of the grid. Empty cells are indicated by the character  '.' . A sudoku puzzle... ...and its solution numbers marked in red. Note: The given board contain only digits  1-9  and the character  '.' . You may assume that the given Sudoku puzzle will have a single unique solution. The given board size is always  9x9 . The solution is via backtracking with pruning. Basically it is important to understand that there is only one solution, hence the moment that...

Problem is here:  https://leetcode.com/problems/longest-increasing-subsequence/description/ : Given an unsorted array of integers, find the length of longest increasing subsequence. Example: Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101] , therefore the length is 4 . Note: There may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm should run in O( n 2 ) complexity. Follow up:  Could you improve it to O( n  log  n ) time complexity? The solution below is the N^2. Use DP for it: keep track of the best sequence for all elements 0..i-1 using O(n) space. Then it is an easy O(n) time check for element i. Code is below, cheers, Marcelo. public class Solution { public int LengthOfLIS(int[] nums) { if (nums == null || nums.Length == 0) return 0; int[] longest = new int[nums.Length]; int retVal = 1; longest[0] = 1; for (int i = 1; i...

Problem today comes from Daily Coding Problem: Good morning! Here's your coding interview problem for today. This problem was asked by Facebook. Given a binary tree, return all paths from the root to leaves. For example, given the tree 1 / \ 2 3 / \ 4 5 it should return [[1, 2], [1, 3, 4], [1, 3, 5]]. The recursive solution is relatively straightforward, so here I decided to do the non-recursive version of it. Sometimes it is important to implement the non-recursive solution in real application to avoid getting bounded by the stack memory limits, which in most languages is bounded at 1MB. The non-recursive solution I chose uses a Stack, but it could have been done in this case with a Queue too. Create a structure (class) holding a node and a path, push the root, when you pop check whether you're at a leaf node, if so add the current list to the return variable, and then push the children if they exist. Solves the problem well, code below, cheer...