- Find third max in linear time.
LeetCode – 561 : Array Partition I
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Example 1:
Input: [1,4,3,2] Output: 4 Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
Note:
- n is a positive integer, which is in the range of [1, 10000].
- All the integers in the array will be in the range of [-10000, 10000].
Idea – 1
The maximum element will not contribute towards the sum. The best pairing with the max elements will be with the second max. Once this pair is determined, we keep doing the same for the array of size n-2. We sort. Time complexity
and space complexity 
.
[code lang="java"]
class Solution {
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int sum = 0;
for(int i = 0; i < n; i += 2)
{
sum += nums[i];
}
return sum;
}
}
[code]
Runtime: 14 ms, faster than 92.53% of Java online submissions for Array Partition I.Memory Usage: 39.3 MB, less than 99.91% of Java online submissions for Array Partition I.
LeetCode – 269 : Alien Dictionary
There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
Example 1:
Input:
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
Output: "wertf"
Example 2:
Input:
[
"z",
"x"
]
Output: "zx"
Example 3:
Input: [ "z", "x", "z" ] Output:""Explanation: The order is invalid, so return"".
Note:
- You may assume all letters are in lowercase.
- You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
- If the order is invalid, return an empty string.
- There may be multiple valid order of letters, return any one of them is fine.
[code lang="java"]
class Solution {
public String alienOrder(String[] words) {
}
}
[code]
Idea – 1
Since words are lexicographically sorted, if two consecutive words, word1 and word2 (word1 < word2) first differ in the i-th letter, we have an ordering between the two letters like: word1.charAt(i) < word2.charAt(i). We can thus build a directed graph where nodes are the distinct letters in the given list of words and an edge nodeA -> nodeB exists if nodeA’s letter < nodeB’s letter (found from the earlier rule). For the first example the graph would look like:
. The size of the graph would also be .
Note – 1
Between two consecutive words after the letter where they mismatch, the ordering between rest of the letters cannot be determined, so we can stop processing there.Note – 2
Between three consecutive words we only need to compare word1 with word2 and word2 with word3 – we do not need to compare word1 with word3. In scenario1 no new information comes from comparing word1 with word3. And scenario2 is illegal, because word3 would be closer to word1 than word2.
[code lang="java"]
class Solution {
public String alienOrder(String[] words) {
Digraph g = new Digraph(words);
for(int i = 0; i < words.length-1; ++i)
{
String current = words[i];
String next = words[i+1];
int max = Math.min(current.length(), next.length());
int j = 0;
while(j < max)
{
if(current.charAt(j) != next.charAt(j))
{
break;
}
++j;
}
if(j < max)
{
g.addEdge(current.charAt(j), next.charAt(j));
}
}
StringBuilder order = new StringBuilder();
for(char c : g.getTopologicalOrder())
{
order.append(c);
}
return order.toString();
}
}
class Digraph
{
HashMap<Character, HashSet<Character>> adjacencyList;
LinkedList<Character> topologicalOrder;
HashSet<Character> visited;
HashSet<Character> active;
boolean hasCycle;
public Digraph(String[] words)
{
adjacencyList = new HashMap<>();
for(String w : words)
{
for(int i = 0; i < w.length(); ++i)
{
char c = w.charAt(i);
adjacencyList.putIfAbsent(c, new HashSet<>());
}
}
visited = new HashSet<>();
active = new HashSet<>();
}
public void addEdge(char u, char v)
{
adjacencyList.get(u).add(v);
}
public List<Character> getTopologicalOrder()
{
if(hasCycle)
{
return new LinkedList<>();
}
if(topologicalOrder != null)
{
return topologicalOrder;
}
topologicalOrder = new LinkedList<>();
for(char v : adjacencyList.keySet())
{
if(!hasCycle && !visited.contains(v))
{
dfs(v);
}
}
if(hasCycle)
{
return new LinkedList<>();
}
return topologicalOrder;
}
private void dfs(char v)
{
visited.add(v);
active.add(v);
for(char w : adjacencyList.get(v))
{
if(!visited.contains(w))
{
dfs(w);
}
else if(active.contains(w))
{
hasCycle = true;
return;
}
}
active.remove(v);
topologicalOrder.addFirst(v);
}
}
[code]
Runtime: 4 ms, faster than 73.13% of Java online submissions for Alien Dictionary.Memory Usage: 34.9 MB, less than 93.91% of Java online submissions for Alien Dictionary.
LeetCode – 76 : Minimum Window Substring
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example:
Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"
Note:
- If there is no such window in S that covers all characters in T, return the empty string
"". - If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
Idea – 1
Say a window [0, j) of s is the minimum among all windows that starts at 0 and has all chars of t by the required counts. In the example, [0, 6) is this window. Now we try to shrink (left-to-right) this window as much as possible, when we cannot shrink it anymore i.e. shrinking one more char would drop count of some t-char too low, we have found the optimal window that ends at j-1. Now we drop one char and becomes one char short. Now we expand j rightwards to find that dropped char which would make the window contain all t-chars once more. We repeat this shrink-expand. If length of s is n and length of t is m, time complexity is
and space complexity is 
.
[code lang="java"]
class Solution {
public String minWindow(String s, String t) {
HashMap<Character, Integer> tmap = new HashMap<>();
for(int i = 0; i < t.length(); ++i)
{
char tc = t.charAt(i);
tmap.put(tc, tmap.getOrDefault(tc, 0)+1);
}
int targetSize = t.length();
// initialize window with at least all chars of t
// window can have more of some t-chars than is required
HashMap<Character, Integer> window = new HashMap<>();
int j = 0;
while(j < s.length() && targetSize > 0)
{
char sc = s.charAt(j);
if(tmap.containsKey(sc))
{
if(window.getOrDefault(sc, 0) < tmap.get(sc))
{
--targetSize;
}
window.put( sc, window.getOrDefault(sc, 0)+1 );
}
++j;
}
if(targetSize > 0)
{
return "";
}
int i = 0;
int minstart = i, minend = j;
while(true)
{
// try shrinking window as much as possible
Character skipped = null;
while(i < j)
{
char ic = s.charAt(i);
// either ic is not in t or window has extra so we can shrink
if(tmap.containsKey(ic) && tmap.get(ic) < window.get(ic))
{
window.put(ic, window.get(ic)-1);
}
else if(tmap.containsKey(ic)) // in window count of ic is at the edge
{
window.put(ic, window.get(ic)-1);
// expand should regain skipped
skipped = ic;
// is this a better solution
if(minend-minstart+1 > j-i+1)
{
minstart = i;
minend = j;
}
// skip and start expansion
++i;
break;
}
++i;
}
// all (t-)chars in window were required
// so window is already optimal
if(skipped == null)
{
break;
}
// expand until window regain skipped
while(j < s.length() && s.charAt(j) != skipped)
{
if(tmap.containsKey(s.charAt(j)))
{
window.put(s.charAt(j), window.get(s.charAt(j))+1);
}
++j;
}
// could not find skipped through expansion
if(j == s.length())
{
break;
}
// establish window [i, j)
++j;
// skipped is included in the window, go to shrink
window.put(skipped, window.get(skipped)+1);
}
return s.substring(minstart, minend);
}
}
[code]
LeetCode – 98 : Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
Example 1:
2 / \ 1 3 Input: [2,1,3] Output: true
Example 2:
5 / \ 1 4 / \ 3 6 Input: [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.
[code lang="java"]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
}
}
[code]
Idea – 1
val of every node must be within a range. For any bst , root's val must be in
. Root's left child’s value must be in 
. Root's right child's val must be in 
. We apply this check recursively for each node. For an n-node bst, the time complexity is and average recursion-stack depth is 
.
[code lang="java"]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
private boolean isValidBST(TreeNode x, Integer min, Integer max)
{
if(x == null)
{
return true;
}
boolean biggerThanMin = (min == null) || (min < x.val);
boolean smallerThanMax = (max == null) || (x.val < max);
return biggerThanMin
&& smallerThanMax
&& isValidBST(x.left, min, x.val)
&& isValidBST(x.right, x.val, max);
}
}
[code]
Runtime: 0 ms, faster than 100.00% of Java online submissions for Validate Binary Search Tree.Memory Usage: 37.8 MB, less than 94.08% of Java online submissions for Validate Binary Search Tree.
Idea – 2
Instead of putting pressure on thread's stack space (through recursion), we could use an explicit (heap-allocated) stack and do it iteratively. Asymptotic complexities remain unchanged.
[code lang="java"]
class Solution {
class StackItem
{
TreeNode x;
Integer min;
Integer max;
public StackItem(TreeNode x, Integer min, Integer max)
{
this.x = x;
this.min = min;
this.max = max;
}
public boolean biggerThanMin()
{
return (this.min == null) || (x.val > this.min);
}
public boolean smallerThanMax()
{
return (this.max == null) || (x.val < this.max);
}
}
public boolean isValidBST(TreeNode root) {
if(root == null)
{
return true;
}
Deque<StackItem> stack = new ArrayDeque<>();
stack.addLast( new StackItem(root, null, null) );
while(!stack.isEmpty())
{
StackItem top = stack.removeLast();
if(!top.biggerThanMin() || !top.smallerThanMax())
{
return false;
}
if(top.x.left != null)
{
stack.addLast( new StackItem(top.x.left, top.min, top.x.val) );
}
if(top.x.right != null)
{
stack.addLast( new StackItem(top.x.right, top.x.val, top.max) );
}
}
return true;
}
}
[code]
Runtime: 2 ms, faster than 23.79% of Java online submissions for Validate Binary Search Tree.Memory Usage: 38.6 MB, less than 76.26% of Java online submissions for Validate Binary Search Tree.
LeetCode – 528 : Random Pick with Weight
Given an array w of positive integers, where w[i] describes the weight of index i, write a functionpickIndex which randomly picks an index in proportion to its weight.
Note:
1 <= w.length <= 100001 <= w[i] <= 10^5pickIndexwill be called at most10000times.
Example 1:
Input: ["Solution","pickIndex"] [[[1]],[]] Output: [null,0]
Example 2:
Input: ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[1,3]],[],[],[],[],[]] Output: [null,0,1,1,1,0]
Explanation of Input Syntax:
The input is two lists: the subroutines called and their arguments. Solution‘s constructor has one argument, the array w. pickIndex has no arguments. Arguments are always wrapped with a list, even if there aren’t any.
[code lang="java"]
class Solution {
public Solution(int[] w) {
}
public int pickIndex() {
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(w);
* int param_1 = obj.pickIndex();
*/
[code]
Idea – 1
Consider the sequence
, here at indices 0, 1, 2, and 3 we have weights 1, 3, 2, and 4. Thus 10% of the time we must pick index 0, 30% of the time we must pick index 1, 20% of the time we must pick index 2, and 40% of the time we must pick index 3. For our example totalWeight = 1+3+2+4 = 10. We divide the total weight like: [1, 1], [2, 4], [5, 6], and [7, 10]. Now if we draw x from [1..10] at random, we pick 0 if x is in [1, 1], we pick 1 if x is in [2, 4] etc. So we pick an index proportionally to its weight. Time complexity is 
, space complexity is .
[code lang="java"]
class Solution {
private static final Random rng = new Random(System.currentTimeMillis()%Integer.MAX_VALUE);
private int totalWeight = 0;
private int[] weights;
public Solution(int[] w) {
for(int x : w)
{
totalWeight += x;
}
weights = w;
}
public int pickIndex() {
int x = 1+rng.nextInt(totalWeight);
int cumsum = 0;
for(int i = 0; i < weights.length; ++i)
{
cumsum += weights[i];
if(x <= cumsum)
{
return i;
}
}
return -1;
}
}
[code]
Runtime: 90 ms, faster than 13.88% of Java online submissions for Random Pick with Weight.Memory Usage: 52 MB, less than 35.80% of Java online submissions for Random Pick with Weight.
Idea – 2
If we precompute the cumsum, we can dispense with the summing in pickIndex. Time complexity remains same, space complexity becomes.
[code lang="java"]
class Solution {
private static final Random rng = new Random(System.currentTimeMillis()%Integer.MAX_VALUE);
private int[] cumsum;
public Solution(int[] w) {
cumsum = new int[w.length];
cumsum[0] = w[0];
for(int i = 1; i < w.length; ++i)
{
cumsum[i] = cumsum[i-1] + w[i];
}
}
public int pickIndex() {
int x = 1+rng.nextInt(cumsum[cumsum.length-1]);
for(int i = 0; i < cumsum.length; ++i)
{
if(x <= cumsum[i])
{
return i;
}
}
return -1;
}
}
[code]
Runtime: 80 ms, faster than 27.95% of Java online submissions for Random Pick with Weight.Memory Usage: 52.5 MB, less than 34.07% of Java online submissions for Random Pick with Weight.
Idea – 3
Since cumsum is sorted, we could leverage binary search in pickIndex which reduces time complexity to, space complexity remains .
[code lang="java"]
class Solution {
private static final Random rng = new Random(System.currentTimeMillis()%Integer.MAX_VALUE);
private int[] cumsum;
public Solution(int[] w) {
cumsum = new int[w.length];
cumsum[0] = w[0];
for(int i = 1; i < w.length; ++i)
{
cumsum[i] = cumsum[i-1] + w[i];
}
}
public int pickIndex() {
int x = 1+rng.nextInt(cumsum[cumsum.length-1]);
return ceilSearch(cumsum, x);
}
private int ceilSearch(int[] A, int key)
{
int lo = 0, hi = A.length-1;
while(lo <= hi)
{
int mid = lo+(hi-lo)/2;
if(key == A[mid])
{
return mid;
}
else if(key < A[mid])
{
hi = mid-1;
}
else
{
lo = mid+1;
}
}
return lo;
}
}
[code]
Runtime: 67 ms, faster than 92.00% of Java online submissions for Random Pick with Weight.Memory Usage: 44.3 MB, less than 95.91% of Java online submissions for Random Pick with Weight.
LeetCode – 88 : Merge Sorted Array
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
- The number of elements initialized in nums1 and nums2 are m and n respectively.
- You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
Example:
Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6]
[code lang="java"]
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
}
}
[code]
Idea – 1
We start with m-1 th and n-1 th elements from nums1 and nums2, whichever is bigger (say nums2) we put that at m+n-1 th place of nums1 and move leftwards in nums2. If we are done processing nums2, we are done. If we are done with nums1 elements, we copy rest of nums2 to the places left in nums1. Time complexity is
and space complexity is .
[code lang="java"]
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m-1, j = n-1;
int k = m+n-1;
while(i >= 0 || j >= 0)
{
if(j < 0)
{
break;
}
else if(i < 0 || nums2[j] >= nums1[i])
{
nums1[k--] = nums2[j--];
}
else
{
nums1[k--] = nums1[i--];
}
}
}
}
[code]
Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Sorted Array.Memory Usage: 35.5 MB, less than 99.61% of Java online submissions for Merge Sorted Array.
LeetCode – 344 : Reverse String
Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.
Example 1:
Input: ["h","e","l","l","o"] Output: ["o","l","l","e","h"]
Example 2:
Input: ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]
[code lang="java"]
class Solution {
public void reverseString(char[] s) {
}
}
[code]
Idea – 1
We swap the two ends and move inwards. Now we have n-2 characters to reverse, we do this repeatedly. Time complexity, space complexity .
[code lang="java"]
class Solution {
public void reverseString(char[] s) {
if(s == null || s.length < 2)
{
return;
}
int i = 0, j = s.length-1;
while(i < j)
{
swap(s, i++, j--);
}
}
private void swap(char[] A, int i, int j)
{
char tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
}
[code]
Runtime: 1 ms, faster than 100.00% of Java online submissions for Reverse String.Memory Usage: 47.4 MB, less than 64.05% of Java online submissions for Reverse String.
LeetCode – 347 : Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]
Example 2:
Input: nums = [1], k = 1 Output: [1]
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.
[code lang="java"]
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
}
}
[code]
Idea – 1
We use a hash map to save the frequency of each element. Next we put the keys in a min heap of size k (whenever the heap becomes bigger than k we throw away top which is the least frequent element). At the end we have k most frequent elements in the heap. Time complexity is
and space complexity is .
[code lang="java"]
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer> ans = new ArrayList<>();
int n = nums.length;
HashMap<Integer, Integer> map = new HashMap<>();
for(int x : nums)
{
map.put( x, map.getOrDefault(x, 0)+1 );
}
PriorityQueue<Integer> minq = new PriorityQueue<>( (a, b) -> ( map.get(a)-map.get(b) ) );
for(int key : map.keySet())
{
minq.offer(key);
if(minq.size() > k)
{
minq.poll();
}
}
while(!minq.isEmpty())
{
ans.add(minq.poll());
}
return ans;
}
}
[code]
Runtime: 42 ms, faster than 42.71% of Java online submissions for Top K Frequent Elements.Memory Usage: 39.1 MB, less than 65.70% of Java online submissions for Top K Frequent Elements.
LeetCode – 17 : Letter Combinations of a Phone Number
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:
Input: "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
[code lang="java"]
class Solution {
public List<String> letterCombinations(String digits) {
}
}
[code]
Idea – 1
If there are n digits each having m possible substitutions, there are
combinations in total. We generate each through dfs. Time complexity is 
and space complexity due to recursion stack (excluding output size) is .
[code lang="java"]
class Solution {
private static final String[] map =
{
"",
"",
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz" // 9
};
public List<String> letterCombinations(String digits) {
List<String> ans = new ArrayList<>();
if(digits.isEmpty())
{
return ans;
}
collect(digits, 0, "", ans);
return ans;
}
private void collect(String digits, int i, String buffer, List<String> ans)
{
if(i >= digits.length())
{
ans.add(buffer);
return;
}
char c = digits.charAt(i);
String subst = map[c-'0'];
for(int j = 0; j < subst.length(); ++j)
{
collect(digits, i+1, buffer+subst.charAt(j), ans);
}
}
}
[code]
Runtime: 0 ms, faster than 100.00% of Java online submissions for Letter Combinations of a Phone Number.Memory Usage: 35.1 MB, less than 98.08% of Java online submissions for Letter Combinations of a Phone Number.
programmingpuzzles 