Daily Archives: August 5, 2016

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

Solution. Loop from end to start. In this way, we can do this in-place.

public static void merge(int[] nums1, int m, int[] nums2, int n) {
    int k = m + n - 1;
    m--;
    n--;
    while (m >= 0 && n >= 0) {
        if (nums1[m] > nums2[n]) {
            nums1[k--] = nums1[m--];
        }
        else {
            nums1[k--] = nums2[n--];
        }
    }
    while (m >= 0) {
        nums1[k--] = nums1[m--];
    }
    while (n >= 0) {
        nums1[k--] = nums2[n--];
    }
}

Check my code on github.

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Solution. Let’s first talk about the normal Subset problem, which doesn’t has duplicate. There is a loop way rather than recursion. Let’s say [1, 2, 3]. Assume we already have subset(1, 2), which is {[], [1], [2], [1, 2]}.

For 3, we can either add it {[], [1], [2], [1, 2]}

or not add it {[3], [1, 3], [2, 3], [1, 2, 3]}.

So we will have subset(1, 2, 3), which is {[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]}. It’s like for each element, we can either pick up or not pick up it.

For Subsets II problem, let’s say we want to get subset for [1, 2, 3, 3]. Assume we have subset(1, 2) = {[], [1], [2], [1, 2]}. Based on subset(1, 2), we can either add zero 3, add one 3, or two 3 in the subset(1, 2). So the process is like:

public static List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>(Collections.singleton(new ArrayList<>()));
    Arrays.sort(nums);
    int i = 0;
    while (i < nums.length) {
        int next = i + 1;
        while (next < nums.length && nums[next] == nums[i]) {
            next++;
        }
        int size = ans.size();
        for (int j = 0; j < size; j++) {
            List<Integer> curr = new ArrayList<>(ans.get(j));
            for (int k = 1; k <= next - i; k++) {
                curr.add(nums[i]);
                ans.add(new ArrayList<>(curr));
            }
        }
        i = next;
    }
    return ans;
}

Check my code on github.