Leetcode 217, 219 & 220. Contains Duplicate I II & III

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Analysis:

Simply put the values in a set. Then check the size of the set equals to the length of th array.

Time complexity: O(n)

Space complexity: O(1)

Below is the code:

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        // O(n) O(1)
        
        if (nums == null || nums.length == 0) {
            return false;
        }
        
        HashSet set = new HashSet<>();
        
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        
        if (set.size() == nums.length) {
            return false;
        }
        
        return true;
    }
}

Followup:

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

Analysis:

To find the the required result. We can put the integers in a hash table. Integer is the key, index is the value. Then we check whether there’s two keys are the same and the value of these two keys are at most k.

Time complexity: O(n)

Space complexity: O(n)

Code is below:

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // O(n) O(n)
        
        if (nums == null || nums.length == 0 || k < 0) {
            return false;
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        
        // Check whether having the same key, but the value is different
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if (i - map.get(nums[i]) <= k) {
                    return true;
                }
            }
            
            map.put(nums[i], i);
        }
        
        return false;
    }
}

Followup:
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

Analysis:

 

Leetcode 136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Analysis:

Bit manipulation. Based on the rules that a ^ b ^ a = b,  0 ^ b = b. So we can go through the whole array and use the xor to get the only one.

Time complexity: O(n)

Space complexity: O(1)

Below is the code:

public class Solution {
    public int singleNumber(int[] nums) {
        // O(n) O(1)
        // a ^ b ^ a = b,  0 ^ b = b
        
        // Corner case
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            result ^= nums[i];
        }
        
        return result;
    }
}

Leetcode 1, 167 & 170 Two Sum I, II && III

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Analysis:

To get two values which the sum of them equals to the target, the brute force one is to have 2 for loop to go over the array twice. This could take O(n^2).

So consider how to get an value very quick, we can have hashtable, which can quickly get the value in nearly O(1).

So basically, what we can do it to put all values in a hash table. Then go over it again to find another value.

Note: here we use the value as key and the index as the value.

Time complexity: O(n)

Space complexity: O(n)

The code is below:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        // Hashtable O(n) O(n)
        
        // Corner case
        if (nums == null || nums.length == 0) {
            return null;
        }
        
        HashMap<Integer, Integer> map = new HashMap<>();
        
        // number as key, index as value
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        
        for (int i = 0; i < nums.length; i++) {
            int temp = target - nums[i];
            if (map.containsKey(temp) && map.get(temp) != i) {
                return new int[] {i, map.get(temp)};
            }
        }
        
        return null;
    }
}

 

Follow up:

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Analysis:

Sorted array? Very familiar? Yes, binary search.

Also we can use another powerful method called two pointers: we can have a start and end. If start + end = target, then return them. If start + end < target, we know that start is small, so we add start by 1. Otherwise reduce the end by 1.

Time complexity: O(n)

Space complexity: O(1)

The code is below:

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        //Two pointers O(n) O(1)
        
        // Corner case
        if (numbers == null || numbers.length == 0) {
            return null;
        }
        
        int start = 0;
        int end = numbers.length - 1;
        
        while (start < end) {
            if (numbers[start] + numbers[end] == target) {
                return new int[] {start + 1, end + 1};
            } else if (numbers[start] + numbers[end] < target) {
                start++;
            } else {
                end--;
            }
        }
        return null;
    }
}

Followup:
Design and implement a TwoSum class. It should support the following operations: add and find.

add – Add the number to an internal data structure.
find – Find if there exists any pair of numbers which sum is equal to the value.

For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

Analysis:

This is more like a design problem. So we can use the similar method to have a hash table to store the value. For adding, we can use map.put() and for finding, we can go through the entrySet and find another value.

Note: for special case where we have multiple values to be the same, like 0, 0, 0 if we want to find 0, it also should return true. So we should add a condition that, if i == j then the occurrence should be larger than 1.

Time complexity: O(n)

Space complexity: O(n)

The code is below:

public class TwoSum {

    HashMap<Integer, Integer> map = new HashMap<>();

    // Add the number to an internal data structure.
	public void add(int number) {
	    if (map.containsKey(number)) {
	        map.put(number, map.get(number) + 1);
	    } else {
	        map.put(number, 1);
	    }
	}

    // Find if there exists any pair of numbers which sum is equal to the value.
    public boolean find(int value) {
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            // Find i + j == value
            int i = entry.getKey();
            int j = value - i;
            
            // special case when i == j 
            if ((i == j && entry.getValue() > 1) || (i != j && map.containsKey(j))) {
                return true;
            }
        }
        return false;
    }
	
}


// Your TwoSum object will be instantiated and called as such:
// TwoSum twoSum = new TwoSum();
// twoSum.add(number);
// twoSum.find(value);

Leetcode 349 & 350.Intersection of Two Arrays I & II

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

• Each element in the result must be unique.

• The result can be in any order.

Analysis:

