Another Casual Coder

Problem:  https://leetcode.com/problems/minimum-moves-to-equal-array-elements/ , or copied/pasted here: Given a  non-empty  integer array of size  n , find the minimum number of moves required to make all array elements equal, where a move is incrementing  n  - 1 elements by 1. Example: Input: [1,2,3] Output: 3 Explanation: Only three moves are needed (remember each move increments two elements): [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4] This is an interesting problem that can be solved more simplistically than the problem suggests. Don't try to follow the strategy implied by the problem description - it is misleading and will make your code convoluted and inefficient. Here are few insights that will lead to a 3-liner solution: Insight 1 : when the problem says "incrementing n-1 elements by 1", notice that this is the same as saying "decrementing 1 element by 1". If you're increasing n-1 elements by 1 (meaning increasing all bu...

https://leetcode.com/problems/path-sum-iii/ , which for reference, here it is: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes). The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.  I decided to go with an O(n^2) solution given n=1000. Idea is to build an inner method that checks all the solutions given a certain node (that's the private method below), which runs in O(n). For each node in the tree, call the inner method passing the current node as the "root", making it O(n^2).   Still fast compared to the other submissions - code's down below, thanks! Marcelo. /**  * Definition for a binary tree node.  * public class TreeNode {  *     public int val;  *     public...

This one was a little more sophisticated, but still marked by LeetCode as an easy category problem. Here it is:  https://leetcode.com/problems/binary-watch/ . The goal is, given a number of potential lights to be on in the following binary watch, list all the possible hours it can give. Problem will be split primarily into two parts: Part 1 : model a configuration for the clock. In my case I decided to model it as one string with 10 chars, with 0s (off) or 1s (on), the first 4 chars indicating the hour, the last 6 the minutes. Hence for the config in the picture the string would then be "0011011001". Write a method to determine the time given a single  config. The method is basically a base-conversion algorithm from base-2 to base-10 with some minor (albeit important) caveats along the way. But that's primarily what part 1 does: a base conversion. Part 2 : do a DFS (depth-first-search) generating all the possible values of config, turning on the bits whenever do...

Another one from LeetCode (I'm impressed by how well and fast their site works!): https://leetcode.com/problems/intersection-of-two-arrays-ii/ . Here it is: Given two arrays, write a function to compute their intersection. Example: Given   nums1   =   [1, 2, 2, 1] ,   nums2   =   [2, 2] , return   [2, 2] . We'll be optimizing for speed not necessarily space. The goal is to write an algorithm in O(len(nums1) + len(nums2)) with small constant. Here is the approach: Use a hashTable and insert all the elements of nums1 into it Keep the value of each key as the number of instances of that key seen Have another hashTable which will store the overlapped elements Go thru the second array nums2 and whenever you see a match in the first hashTable, then Add the match to the overlapped hashTable Keep track of the number of elements added Reduce the count of elements in the first hashTable.  Whenever that count hits zero, remove it from...

This problem by LeetCode is a good candidate to exemplify a method to convert a recursive function to non-recursive one. Problem is this:  https://leetcode.com/problems/sum-of-left-leaves/ , or copied/pasted here: " Find the sum of all left leaves in a given binary tree. ". Recursively one can solve this problem easily in 3 lines of code:         public int SumOfLeftLeaves(TreeNode root)         {             if (root == null) return 0; //Line 1             if (root.left != null && root.left.left == null && root.left.right == null) return root.left.val + SumOfLeftLeaves(root.right);  //Line 2             return SumOfLeftLeaves(root.left) + SumOfLeftLeaves(root.right);  //Line 3         } In essence the first line is the base case (no tree, no sum), the second line is the processing on the current...

Recently I saw a very nice interview question: given two strings, can you tell quickly whether they differ by no more than one character? The two-pointers approach works well for this question. However, when we expand the problem to ask "do two given strings differ by no more than N characters?" then it becomes problematic with the two-pointers approach. The problem is that for a case like this one: String 1: abc8 String 2: a123456bc7 N: 8 The answer is "yes", because you can remove all the numbers (8 numbers in total) and the two remaining strings will match. But if you're operating with pointers then when you get to the first mismatched element ('b' and '1') which pointers do you move? The first, second, or both? If you go this route recursively chances are you'll end up with an exponential solution. One way to solve this problem is using Dynamic Programming . The idea requires solving the problem for smaller strings and use that...

The game of Tic-Tac-Toe  has been played billions of times and has been around for thousands of years. There is a well-defined strategy to win the game 100% of the time - it is there in the Wiki. But there is a simpler strategy that can guarantee you (or a computer) victory in 99% of the cases (well, victory + draws in 99% of the time). Without further due, here is the proposed algorithm: 1) If the computer can win in the next move, then: win! 2) If the human can win in the next move, then: computer blocks it! 3) If the center hasn't been played yet: computer plays the center! 4) If the diagonals are open: computer plays them randomly! 5) Computer keeps track of its last move: plays as far away as possible! As you can see, 1-2-3 are straightforward moves and super easy to implement. 4 is not as simple as there is a variant (see code for more info). The case number 5 is actually simple to implement: keep track of the last move played, and then try to play a move from the far...