Another Casual Coder

https://leetcode.com/problems/subsets-ii/ , problem statement: Given a collection of integers that might contain duplicates,  nums , return all possible subsets. Note:  The solution set must not contain duplicate subsets. For example, If  nums  =  [1,2,2] , a solution is: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] I've posted before a trick to generate subsets of a set non-recursively by using bit math, you can read the post here:  https://anothercasualcoder.blogspot.com/2014/10/a-non-recursive-trick-for-subsets.html . Technique to solve this problem is exactly the same with two caveats: First sort the input array so that the key generation for the hash table becomes unique Then keep track of the solutions already seen using a hash table Complexity is still O(2^n) (actually nlog + 2^n). Beats more than half of the C# submissions. Code is down below, cheers, Marcelo. Code:     public class Solution ...

https://leetcode.com/problems/valid-perfect-square/ , problem statement: Given a positive integer  num , write a function which returns True if  num  is a perfect square else False. Note:   Do not  use any built-in library function such as  sqrt . Example 1: Input: 16 Returns: True Example 2: Input: 14 Returns: False Straightforward binary search from 1 to Int32.MaxValue (2147483647) which gives an O-time of Log(2147483647), also known as 31. Code below: using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Numerics; using System.Text; using System.Threading.Tasks; using System.IO; namespace LeetCode {     class Program     {         static void Main(string[] args)         {             Solution sol = new Solution();             Console.WriteLine(sol.IsPer...

https://leetcode.com/problems/combination-sum/ , problem statement: Given a  set  of candidate numbers ( C )  (without duplicates)  and a target number ( T ), find all unique combinations in  C  where the candidate numbers sums to  T . The  same  repeated number may be chosen from  C  unlimited number of times. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set  [2, 3, 6, 7]  and target  7 ,  A solution set is:  [ [7], [2, 2, 3] ] The strategy to be used here will be recursion + backtracking  + tree pruning, although the pruning done here is far from being the most efficient one. In a nutshell here is the logic: The recursion will take as input: The current index of the set The set itself The current sum thus far The current list The target number The solution list...

https://leetcode.com/problems/house-robber-iii/ , problem statement: The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night. Determine the maximum amount of money the thief can rob tonight without alerting the police. Example 1: 3 / \ 2 3 \ \ 3 1 Maximum amount of money the thief can rob =  3  +  3  +  1  =  7 . Example 2: 3 / \ 4 5 / \ \ 1 3 1 Maximum amount of money the thief can rob =  4  +  5  =  9 . Key idea is to do a DFS (Depth-First-Search) but using post-order traversal (left-right-current). Whenever the current node can b...

https://leetcode.com/problems/combination-sum-iv/ , description of the problem: Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target. Example: nums = [1, 2, 3] target = 4 The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) Note that different sequences are counted as different combinations. Therefore the output is 7 . Definitely a brute-force approach is exponential and won't work for large target numbers. Since the problem statement is asking only for the number of combinations (not actually the combinations themselves), then Dynamic Programming (DP) comes to mind as a plausible tool. The DP code to solve this problem is very short, but the key is to grasp the idea behind it, which is usually not that straightforward. Here is the idea: instead of solving the problem for the "target" number, let's try to solve it...

https://leetcode.com/problems/decode-string/ , this problem looked much simpler than it actually was. Code wise it was not that complicated, but it turned out being a fairly "special case" code with many different conditions being handled. It was neither a linear straightforward string manipulation solution, nor a base-case-induction stack-based one. It was a hybrid, which made the code hard to follow IMO. Here is the problem: Given an encoded string, return it's decoded string. The encoding rule is:  k[encoded_string] , where the  encoded_string  inside the square brackets is being repeated exactly  k  times. Note that  k  is guaranteed to be a positive integer. You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers,  k . For example, there won't be ...

https://leetcode.com/problems/4sum-ii/ , here is the problem copied/pasted for easy access: Given four lists A, B, C, D of integer values, compute how many tuples  (i, j, k, l)  there are such that  A[i] + B[j] + C[k] + D[l]  is zero. To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -2 28  to 2 28  - 1 and the result is guaranteed to be at most 2 31  - 1. Example: Input: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] Output: 2 Explanation: The two tuples are: 1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0 2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0 With the input in the N=500 range, it is clear that an N^4 solution won't work (62,500,000,000) or even an N^3 solution would take some non-negligible time (125,000,000). The goal is to try to come up with something better: an N^2 solution might do the trick here (250,...

https://leetcode.com/problems/combination-sum-iii/ , here is the problem definition: Find all possible combinations of  k  numbers that add up to a number  n , given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Example 1: Input:  k  = 3,  n  = 7 Output: [[1,2,4]] Example 2: Input:  k  = 3,  n  = 9 Output: [[1,2,6], [1,3,5], [2,3,4]] The solution is a DFS (Depth-First-Search), cutting down the combinations by trimming the search in the base case (no need to go further past k, or when the sum is past n). It is a standard base-case-induction-case algorithm. Some nuances of the language to be aware of: for instance the line in bold is necessary 'cause if you try to add "currentSet" to the solution it will be empty since it is being operated by reference rather than by value. The solution isn't that fast, only beating 60% of the c# submissions. There are pr...

https://leetcode.com/problems/top-k-frequent-elements/ : Given a non-empty array of integers, return the  k  most frequent elements. For example, Given  [1,1,1,2,2,3]  and k = 2, return  [1,2] . Note:  You may assume  k  is always valid, 1 ≤  k  ≤ number of unique elements. Your algorithm's time complexity  must be  better than O( n  log  n ), where  n  is the array's size. Subscribe  to see which companies asked this question Hide Tags   Hash Table   Heap Show Similar Problems I did look at the hints for this problem, which suggested "Hash Tables" and "Heaps". With that information in mind then the solution becomes:  - Create a class that implements a heap. In my case I had a Priority Queue class, which should do the trick  - Add all the elements in the array to a hash table (add the count of elements to the hash table) ...