Boyer-Moore Voting algorithm. Current will contribute to a candidate’s count if the same as the candidate, otherwise, it deduce counts for all current candidates. Majority Element Given an array, return the majority element, which is defined as the element that exists more than floor(nums.lengh/2) number of times. Solve it using Boyer-Moore Algorithm. The ideas is […]
These kind of problems normally involves given an array of “bars”, and need to calculate certain areas, i.e. rectangle area or amount of trapped water. Solve these type of problems using Increasing/Decreasing Stack Framework. Store index in a stack and maintaining increasing/decreasing property. Increasing Stack: Short bar clears long bars from the stack. Long bar […]
Use backtracking to solve this class of problems including subsets, permutations, combinations, etc. Core idea is summarized here. Subsets (Naive) Given an integer array of distinct integers, find all possible subsets of the input array. Cannot have duplicates. Walk through the input. For each iteration, duplicate the current result list and insert them back. At […]
Here are two options of doing merge sort on an array. Traditional Merge Sort This is the traditional approach to merge sort. The idea is to have three pointers i, j, k which points to array1, array2, and result array respective. Each time insert the smaller number pointed by the pointer into the result and […]
Map map.getOrDefault(key, defaultValue); Return defaultValue if key does not exist in the map; This can be useful to avoid cumbersome of key checking in the map; Char cannot used as a type in map. Needs to be Character. Remove an entry from the map: m.remove(key); Character Convert to lower case: Character.toLowerCase(c) Check alphanumerical: Character.isLetter(c) Character.isDigit(c) […]
Binary Index Tree, also known as Partial Sum Tree, is a array based data structure that is good for getting prefix sum and update the array both in O(logN) time. Binary Index Tree Tutorial 1 Binary Index Tree Tutorial 2 The core idea is that y is x’s parent (y –> x). Unset last bit […]
How to remove the last set bit? n & (n – 1) Example: 12 is 1100. (1100) & (1100 – 1) –> (1100) & (1011) –> 1000 (8), where last set bit is cleared. It can be used to find parent i.e. in binary index tree. (8 is parent of 12) How to set the […]
Union find algorithm can Tells which subset an element is in; Join two subsets; When join, either one can be the other’s parent. (Graph can be undirected). Union: O(1); Find: O(n); Valid Graph Tree (Union-Find Solution) Given a undirected graph represented as a list of edges, determine whether the graph is a valid tree, a.k.a, […]
Consider use Trie when: – An efficient data structure to store a dictionary cause prefixes (or suffix) are collapsed; – Can make EARLY decision based on prefix or suffix, i.e. K edit distance problem, word search II; This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To […]
bilbo3000.wordpress.com 