For two arrays, to compute the intersection, we can go through the first array and put all values in a hashset. Because the result must be unique, so we use hashset. However, like in the follow up question, if we want the result not to be unique, then we should use hashmap. Then go over the second array, if we find that there’s value same in the set, then that’s the intersection. Finally, put all values into an array.

step1: Go over array1, put all values in a set

step2: Go over array2, if we find set contains value in array2, then put it in a set

step3: Go over the set, and put them in a result array.

Time complexity: O(n)

Space complexity: O(n)

Below is the code:

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // O(n) O(n) hashset
        
        // Corner case
        if (nums1 == null || nums2 == null) {
            return null;
        }
        
        // Put all values in nums1 in a hashset
        HashSet set = new HashSet<>();
        HashSet intersection = new HashSet<>();
        
        for (int i = 0; i < nums1.length; i++) {
            set.add(nums1[i]);
        }
        
        // Go over all elements in nums2 and put all commons in result
        for (int i = 0; i < nums2.length; i++) {
            if (set.contains(nums2[i])) {
                intersection.add(nums2[i]);
            }
        }
        
        // Put all nums into the result array
        int[] result = new int[intersection.size()];
        int i = 0;
        for (Integer num: intersection) {
            result[i++] = num;
        }
        
        return result;
    }
}

The followup:

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?

• What if nums1‘s size is small compared to nums2‘s size? Which algorithm is better?

• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Analysis:

Similar to the first question, we can still use hashmap here. Because the result is not unique, so we use hashmap or hashtable.

step1: Go over array1, put all values in a map. The key is the value, the value is the occurrence of that value 

step2: Go over array2, if we find map contains value in array2, then put it in a arraylist

step3: Go over the arraylist, and put them in a result array.

Time complexity: O(n)

Space complexity: O(n)

The code is below:

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // O(n) O(n) hashset
        
        // Corner case
        if (nums1 == null || nums2 == null) {
            return null;
        }
        
        // Put all values in a map as key, occurrence as value
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            if (map.containsKey(nums1[i])) {
                map.put(nums1[i], map.get(nums1[i]) + 1);
            } else {
                map.put(nums1[i], 1);
            }
        }
        
        // Go through nums2
        List results = new ArrayList<>();
        for (int i = 0; i < nums2.length; i++) {             if (map.containsKey(nums2[i]) && map.get(nums2[i]) > 0) {
                results.add(nums2[i]);
                map.put(nums2[i], map.get(nums2[i]) - 1);
            }
        }
        
        // Put the value in an array
        int[] result = new int[results.size()];
        for (int i = 0; i < results.size(); i++) {
            result[i] = results.get(i);
        }
        
        return result;
    }
}

Leetcode 349 Intersection of Two Arrays 1 & 2

Leetcode 349 Intersection of Two Arrays 1

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

• Each element in the result must be unique.
• The result can be in any order.

Analysis:

This problem can be solved by different methods: Hashset and Two pointers

HashSet: no duplicate and no order

• Put numbers in nums1 in a hashset, have another set for result
• Go through nums2 and to see if set contains the number, if contains && resultset not contains, put it in the resultset
• Transfer the numbers out to be the result int[]

Time complexity: O(n)

Space complexity: O(n)

Two pointers:

• Sort both array
• Two pointers start and if nums1[i] < nums2[j], i++; if nums[i] > nums2[j], j++; else add to a set and i++, j++
• Transfer the numbers out to be the result int[]

Time complexity: O(nlogn)

Space complexity: O(n)

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // corner case
        if (nums1 == null || nums2 == null) {
            return null;
        }
        
        
        // Method 1 hashset O(n)
        HashSet set = new HashSet<>();
        HashSet resSet = new HashSet<>();
        
        for (int i = 0; i < nums1.length; i++) {
            set.add(nums1[i]);
        }
        
        
        for (int i = 0; i < nums2.length; i++) {
            if (set.contains(nums2[i]) && !resSet.contains(nums2[i])) {
                resSet.add(nums2[i]);
            }
        }
        
        
        int[] res = new int[resSet.size()];
        int index = 0;
        for (Integer i : resSet) {
            res[index++] = i;
        }
        
        return res;
        
        
        // Method 2 two pointers O(nlogn)
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int i = 0;
        int j = 0;
        
        HashSet set = new HashSet<>();
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {                 i++;             } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                set.add(nums1[i]);
                i++;
                j++;
            }
        }
        
        int[] res = new int[set.size()];
        int index = 0;
        for (Integer k : set) {
            res[index++] = k;
        }

        return res;
    }
    
}

 

 

350. Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?

• What if nums1‘s size is small compared to nums2‘s size? Which algorithm is better?

• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Analysis:

Similar to the above two pointers method, just allows duplicate, then change hashset to a list.

Time complexity: O(nlogn)

Space complexity: O(n)

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // corner case
        if (nums1 == null || nums2 == null) {
            return null;
        }
        
        // Two pointers O(nlogn)
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int i = 0;
        int j = 0;
        
        List list = new ArrayList<>();
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {                 i++;             } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                list.add(nums1[i]);
                i++;
                j++;
            }
        }
        
        int[] res = new int[list.size()];
        int index = 0;
        for (Integer k : list) {
            res[index++] = k;
        }

        return res;

    }
}

