Arrays and Hashing

In this article, we will discuss some of the most popular algorithm problems using arrays and hashing approaches. Some of these problems I received during interviews. 

Let's start with a problem:

Contains Duplicate

Description:

Given an integer array nums, return true if any value appears at least twice 
in the array, and return false if every element is distinct.

Solution:

What if we add an additional data structure like a HashSet and put elements inside? If we have the same elements in Set before insert, we will return true, and that is it. 

So simple, isn't it?

    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        
        for(int n : nums){
            if(set.contains(n)){
                return true;
            } else {
                set.add(n);
            }
        }
        return false;
    }

Moving on to our next task :

Valid Anagram

Description:

Given two strings s and t, return true if t is an anagram of s, 
and false otherwise. An Anagram is a word or phrase formed by rearranging 
the letters of a different word or phrase, typically using all the original 
letters exactly once.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Solution:

First of all, we should understand what an anagram is. Two words will be anagrams only if they have the same characters. That means that we should compare characters. Characters can be in a different order. We can use a few approaches how to handle it. In the first variant, we can sort characters in each word and then compare them. Or we can create a HashMap and, for one word, add characters, and for another, substruct them. Below is the variant with the sorting algorithm.

    public boolean isAnagram(String s, String t) {
        if(s == null && t == null){
            return true;
        } else if(s == null || t == null){
            return false;
        }
        if(s.length() != t.length()){
            return false;
        }
        char[] sCh = s.toCharArray();
        char[] tCh = t.toCharArray();
        Arrays.sort(sCh);
        Arrays.sort(tCh);
        
        for(int i = 0; i < s.length(); i ++){
            if(sCh[i] != tCh[i]){
                return false;
            }
        }
        return true;
    }

Is it clear? Please, let me know in the comments. 

Our next problem:

Two Sum

Description:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Solution:

This is one of the basic Hash problems. Let's find a brut force solution. We can prepare two for each loop, and iterate over elements and compare their sums. It works, but the time complexity will be O(N^2), and it could be very, very slow. 

But what if, instead of the second loop, we save all previous elements into HashMap? Will it be checked with current elements? For example, we have array [3,3] and target = 6. In the first iteration, we will put into map 3 as the key and 0(index) as the value. And then, on the next iteration, we check the map with target - cur

In our case, it will be 6 - 3 = 3. We have to pair it in our map with element 3 and map it to get the response. 

Let's take a look at the code:

    public int[] twoSum(int[] nums, int target) {
        int[] rez = new int[2];
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++){
            int rest = target - nums[i];
            if(map.containsKey(rest)){
                rez[0] = map.get(rest);
                rez[1] = i;
                return rez;
            } else {
                map.put(nums[i], i);
            }
        }
        return rez;
     }

For some of you, these problems may look easy, but not for me. I spent a lot of time trying to find a correct solution. 

Now we will look at the hardest problem in this article:

Group Anagrams

Description:

Given an array of strings strs, group the anagrams together. 
You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters 
of a different word or phrase, 
typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Solution:

Do you remember the previous problem with Anagrams? I want to use the same approach. We remember that anagrams are words with the same characters, and the same characters count. What if we sort characters in the word and create a string from it? For example, we have [nat, tna]. We sort "nat" and receive "ant." We sort "tan" and again receive "ant." We can sort and put words into a map. And the key will be a sorted string, and the value will be the original word. Smart, isn't it?

Time to look at the code:

 public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String sorted = String.valueOf(chars);
            if (map.containsKey(sorted)) {
                map.get(sorted).add(s);
            } else {
                List<String> list = new ArrayList<>();
                list.add(s);
                map.put(sorted, list);
            }
        }

        return new ArrayList<>(map.values());
    }

I hope you are enjoying this topic. Next time, I'm going to solve more complicated topics. 

Feel free to add your thoughts in the comments. I really appreciate your time and want to hear your feedback.