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.
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.
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:
A topological sort order of the vertices in this graph will give the required ordering of the letters. If a cycle is found, there is no valid ordering. If there are n words with longest having length m, constructing the graph and doing topological sort both would require time . 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.
and space complexity 
.
. The size of the graph would also be 
programmingpuzzles 