Leetcode 75. Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.

Could you come up with an one-pass algorithm using only constant space?

Analysis:

The basic (two-pass) way is to count the occurrence of 0, 1 and 2. Then overwrite the corresponding value.

A better (one-pass) way is to use three pointers. One is for left, one is right and one is the index.

If we encounter 0, we swap it with the left value, left++, index++; if we encounter 1, index++; if we encounter 2, swap it with the right value, right–;

Time complexity: O(n)

Space complexity: O(1)

An example for this algorithm is :

1 0 2 2 1 0
    ^         ^
    L         H
    M

    Mid != 0 || 2
    Mid++

    1 0 2 2 1 0
    ^ ^       ^
    L M       H

    Mid == 0
    Swap Low and Mid
    Mid++
    Low++

    0 1 2 2 1 0
      ^ ^     ^
      L M     H

    Mid == 2
    Swap High and Mid
    High--

    0 1 0 2 1 2
      ^ ^   ^
      L M   H

    Mid == 0
    Swap Low and Mid
    Mid++
    Low++

    0 0 1 2 1 2
        ^ ^ ^
        L M H

    Mid == 2
    Swap High and Mid
    High--

    0 0 1 1 2 2
        ^ ^
        L M
          H

    Mid <= High is our exit case

Code is below:

public class Solution {
    public void sortColors(int[] nums) {
        // O(n)
        
        if (nums == null || nums.length == 0) {
            return;
        }
        
        int left = 0; 
        int right = nums.length - 1;
        int i = 0;
        
        while (i <= right) {
            if (nums[i] == 0) {
                swap(nums, i, left);
                left++;
                i++;
            } else if (nums[i] == 2) {
                swap(nums, i, right);
                right--;
            } else {
                i++;
            }
        }
    }
    
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

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;

    }
}