# SE103 Week 2 Warm Up Solutions
[Find K Pairs with Smallest Sums](#Find-K-Pairs-with-Smallest-Sums)
[Happy Number](#Happy-Number)
[Isomorphic Strings](#Isomorphic-Strings)
[Jewels and Stones](#Jewels-and-Stones)
[Top K Frequent Words](#Top-K-Frequent-Words)

## Find K Pairs with Smallest Sums
**Java**

/*
Use min_heap to keep track on next minimum pair sum. We only need to maintain K
possible candidates in the data structure.
*/

public class Solution {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> que = new PriorityQueue<>(
          (a,b) -> a[0] + a[1] - b[0] - b[1]);
        List<int[]> res = new ArrayList<>();

        if (nums1.length == 0 || nums2.length == 0 || k == 0)
          return res;

        for (int i = 0; i < nums1.length && i < k; i++)
          que.offer(new int[]{nums1[i], nums2[0], 0});

        while(k-- > 0 && !que.isEmpty()) {
            int[] cur = que.poll();
            res.add(new int[]{cur[0], cur[1]});
            if(cur[2] == nums2.length - 1)
              continue;

            que.offer(new int[]{cur[0], nums2[cur[2] + 1], cur[2] + 1});
        }
        return res;
    }
}

**Python**

'''
The smallest pair is (0, 0). The next possible candiates for the smallest pair
is (i +1, j), and (i, j + 1). Visit them in the order of their sum with a min
heap.
'''
from heapq import *

class Solution:
    def kSmallestPairs(self, nums1, nums2, k):
        if not nums1 or not nums2:
            return []

        heap = [(nums1[0] + nums2[0], 0, 0)]
        visited = set()
        output = []

        while len(output) < k and heap:
            val = heappop(heap)
            output.append([nums1[val[1]], nums2[val[2]]])

            if val[1] < len(nums1) - 1 and (val[1] + 1, val[2]) not in visited:
                visited.add((val[1] + 1, val[2]))
                heappush(heap, (nums1[val[1] + 1] + nums2[val[2]], val[1] + 1, val[2]))
            if val[2] < len(nums2) - 1 and (val[1], val[2] + 1) not in visited:
                visited.add((val[1], val[2] + 1))
                heappush(heap, (nums1[val[1]] + nums2[val[2] + 1], val[1], val[2] + 1))

        return output

## Happy Number
**Java**

public class Solution {
    public boolean isHappy(int n) {
        if (n == 0) {
            return false;
        } else if (n == 1) {
            return true;
        }

        Set<Integer> hashSet = new HashSet<>();
        int sum = 0;
        while (true) {
            while (n > 0) {
                sum += (n % 10) * (n % 10);
                n /= 10;
            }
            if (sum == 1) {
                return true;
            } else {
                if (hashSet.contains(sum)) {
                    return false;
                } else {
                    hashSet.add(sum);
                }
            }
            n = sum;
            sum = 0;
        }
    }
}

**Python**

'''
After each interation, store the result if it is not equal to 1. Continue to
iterate and check if the new calculation equals 1. If it does not, check if the
current number was previously saved. If the number was not, add it. If it was,
return false, because we know we're in a cycle.
'''
def isHappy(self, n):
    mem = set()
    while n != 1:
        n = sum([int(i) ** 2 for i in str(n)])
        if n in mem:
            return False
        else:
            mem.add(n)
    else:
        return True

## Isomorphic Strings
**Java**

/*
Solution tries to map each s character to its equivalent t character. If the
given character has already been mapped to something else, the check fails.
*/
public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s == null || s.length()<= 1) return true;
        HashMap<Character, Character> map = new HashMap<Character, Character> ();
        for (int i = 0; i<s.length(); i++) {
            char a = s.charAt(i);
            char b = t.charAt(i);
            if (map.containsKey(a)) {
                if (map.get(a).equals(b))
                    continue;
                else
                    return false;
            } else {
                if (!map.containsValue(b))
                    map.put(a, b);
                else
                    return false;
            }
        }
        return true;
    }
}

**Python**

'''
Solution tries to map each s character to its equivalent t character. If the
given character has already been mapped to something else, the check fails.
'''
def isIsomorphic(self, s, t):
    if len(s) != len(t):
        return False
    else:
        mapping = {}
        for i in range(len(s)):
            if s[i] in mapping:
                if mapping[s[i]]!=t[i]:
                    return False
            else:
                if t[i] in mapping.values():
                    return False
                else:
                    mapping[s[i]] = t[i]
        return True

## Jewels and Stones
**Java**

public class Solution {
    public int numJewelsInStones(String J, String S) {
        Set<Character> jSet = new HashSet<>();
        for (Character ch: J.toCharArray()) {
            jSet.add(ch);
        }
        int count = 0;
        for (Character ch: S.toCharArray()) {
            if (jSet.contains(ch)) {
                count++;
            }
        }
        return count;
    }
}

**Python**

'''
For each stone, check if it's a jewel. Count the number of jewels we find.
'''
def numJewelsInStones(self, J, S):
    counts = []
    for c in S:
        if c in J:
            counts.append(c)
    return len(counts)

## Top K Frequent Words
**Java**

/*
  Keep a count of each word in a HashMap and then insert in a Priority Queue.
  While inserting in pq, if the count of two words is same, 
  insert based on string compare of the keys.
*/

public class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        List<String> result = new LinkedList<>();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i<words.length; i++) {
            if (map.containsKey(words[i]))
                map.put(words[i], map.get(words[i]) + 1);
            else
                map.put(words[i], 1);
        }

        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
            (a, b) -> a.getValue() == b.getValue() ?
            b.getKey().compareTo(a.getKey()) : a.getValue() - b.getValue()
        );

        for (Map.Entry<String, Integer> entry: map.entrySet()) {
            pq.offer(entry);
            if (pq.size() > k)
                pq.poll();
        }

        while (!pq.isEmpty())
            result.add(0, pq.poll().getKey());

        return result;
    }
}

**Python**

'''
We know that the maximum frequency of words cannot exceed N because there is a
maximum of N words.

ex.
Input: ["i", "love", "leetcode", "i", "love", "coding"]
Frequency: {"i": 2, "love": 2, "leetcode": 1, "coding": 1}
Group by frequency: { 1: ["leetcode", "coding"], 2: ["i", "love"] }

Hence we can count the frequency of the words and group them by frequency.
Iterate through the group starting from a frequency of N and collect until you
have at least k words. We then sort the final list.
'''
def topKFrequent(self, words, k):
    from collections import Counter
    counter = Counter(words)
    freqs = {}
    for word, count in counter.items():
        if count not in freqs:
            freqs[count] = []
        freqs[count].append(word)
    res = []
    for i in range(len(words), 0, -1):
        if i in freqs:
            for word in freqs[i]:
                res.append((word, i))
        if len(res) >= k:
            break
    res.sort(cmp=lambda a, b: (b[1] - a[1]) if a[1] != b[1] else
        (-1 if a[0] < b[0] else 1))
    return [el[0] for el in res[:k]]