Blind 75

Array & Hashing

217. Contains Duplicate

// Time: O(n), Space: O(n)
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> res = new HashSet<>();
        for(int i=0; i<nums.length; i++) {
            if(res.contains(nums[i])) {
                return true;
            } else {
                res.add(nums[i]);
            }
        }
        return false;
    }
}

242. Valid Anagram

// Time: O(n), Space: O(n)
class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) {
            return false;
        }

        int[] store = new int[26];

        for(int i=0; i<s.length(); i++) {
            store[s.charAt(i) - 'a'] += 1;
            store[t.charAt(i) - 'a'] -= 1;
        }

        for(int n : store) {
            if(n!=0) {
                return false;
            }
        }

        return true;
    }
}

1. Two Sum

// Time: O(n), Space: O(n)
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> prevMap = new HashMap<>();

        for(int i=0; i<nums.length; i++) {
            int diff = target - nums[i];
            if(prevMap.containsKey(diff)) {
                return new int[] {prevMap.get(diff), i};
            }
            prevMap.put(nums[i], i);
        }

        return new int[] {};
    }
}

49. Group Anagrams

// Time: O(m*n)
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        if(strs.length == 0) {return res;}

        HashMap<String, List<String>> map = new HashMap();

        for(String s : strs) {
            char[] hash = new char[26];

            for(char c : s.toCharArray()) {
                hash[c - 'a'] += 1;
            }

            String key = new String(hash);

            map.computeIfAbsent(key, k->new ArrayList<>());
            map.get(key).add(s);
        }

        res.addAll(map.values());

        return res;
    }
}