Find the first non-repeating character in a String

Given a String, find the first non-repeating character.

For this problem, we can use hashmap to solve it. Two scans are needed for the whole process.

1. Go through the whole string, put the occurrence of each character in the hashmap. Key is each char, value is the number of occurrence.
2. Go through the hashmap, find the first key which has value of 1.

Time complexity: O(n)

public static Character firstNonRepeated (String str) {
	HashMap<Character, Integer>  hashmap = new HashMap<>();

	// put the occurrence of each char in the hashtable
	for (int i = 0; i < str.length(); i++) {
		char c = str.charAt(i);
		if (hashmap.containsKey(c)) {
			hashmap.put(c, hashmap.get(c) + 1);
		} else {
			hashmap.put(c, 1);
		}
	}

	// Search for the first non repeating char
	for (i = 0; i < str.length(); i++) {
		char c = str.charAt(i);
		if (hashmap.get(c) == 1) {
			return c;
		}
	}
	return null;
}

Leetcode 49 Group Anagrams

Leetcode 49 Group Anagrams

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: For the return value, each inner list’s elements must follow the lexicographic order. All inputs will be in lower-case.

 

 

Leetcode 242 Valid Anagram

Leetcode 242 Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

 Analysis:

Anagram (易构词，变位词) is a kind of word, which can produce a new word, after rearranging the order of the characters.

Note: if the length of the two strings are not the same, they’re not anagrams. 

Method 1:

We can try to sort the two arrays and then compare them, if they’re equal to each other, they’re anagrams, vise versa.

        
        if (s.length() != t.length()) {
            return false;
        }
        
        char[] ary1 = s.toCharArray();
        char[] ary2 = t.toCharArray();
        
        Arrays.sort(ary1);
        Arrays.sort(ary2);
        
        return Arrays.equals(ary1, ary2);

Here we should be aware the usage of Arrays. We first need to convert the string to a char array, because the parameter for Array.sort() method is char array. Then we can use the Array.equals method to check whether the two arrays are equal to each other.

Note: For this method, we need to import java.util.Arrays.

Time complexity: O(nlogn + n) = O(nlogn)

Space complexity: O(1)

Assume n is the length of s, then sorting algorithm cost O(nlogn), and comparing two strings cost O(n). The sorting dominates, then it requires O(nlogn).

Method 2:

If method 1 is not allowed, we can try another way. We can count the occurrences of each letter in the two strings and compare them. Since both s and t contain only letters from a-z, a simple counter table of size 26 is suffice.

Do we need two counter tables for comparison? No!

We could use one table to increase the counter for each letter in s and decrease the counter for each letter in t, then check if the counter reaches back to zero.

        int[] counts = new int[26];
        
        for (int i = 0; i < s.length(); i++) {
            counts[s.charAt(i) - 'a']++;
            counts[t.charAt(i) - 'a']--;
        }
        
        for (int count: counts) {
            if (count != 0) {
                return false;
            }
        }
        
        return true;

Or we can first increase the counter for s, then decrease the counter for t. If at any point that counter for t is below 0, we know that there’s other element in t that does not belong to s. The code is:

        int[] count = new int[256];
        
        for (int i = 0; i < s.length(); i++) {
            count[(int) s.charAt(i)]++;
        }
        
        for (int i = 0; i < t.length(); i++) {
            count[(int) t.charAt(i)]--;
            if (count[(int) t.charAt(i)] < 0) {
                return false;
            }
        }
        
        return true;

Time complexity: O(n)
Space complexity: O(1)

Accessing the counter table is constant time, so it’s O(n). For the space, we do have extra counter table. However, its size is fixed, so it’s O(1).

Follow up: what if the inputs contains unicode characters?

Use HashTable instead of counter array.

 

Leetcode 1 Two Sum

Leetcode 1 Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Analysis:

The first problem in Leetcode!!!

Brute force method:

Use two loops, go find int x and then find the value of target – x. This could lead to O(n^2) time complexity.

Alternative method – Hashtable:

Use key for numbers in the array, and the index as the value. Add every number into the hashtable and its index as the value. If found a pair, set their index into the return array.

Time complexity: O(n)

Space complexity: O(n)

As we need to go through the whole array once, so it’s O(n), while look up in hashtable is O(1).

Note: we can not use two pointers here, as we need to find the index and the numbers is not sorted.

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        // method 1: hashtable O(n), O(n)
        if (nums == null || nums.length == 0) {
            return null;
        }
        
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] result = new int[2];
        
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                result[0] = map.get(target - nums[i]);
                result[1] = i;
                break;
            }
            map.put(nums[i], i);
        }
        
        return result;

     // method 2: two pointers O(nlogn + n) = O(nlogn)
     // can not use two pointers here, as we need to sort the array and can not find the index.
    }
}